小山菌_代码随想录算法训练营第二十九天| 455. 分发饼干 、376. 摆动序列、53. 最大子序和

455. 分发饼干

文档讲解：代码随想录.分发饼干
视频讲解：贪心算法，你想先喂哪个小孩？| LeetCode：455.分发饼干
状态：已完成

代码实现

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 第一种方法从贪心满足最大值sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size() - 1;int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍历学生胃口if (index >= 0 && s[index] >= g[i]) { // 遍历饼干result++;index--;}}return result;// 第二种方法 贪心有限满足最小胃口// sort(g.begin(), g.end());// sort(s.begin(), s.end());// int index = 0;// int result = 0;// for (int i = 0; i < s.size(); i++) { // 遍历饼干//     if (index < g.size() && s[index] >= g[i]) {//遍历学生胃口//         result++;//         index++;//     }// }// return result;}
};

心得体会

1. 理解了贪心的基本概念，有了初步的理解

376. 摆动序列

文档讲解：代码随想录.摆动序列
视频讲解：贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列
状态：已完成

代码实现

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) {return nums.size();}int cur_diff = 0;int pre_diff = 0;int result = 1;for (int i = 1; i < nums.size(); i++) {cur_diff = nums[i] - nums[i - 1];if (pre_diff <= 0 && cur_diff > 0 ||pre_diff >= 0 && cur_diff < 0) {pre_diff = cur_diff;result++;}}return result;}
};

心得体会

1. 这题的特殊情况比较多，比较难想到
2. 采用动态规划的方法后面再实现

53. 最大子序和

文档讲解：代码随想录最大子序和
视频讲解：贪心算法的巧妙需要慢慢体会！LeetCode：53. 最大子序和
状态：已完成

代码实现

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count = count + nums[i];if (count > result) {result = count;}if (count < 0) {count = 0;}}return result;}
};

心得体会

1. 贪心确实比暴力方法更精巧