【算法】前缀和与差分(2)一 一维数组差分
一、差分:一维数组的差分可看作是一维数组前缀和的逆运算。二、差分数组首先给定一个原数组a: a[1]、a[2]、a[3]、......然后构造一个数组b: b[1]、b[2]、...
【算法】广度优先搜索算法(BFS)
一、广度优先搜索的过程 广度优先搜索算法(又称宽度优先搜索算法,BFS)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra...
【算法】二分法—最大化平均值问题简单总结
0.前言通过几道题目 切割钢管、木材加工、切割绳子、均分蛋糕 四道题,尝试了二分法中最大化平均值问题。然后,下面进行简单的对比和总结。1.简单总结while(l < ...
【算法】最短路径算法——Floyed-Warshell算法
如下图所示,我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相怜。最短路径就是指连接两点的这些路径中最短的一条。【注意】边的权值可以为负。当出现负边权...
【算法】二叉树(1):二叉树及其编号
0.前言 二叉树(Binary Tree)的递归定义如下:二叉树要么为空,要么由根结点(root)、左子树(left...
【算法】动态规划(三)——解题方法与解题思路
0.前言动态规划最核心的思想就是:拆分子问题,记住过往,减少重复计算。动态规划可以从下面的参考网上的一个例子:A :"1+1+1+1+1+1+1+1 =?"...
【算法】最大子段和
【题目描述】给出一个长度位n的序列a,选出其中连续且非空的一段使得这段和最大【输入描述】第一行是一个整数,表示序列的长度n。第二行有n个整数,第i个整数表示序列的第i个数字ai【输出描述】输出一行一个...
【算法】最小重量机器设计
【题目描述】设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设Wij 是 从供应商j处购得的部件i的重量,Cij 是相应的价格。 试设计一个算法,给出总价格不超...
【算法】动态规划(二)——数字三角形问题
1.问题描述及状态定义数字三角形问题:有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示:从第一行开的数开始走,每次可以往下或右走一格,直到走到...