目錄
理論基礎
455.分發餅干
思路
代碼
376.擺動序列
思路
代碼
53.最大子序和
思路
代碼
理論基礎
代碼隨想錄
455.分發餅干
代碼隨想錄
思路
? ? ? ? 可以是大餅干優先滿足大胃口，也可以是小餅干優先滿足小胃口。
代碼
class Solution:def findContentChildren(self, g, s):g.sort() # 將孩子的貪心因子排序s.sort() # 將餅干的尺寸排序index = 0for i in range(len(s)): # 遍歷餅干if index < len(g) and g[index] <= s[i]: # 如果當前孩子的貪心因子小于等于當前餅干尺寸index += 1 # 滿足一個孩子，指向下一個孩子return index # 返回滿足的孩子數目376.擺動序列
代碼隨想錄?
思路
? ? ? ? 真就像Carl哥說的那樣：
貪心算法其實就是沒有什么規律可言，所以大家了解貪心算法 就了解它沒有規律的本質就夠了。
不用花心思去研究其規律， 沒有思路就立刻看題解。
基本貪心的題目 有兩個極端，要不就是特簡單，要不就是死活想不出來。
? ? ? ? ?我連用什么方式來判斷這個是正，下個是負，或者這個是負，下個是正都不會。。。（每日崩潰1/1），其實就是用兩個變量來存儲。計算波峰的次數，具體可以看鏈接。
代碼
class Solution:def wiggleMaxLength(self, nums):if len(nums) <= 1:return len(nums) # 如果數組長度為0或1，則返回數組長度curDiff = 0 # 當前一對元素的差值preDiff = 0 # 前一對元素的差值result = 1 # 記錄峰值的個數，初始為1（默認最右邊的元素被視為峰值）for i in range(len(nums) - 1):curDiff = nums[i + 1] - nums[i] # 計算下一個元素與當前元素的差值# 如果遇到一個峰值if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):result += 1 # 峰值個數加1preDiff = curDiff # 注意這里，只在擺動變化的時候更新preDiffreturn result # 返回最長擺動子序列的長度53.最大子序和
代碼隨想錄?
思路
? ? ? ? 貪心真的很逆天，一點思路都沒有，暴力法最后十個用例過不了的。。。Carl點撥了一下我覺得很有道理，一個負數加一個正數肯定比0加一個正數要小，所以就是從頭開始遍歷起，不斷計算累計和，如果累計和是負數，前面那一整段就不要了，直接0加后面的數，從后面開始重新算。
代碼
class Solution:def maxSubArray(self, nums):result = float('-inf') # 初始化結果為負無窮大count = 0for i in range(len(nums)):count += nums[i]if count > result: # 取區間累計的最大值（相當于不斷確定最大子序終止位置）result = countif count <= 0: # 相當于重置最大子序起始位置，因為遇到負數一定是拉低總和count = 0return result
