代码随想录算法训练营第二十七天 | 455.分发饼干，376. 摆动序列，53. 最大子序和
二十七天打卡，今天是贪心算法的第一天，贪心算法没有固定解法，摆动序列这一题要固定判断平坡规则
455.分发饼干
题目链接
做题过程
- 优先小饼干喂小胃口的人，这样能求得最多喂饱的人数。
知识点
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
贪心算法
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int result = 0;sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0;int j = 0;while (i < g.size() && j < s.size()) {if (g[i] <= s[j]) {result++;i++;j++;} else {j++;}}return result;}
};
376.摆动序列
题目链接
做题思路
- 做的时候想用贪心做，但没考虑到平坡的情况，这时要统一规则
知识点
- 本题要考虑三种情况：
- 情况一：上下坡中有平坡
- 情况二：数组首尾两端
- 情况三：单调坡中有平坡
贪心算法
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() < 2) return 1;int prediff = nums[1] - nums[0];int result = 1;if (prediff != 0) result++;for (int i = 2; i < nums.size(); i++) {int curdiff = nums[i] - nums[i - 1];if (curdiff > 0 && prediff <= 0 || curdiff < 0 && prediff >= 0) {result++;prediff = curdiff;}}return result;}
};
53.最大子数组和
题目链接
解题过程
- 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
- 全局最优：选取最大“连续和”
贪心算法
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];result = max(result, sum);if (sum < 0) sum = 0;}return result;}
};