训练营：贪心篇

贪心就是：局部最优

1、
455. 分发饼干

 按照饼干分，从大到小，最大的给胃口最大能满足的

def findContentChildren455(g, s):g = sorted(g,reverse=True)s = sorted(s,reverse=True)j=0c = 0i=0while(i<len(s) and j<len(g)):if s[i]>=g[j]:c = c+1j = j + 1i=i+1else:j = j+1return c

2、
860. 柠檬水找零

这就比较简单了，就是if列举

def lemonadeChange860(bills):res={"5":0,"10":0,"20":0}for i in range(len(bills)):if bills[i]==5:res["5"]=res["5"]+1elif bills[i]==10:if res["5"]>0:res["10"] = res["10"]+1res["5"] = res["5"]-1else:return Falseelse:if res["10"]>0 and res["5"]>0:res["10"] = res["10"]-1res["5"] = res["5"]-1elif res["5"]>2:res["5"] = res["5"]-3else:return Falsereturn True

3、
406. 根据身高重建队列

关键是排序，身高从大到小排，以及第二个数从小到大排，这样能把等于的也算上，然后，第二个数其实就是他在从大到小排的时候，排在第几的位置

def reconstructQueue40602(people):if len(people)<2:return people#people.sort(key=lambda x: (x[0], ~x[1]),reverse=True)people.sort(key=lambda x: (-x[0], x[1]))print(people)res = []for i in range(0,len(people)):tmp = people[i]res.insert(tmp[1],tmp)return res

4、
452. 用最少数量的箭引爆气球

这道题的关键就是更新最小区间，左边界从小到大排序之后，主要就是右边界

我会再申请一个数组记录当前区间，或者记录右区间

  def findMinArrowShots(self, points: List[List[int]]) -> int:points = sorted(points)# print(points)c=1res = points[0][1]for i in range(1,len(points)):tmp = points[i]# if res[1]>= tmp[0]:#     res[0] = tmp[0]#     res[1] = min(res[1],tmp[1])if res >= tmp[0]:res = min(res, tmp[1])else:c=c+1res = tmp[1]return c

5、
435. 无重叠区间

 和上面的题类型，从小到大排序，重叠的话去掉右边界大的，如果直接pop会超时，不需要真的去掉，s不跳到那个数上就行，不重叠的话s=i

def eraseOverlapIntervals43502(intervals):intervals = sorted(intervals)print(intervals)i=1c=0s = 0while i<len(intervals):if intervals[s][1]>intervals[i][0]:if intervals[s][1]>intervals[i][1]:s = ic = c+1else:s = ii=i+1return c

6、
56. 合并区间

右边界的对比，总习惯去新申请一下内存记录当前值，代码随想录里面都是在原数组里面直接改，速度虽然差不多，但是内存会小很多，对比一下

def merge56(intervals):intervals = sorted(intervals)tmp = intervals[0][1]s = intervals[0][0]res=[]for i in range(len(intervals)):if tmp>=intervals[i][0]:tmp = max(tmp,intervals[i][1])else:res.append([s,tmp])s = intervals[i][0]tmp = intervals[i][1]res.append([s, tmp])return res

def merge5602(intervals):intervals = sorted(intervals)res=[]res.append(intervals[0])for i in range(1,len(intervals)):if res[-1][1]>=intervals[i][0]:res[-1][1] = max(res[-1][1],intervals[i][1])else:res.append(intervals[i])#res.append([s, tmp])return res

7、
738. 单调递增的数字

关键是从后往前找，小了就减1，然后后面的都为9，还有int转str，然后切片

def monotoneIncreasingDigits73802(n):n = str(n)for i in range(len(n)-1,0,-1):if n[i-1]>n[i]:#n[i] = n[i]-1a = n[:i-1]b = str(int(n[i-1])-1)c = ("9"*(len(n)-i))n=n[:i-1]+str(int(n[i-1])-1)+("9"*(len(n)-i))return int(n)

8、
714. 买卖股票的最佳时机含手续费

 这题还挺巧妙的，关键是买入之后，新的值为prices[i]-tee，因为有可能存在比它更大的，那这次就不算买入，只收一次手续费

后面只有比他-手续费还小，这次才保留卖出，记录新的买入值

def maxProfit714( prices, fee):sum = 0t = prices[0]for i in range(1,len(prices)):if prices[i]<t:t = prices[i]elif prices[i]-t-fee>0:sum = sum+prices[i]-t-feet = prices[i]-feereturn sum

总结：

贪心就是局部最优，关键还是思路