目录贪心理论基础什么是贪心贪心的套路贪心一般解题步骤455. 分发饼干题目描述题目例子解题思路376. 摆动序列题目描述题目例子解题思路53. 最大子数组和题目描述题目例子解题思路贪心理论基础什么是贪心贪心的本质是选择每一阶段的局部最优从而达到全局最优贪心的套路贪心没有套路就是从局部最优找整体最优的过程即常识性推导加举反例贪心一般解题步骤将问题分解为若干字问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解455. 分发饼干题目描述假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子i都有一个胃口值g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干j都有一个尺寸s[j]。如果s[j] g[i]我们可以将这个饼干j分配给孩子i这个孩子会得到满足。你的目标是满足尽可能多的孩子并输出这个最大数值。题目例子g [1,2,3], s [1,1],输出1解析有两块饼干s孩子们胃口值是g只能让满足胃口为1的解题思路大胃口优先我是将胃口进行到倒序排列对大胃口找到他的对应饼干比如说[6,4,2,1]对应饼干为[5,3]6没有找到对应的饼干4找到第一个5的饼干标记为True再找下一个满足胃口的饼干最后total2,但是由于用了两次for循环最后超出时间限制class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: total 0 g.sort(reverse True) s.sort(reverse True) used [False] * len(s) for i in range(0,len(g)): for j in range(len(s)): if g[i] s[j] and used[j] False: total 1 used[j] True break return total卡哥的大胃口优先通过index将其锁定在倒序的饼干数组中因为大胃口匹配大饼干大胃口若没有被当前最大饼干[0,index]满足说明没有被满足那就跳过他class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() index len(s) - 1 result 0 for i in range(len(g) - 1, -1,-1): if index 0 and s[index] g[i]: index - 1 result 1 return result小胃口优先我采用双指针来遍历class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() #pg指向g的下标ps指向s的下标 pg ps 0 total 0 #遍历胃口 while pg len(g): #遍历饼干 while ps len(s): #若小胃口满足total1跳出循环不必再找下一个 if g[pg] s[ps]: total 1 break #遍历小饼干 ps 1 #若小胃口满足则对此时的pg和ps1判断下一个人的胃口和满足他的下一个饼干 #若未满足说明此时ps len(s)对ps1则判断下一个人时ps len(s)跳过 pg 1 ps 1 return total卡哥的小胃口优先当饼干指针指向最后一位说明不需再进行下一个人的判断相当于当我上面的一个人小胃口未被满足说明后面的人都无法被满足直接就跳过故此时遍历饼干对上述代码进行了优化class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() index 0 for i in range(len(s)): if index len(g) and g[index] s[i]: index 1 return index376. 摆动序列题目描述如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如[1, 7, 4, 9, 2, 5]是一个摆动序列因为差值(6, -3, 5, -7, 3)是正负交替出现的。相反[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。子序列可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。给你一个整数数组nums返回nums中作为摆动序列的最长子序列的长度。题目例子nums [0]输出1nums [0,1]输出2有一个摆动子序列为两个nums [0,0]输出1无摆动nums [1,3,2]输出3有两个摆动子序列为三个nums [1,3,3,2]输出3有两个摆动子序列为三个nums [1,2,2,3]输出2有一层摆动根据以上示例可以看出摆动序列的子序列一定是从第一个元素开始的因为数组中元素可删除后面的摆动子序列一定是它的子集解题思路根据以上实例有一下四种情况为什么判断的时候不可以用prediff * curdiff 0因为这种情况并没有排除平坡元素例如上坡和平坡平坡和平坡等都满足这个要求局部最优删除单调坡度上的节点不包括单调坡度两端的节点此时该坡度有两个局部峰值整体最优整个序列有最多的局部峰值从而达到最长摆动序列class Solution: def wiggleMaxLength(self, nums: List[int]) - int: #情况三pre考虑首尾元素若数组中只有一个元素返回res 1 #若数组中有两个元素元素相等时curdiff和prediff都为0此时res 1 #若这两个元素不相等时则prediff 0 curdiff ! 0进行res 1即res 2 prediff 0 curdiff 0 res 1 for i in range(len(nums) - 1): curdiff nums[i1] - nums[i] #以平坡最后一个元素为参考,情况一二 if prediff 0 and curdiff 0 or prediff 0 and curdiff 0: res 1 #情况四单调坡有平坡 prediff curdiff return res53. 最大子数组和题目描述给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。题目例子nums [-2,1,-3,4,-1,2,1,-5,4]输出6解题思路局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小全局最优选取最大连续和模拟该过程体会何时局部最优class Solution: def maxSubArray(self, nums: List[int]) - int: res float(-inf) count 0 for i in range(len(nums)): count nums[i] if count res: res count if count 0: count 0 return res