贪心算法
贪心策略在实现时，经常使用到的技巧：
根据某标准建立一个比较器来排序
根据某标准建立一个比较器来组成堆
举例题目：会议室安排
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目）还有这个会议室开放的最早时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回这个最多的宣讲场次。
我们发现，以会议开始的时间越早越先被安排是不对的，可以轻易举出反例如下，因为这样的话我们只会安排会议a。
同时，如果以会议持续的时间越短，越先被安排，也是不对的。如下我们只会安排会议b。
正确的应该是以会议结束的时间越早，越先安排，代码如下：
public class Program{
public int start;
public int end;
public Program(int start, int end){
this.start = start;
this.end = end;
}
}
public static class ProgramComparator implements Comparator<Program>{
@Override
public int compare(Program p1, Program p2){
return p1.end-p2.end;
}
}
public boolean ManageMeetings(Program[] programs, int timePoint) {
Arrays.sort(programs, new ProgramComparator());
int result = 0;
for(int i=0;i<programs.length;i++){
if(programs[i].start>=timePoint){
timePoint=programs[i].end;
result++;
}
}
return result;
}
贪心算法正确性的实战验证（对数器）
1.实现一个不依靠贪心策略的解法X,可以用最暴力的尝试
2.脑补出贪心策略A、贪心策略B、贪心策略C.,.
3.用解法X和对数器，去验证每一个贪心策略
举例：字符串重排后字典序最小（说明理论上来验证贪心的正确性十分复杂）
给定一组字符串数组，重新排列每个字符串的顺序，使之拼接后组成一个字典序最小的字符串。
如果字符串a和字符串b拼接，a在前的话我们记作a#b，b在前的话我们记作b#a。
这道题的正确贪心策略是，如果a#b的字典序小于b#a的字典序，那么我们优先安排a。
那么如何证明这个策略是有效的呢？首先我们要证明这个策略具有传递性。
什么是传递性，就是譬如一般的数字比较，如果a＜b，b＜c，那么我们就能得出a＜c。
有什么策略是不具有传递性的吗？有的，譬如剪刀石头布就不具有传递性。
也就是说，我们接下来要证明如下：（黄色的小于号代表是字典序小于的意思）
if a#b＜b#a
and b#c＜c#b
then a#c＜c#a
证明具体过程如下：我们记字符串a的长度为stra，字符串b的长度为strb，字符串c的长度为strc
字典序就是将字符串转化为十六进制后，比较数字的大小。那么a#b的字典序就是a16^strb+b（从这里开始，之后的a都代表着原来的字符串转化为十六进制后的数，其他字母同理）
在这我们再次记16^strb为m(b)，那么a#b的字典序就是am(b)+b，即
a#b=a*m(b)+b
b#a=b*m(a)+a
b#c=b*m(c)+c
c#b=c*m(b)+b
a#c=a*m(c)+c
c#a=c*m(a)+a
我们要证明的再次转变成了（以下的小于号代表的就是数学上的小于号）
if a*m(b)+b<b*m(a)+a，记为式子A
and b*m(c)+c<c*m(b)+b，记为式子B
then a*m(c)+c<c*m(a)+a，记为式子C
我们将式子A-b再*c，得到a*m(b)*c<(b*m(a)+a-b)*c
右边部分展开来，即a*m(b)*c<b*m(a)*c+a*c-b*c
此时左边部分，记作X
我们将式子B-c再*a，得到b*m(c)*a<(c*m(b)+b-c)*a
右边部分展开来，即b*m(c)*a<c*m(b)*a+b*a-c*a
再将右边的最后两项移到左边来，即b*m(c)*a+c*a-b*a<c*m(b)*a
此时右边部分，记作Y
我们发现X=Y。那么就可以推出b*m(c)*a+c*a-b*a<X/Y<b*m(a)*c+a*c-b*c
也就是b*m(c)*a+c*a-b*a<b*m(a)*c+a*c-b*c
把相同项c*a去掉，得到b*m(c)*a-b*a<b*m(a)*c-b*c
再把相同因子b去掉，得到m(c)*a-a<m(a)*c-c
再把左右的常数项调换位置，得到m(c)*a+c<m(a)*c+a
我们发现，这就是式子C，得证
这只是第一步，证明传递性，我们还有之后证明，两两交换位置后，策略没有更优。三三交换位置后，策略没有更优，四四交换位置后，策略没有更优……
所以不建议理论上去证明贪心的正确性，直接用对数器在实践上证明即可。
举例题目：
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金
条，不管切成长度多大的两半，都要花费20个铜板。
一群人想整分整块金条，怎么分最省铜板？
例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60.
金条要分成10,20,30三个部分。如果先把长度60的金条分成10和50，花费60;
再把长度50的金条分成20和30，花费50；一共花费110铜板。
但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20,
花费30；一共花费90铜板。
输入一个数组，返回分割的最小代价。
lc455.分发饼干
class Solution(object):
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
# 排序g和排序s，遍历s序列，找寻与s[i]最接近的数值。g[i]<=s[i] 双指针, 时间复杂度O(m+n)
g.sort()
s.sort()
i, j = 0, 0
ans = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]: # 如果当前饼干能满足当前孩子
ans += 1
i += 1 # 移动到下一个孩子
j += 1 # 无论饼干是否满足能满足当前孩子，饼干指针都前进。
# 因为已经是排序后的了，当前饼干都满足不了当前孩子的话，说明饼干不够大
return ans
时间复杂度：35ms，击败85.07%，时间复杂度为O(nlogn)
lc376.摆动序列
思路
首先想到的是，保留峰值，即驻点，局部最大值或局部最小值。然后将处于单调上坡或单调下坡的元素都删掉。
那么很重要的一个问题就是，首尾元素算不算峰值呢？
代码1：错误示范，将首尾元素算为峰值
本人一开始想的是，首尾元素算是峰值，肯定会被记录的。
所以第一版代码如下：
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return 1
if len(nums) == 2:
if nums[0] != nums[1]:
return 2
else:
return 1
if len(nums) ==3:
if nums[1] < nums[0] and nums[1]<nums[2]:
return 3
elif nums[1] > nums[0] and nums[1]>nums[2]:
return 3
else:
return 1
# 保留峰值（首尾元素都算），将单调坡上的元素都删除
ans = 2
for i in range(1, len(nums)-1):
# 从第二个元素到倒数第二个元素遍历
if nums[i] > nums[i+1] and nums[i] > nums[i-1]:
# 高峰峰值
ans += 1
elif nums[i] < nums[i+1] and nums[i] < nums[i-1]:
# 低峰峰值
ans += 1
return ans
但实际上这个代码实现是有问题，就是当遇到有相邻重复元素，也就是平坡时，会漏算一些可能的摆动值。
譬如序列：[0, 1, 1, 0]，返回的是2而不是预期结果3。
代码2：错误示范，将首尾元素算为峰值并考虑平坡元素
如上代码原本本人是没有加对于len为3的边界情况判断的，也是因为提交后发现对于[0,0,0]通不过，当时没想到这是平坡的情况，以为单纯是长度为3而中间元素又刚好与首尾元素相同时，应该额外加个边界判断。而现在考虑了平坡的情况，所以长度为3的边界判断就不必如此复杂了于是代码变为如下：
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return 1
if len(nums) == 2:
if nums[0] != nums[1]:
return 2
else:
return 1
if len(nums) == 3:
ans = 1
else:
ans = 2
i = 1
while i < len(nums)-1:
# 从第二个元素到倒数第二个元素遍历
if nums[i] > nums[i+1] and nums[i] > nums[i-1]:
# 高峰峰值
ans += 1
elif nums[i] < nums[i+1] and nums[i] < nums[i-1]:
# 低峰峰值
ans += 1
elif nums[i] == nums[i+1] and nums[i]!=nums[0] and nums[i]!= nums[len(nums)-1]:
# 遇到平坡元素，且不与首尾元素相同时，将平坡所有元素算作1个
ans += 1
# 跳过后面平坡的重复值
while nums[i] == nums[i+1]:
i += 1
i += 1
return ans
但是这个代码还是有问题，就是它没有记录单调坡是上行还是下行的情况，而且又将首尾元素默认一定是峰值并记录，遇到以下情况就会行不通。譬如序列[1,7,7,9,9,5]，我们将平坡都算作一个元素，那么就相当于序列[1,7,9,5]，可以看到最后9和5是在同一段单调下行坡上的。
代码3：错误示范，用布尔值来记录上下行状态的变化
为此我们应该使用一个变量来跟踪当前摆动的状态（上升或下降）。只将首元素默认为峰值并记录，根据最后的摆动状态来判断是否应该加入尾元素。在此我选择了布尔值，代码如下：
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return 1
if len(nums) == 2:
if nums[0] != nums[1]:
return 2
else:
return 1
ans = 1
pre_diff = None
# 记录上下行状态，True时说明是上行
for i in range(1, len(nums)):
# 从第二个元素到最后一个元素遍历
diff = (nums[i]-nums[i-1]) > 0
if diff != pre_diff:
# 说明是峰值
ans += 1
pre_diff = diff
return ans
然而这也是错误的，因为布尔值是无法区分平坡元素和下行元素的。当遇到[7,3]和[7,7]时，diff都是False，然而对于平坡元素和下行元素，我们是要进行不同的处理的，前者我们需要浓缩所有平坡元素为1个，再加入答案，后者我们是直接加入答案。
代码4：正确示范
class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return 1
if len(nums) == 2:
if nums[0] != nums[1]:
return 2
else:
return 1
ans = 1
pre_diff = 0
# 记录上下行状态，>0时说明是上行，<0时说明是下行，==0时说明是平坡
for i in range(1, len(nums)):
# 从第二个元素到最后一个元素遍历
diff = nums[i]-nums[i-1]
if (diff > 0 and pre_diff <= 0) or (diff < 0 and pre_diff >= 0):
# 说明是峰值
ans += 1
pre_diff = diff
# 而因为diff不为0，所以只会记录到与首元素不相同的第一个平坡元素。
return ans
效率：0ms，击败100.00%，时间复杂度O（N）
lc53.最大子数组和
贪心
连续子数组，也可以想到前缀和的思想，在这里我们思考一下，一个长度为a的序列的和的最大值，一定是从以每一个元素为结尾（包含该元素）的各个序列的和中挑选出最大值的。
那么就可以看成【前面a-1个元素的序列的和的最大值】和【最后一个数值】这两部分。
此时如果【前面a-1个元素的序列的和的最大值】是负数的话，我们应该直接舍去这部分，只要【最后一个数值】这一部分，就能达到最大。
所以代码如下：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = nums[0]
pre_sum = nums[0]
for i in range(1, len(nums)):
if pre_sum < 0:
pre_sum = nums[i]
else:
pre_sum += nums[i]
ans = max(ans, pre_sum)
return ans
效率：63ms，击败97.54%，时间复杂度为O(N)。
动态规划
这道题也有动态规划的解法：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 看到连续子数组，应该想到dp动态规划。设 dp[i] 表示以 nums[i] 结尾（包含nums[i]）的子数组的最大和。
# 对于每个元素 nums[i]，我们可以选择将其与前面的子数组相加，或者只选择 nums[i] 本身
ans = nums[0]
dp = [nums[0]] * len(nums)
for i in range(1, len(nums)):
dp[i] = max(dp[i-1]+nums[i], nums[i])
ans = max(ans, dp[i])
return ans
效率：击败20%-60%不等，时间复杂度为O(N)。
lc122.买卖股票的最佳时机
思路
这道题如果用贪心来解的话，需要想清楚一点就是，举例：
输入：prices = [1,2,3,4]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 4 天 （股票价格 = 4）的时候卖出, 这笔交易所能获得利润 = 4 - 1 = 3。
最大总利润为 3 。
在【第 1 天买入，在第 4 天卖出】所收获的利润
实际上等于
【（在第1天买入， 在第二天卖出的利润）+（在第2天买入，在第3天卖出的利润 ）+ （在第3天买入，在第4天卖出的利润）】
即 4-1 = （2-1） + （3-2） + （4-3）
只要当天和前一天的利润差为正值，我们就卖出。那么结果就是所有正值利润差之和。贪心贪就贪在，因为买入无成本，所以每天都试图卖出并买入
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
ans = 0
# 贪心，每天都试图买入和卖出
for i in range(1, len(prices)):
# 当天与前一天的价格差
cur_diff = prices[i] - prices[i-1]
if cur_diff > 0:
ans += cur_diff
return ans
效率：4ms，击败99.02%，时间复杂度O（N）