代码随想录算法训练营-回溯算法|455. 分发饼干、376. 摆动序列

1.贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

 455. 分发饼干

1. 局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

2.  for 控制 胃口，里面的 if 控制饼干。

3. 技巧：用了一个 index 来控制饼干数组的遍历，遍历饼干并没有再起一个 for 循环，而是采用自减的方式。

 1 class Solution:
 2     def findContentChildren(self, g, s):
 3         g.sort()  # 将孩子的贪心因子排序
 4         s.sort()  # 将饼干的尺寸排序
 5         index = len(s) - 1  # 饼干数组的下标，从最后一个饼干开始
 6         result = 0  # 满足孩子的数量
 7         for i in range(len(g)-1, -1, -1):  # 遍历胃口，从最后一个孩子开始
 8             if index >= 0 and s[index] >= g[i]:  # 遍历饼干
 9                 result += 1
10                 index -= 1
11         return result

376. 摆动序列

1. 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。

2. 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

3. 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

4. 只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

本题要考虑三种情况：

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

5. 也可以用动态规划进行求解。

 1 class Solution:
 2     def wiggleMaxLength(self, nums):
 3         if len(nums) <= 1:
 4             return len(nums)  # 如果数组长度为0或1，则返回数组长度
 5         curDiff = 0  # 当前一对元素的差值
 6         preDiff = 0  # 前一对元素的差值
 7         result = 1  # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）
 8         for i in range(len(nums) - 1):
 9             curDiff = nums[i + 1] - nums[i]  # 计算下一个元素与当前元素的差值
10             # 如果遇到一个峰值
11             if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
12                 result += 1  # 峰值个数加1
13                 preDiff = curDiff  # 注意这里，只在摆动变化的时候更新preDiff
14         return result  # 返回最长摆动子序列的长度