专门做教育咨询有限公司网站,重庆网站制作建设,保定网站建设报价,电商网站建设课件非科班学习算法day27 | LeetCode455:分发饼干 #xff0c;Leetcode376:摆动序列 #xff0c;Leetcode53:最大子数组和 介绍
包含LC的两道题目#xff0c;还有相应概念的补充。
相关图解和更多版本#xff1a;
代码随想录 (programmercarl.com)https://programmercarl.c… 非科班学习算法day27 | LeetCode455:分发饼干 Leetcode376:摆动序列 Leetcode53:最大子数组和 介绍
包含LC的两道题目还有相应概念的补充。
相关图解和更多版本
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF 二、LeetCode题目
1.LeetCode455:分发饼干
题目链接455. 分发饼干 - 力扣LeetCode 题目解析 局部最优的方式是用当前最大的饼干喂胃口最大的孩子并依次向后寻找直到饼干用完或者孩子都吃上。 c代码如下
class Solution {
public:// 数组排序倒序遍历int count 0;int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int max_s s.size() - 1;for (int i g.size() - 1; i 0; i--) {if (max_s 0 s[max_s] g[i]) {count;max_s--;}}return count;}
};
注意点1一开始使用的是双循环然后还用break很难控制而且后来改对了但是容易超时。所以这里学习了使用标记位置的方法满足条件就减去一个饼干
注意点2这里孩子或者饼干的数量是没有固定关系的所以都可能遍历完for循环里控制的是孩子的遍历结束而max_s0控制的是饼干的遍历结束 2.Leetcode376:摆动序列
题目链接376. 摆动序列 - 力扣LeetCode 题目解析 我认为代码随想录中这道题的做法有点分类复杂了虽然最后的代码呈现很简单分为了三种情况去考虑我学习了一种写法我觉得理解更为容易因为我们需要根据局部峰值的数量来统计全局最优的数量那么也就是说只需要比较一个点前后两个坡度的正负甚至值的大小都不重要还有一个点就是怎么处理相等平坡可以直接跳过循环比分类要容易的多。 C代码如下
class Solution {
public:// 开贪--局部最优为删除坡度中间值--全局最优统计峰值局部峰值个数int wiggleMaxLength(vectorint nums) {// 前坡int preDiff 0;// 后坡int curDiff 0;// 计数变量int count 1;// 处理异常if (nums.size() 1)return nums.size();// 统计拐角for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];if ((preDiff 0 curDiff 0) ||(preDiff 0 curDiff 0)) {count;preDiff curDiff;}}return count;}
}; 简易c代码如下
class Solution {
public:// 开贪--也是统计局部峰值int wiggleMaxLength(vectorint nums) {// 初始化计数变量int count 1;// 初始化前坡int preDiff 0;// 初始化后坡int curDiff 0;// 处理异常if (nums.size() 1)return nums.size();// 大于等于两个的序列for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1])continue;curDiff (nums[i] nums[i - 1]) ? 1 : -1;count curDiff ! preDiff;preDiff curDiff;}return count;}
};
注意点1这里运用了三目运算符简化了代码写法主要的意思就是我们在遇到相等的时候已经跳过了那么现在就看是正是负值不重要
注意点2在统计量做增加操作的时候完全可以写成if的形式这里是用了先用bool返回1或者0然后做调整操作。 3.Leetcode53:最大子数组和
题目链接53. 最大子数组和 - 力扣LeetCode 题目解析 首先利用暴力遍历的方法可以计算每一个元素作为开头的子数组的最大和然后用一个全局变量实时维护。 C代码如下
class Solution {
public:// 暴力求解int max_sum INT_MIN;int maxSubArray(vectorint nums) {for (int i 0; i nums.size(); i) {int sum 0;for (int j i; j nums.size(); j) {sum nums[j];max_sum max(max_sum, sum);}}return max_sum;}
};
贪心c代码如下
class Solution {
public:// 开贪遇到总和为负的就重新开始int max_sum INT_MIN;int sum 0;int maxSubArray(vectorint nums) {for (int i 0; i nums.size(); i) {sum nums[i];if (sum max_sum) {max_sum sum;}if (sum 0) {sum 0; // 初始化--重新统计最大}}return max_sum;}
}; 注意点1容易陷入误区认为如果全是负数的序列就会返回0但实际上维护的是max_sum所以不存在该问题仍然会返回序列单个最大值作为结果。
总结 打卡第27天坚持
