石家庄建设路网站,厦门网站设计多少钱,网站建设服务合同是否缴纳印花税,罗湖网站公司前言
考过概率论#xff0c;发过一场烧#xff0c;兜兜转转又一月#xff0c;轻舟已撞万重山#xff0c;赶紧刷题
贪心算法理论基础
贪心的本质#xff1a;局部最优→全局最优无套路#xff0c;常识性推导 举反例
455. 分发饼干 - 力扣#xff08;LeetCode#xf…前言
考过概率论发过一场烧兜兜转转又一月轻舟已撞万重山赶紧刷题
贪心算法理论基础
贪心的本质局部最优→全局最优无套路常识性推导 举反例
455. 分发饼干 - 力扣LeetCode
先排序局部最优最大/小的饼干分给最大/小的小孩秒了 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int j s.size() - 1;int sum 0;for(int i g.size() - 1; i 0; i--){if(j 0 s[j] g[i]){sum;j--;}}return sum;}
}; 376. 摆动序列 - 力扣LeetCode
情况一上下坡中有平坡取一边的差值等于0 情况二数组首尾两端取一个虚拟头preDiff初始为1 情况三单调坡中有平坡遇到拐点再更新prediff class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff; // 注意这里只在摆动变化的时候更新prediff}}return result;}
}; // 题解来的代码类似自己起初的思路可惜自己用flag-1/1调不出来
class Solution {
public:int wiggleMaxLength(vectorint nums) {int res 0;int reverse 0; //初始不知道第一次会上坡还是下坡for(int i 1; i nums.size(); i){if(nums[i-1]nums[i] reverse ! 1){ // 这个≠很精髓res;reverse 1;//记录上坡了}else if(nums[i-1]nums[i] reverse ! 2){res;reverse 2;//记录下坡了} }return res 1; //res是两两比较得来的值差一个边界值要1}
}; 53. 最大子数组和 - 力扣LeetCode
贪心思路若连续和为负数则从下一个数重新开始求连续和注意用result及时记录连续和的最大值也可能是负的 class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) {count nums[i];if (count result) { // 取区间累计的最大值相当于不断确定最大子序终止位置result count;}if (count 0) count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}return result;}
};
后言
第二题死磕太久了蓝受一下子就10点了贪心第一次做好难想哦~
