贪心算法没有回溯寻找所有可能情况的意识，也不像动态规划那样寻找全局最优。（所以个人觉得贪心算法比回溯和动态规划简单一点哈）贪心算法总是选择每个状态下的局部最优解，然后将所有的局部最优解整合，得到所求解。所以不一定会得到整体最优解，因此贪心策略必须具有无后效性。贪心选择将以自顶向下迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。使用使用贪心算法的一个重要前提就是证明每一个子问题都可以得到局部最优解。通常可以首先证明问题的一个整体最优解是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题；然后用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。贪心算法所能解决的大部分问题具有二分的特性：随着算法的进行，一部分对象被筛选出作为候选添加到结果集中，另一部分对象因为不满足条件而被丢弃。嗯……来两个经典的题。首先可以确定一个条件，如果 sum(gas) < sum(cost) 的话那么一定不能走完一周，反之sum(gas)≥ sum(cost) 一定存在一种走完一周的方式。对于每一次从加油站出发到下一个加油站的子状态，所需满足的条件是邮箱所剩油量不小于所需消耗的量，否则之前的所有行径路程清零，以下一个站作为起点再次出发。结束条件是走完所有加油站。
classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int:ifsum(gas)<sum(cost):return-1tmp,rest,start=0,0,0foriinrange(len(gas)):tmp+=gas[i]-cost[i]rest+=gas[i]-cost[i]iftmp<0:tmp=0start=i+1returnstartifrest>=0else-1
这题典型的特点是无后效性，所以先把 h比较大的放在前面从而不影响到后面 h 比较小的人的排序，一般来说 h 比较高的 k 会比较小，所以对于比较小的 h 来说，k 值恰好表明了它在插入队列时前面所有比它的 h 大的人数，所以直接根据 k 差值就好。这是局部最优，但不是全局最优。我们也不需要全局最优的排序。
classSolution:defreconstructQueue(self,people:List[List[int]])->List[List[int]]:people.sort(key=lambdax:[-x[0],x[1]])res=[]forpinpeople:res.insert(p[1],p)returnres
今天出去浪了……写的挺水的。我检讨
