无投入网站推广,正安县住房和城乡建设局网站,海口 做网站,响应式网站设计稿目录
一、贪心算法理论基础
二、#xff08;leetcode 455#xff09;分发饼干
三、#xff08;leetcode 376#xff09;摆动序列
四、#xff08;leetcode 53#xff09;最大子序和 一、贪心算法理论基础
1.什么是贪心
贪心的本质是选择每一阶段的局部最优#xf…目录
一、贪心算法理论基础
二、leetcode 455分发饼干
三、leetcode 376摆动序列
四、leetcode 53最大子序和 一、贪心算法理论基础
1.什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
2.贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目做题的时候只要想清楚局部最优是什么如果推导出全局最优其实就够了。
二、leetcode 455分发饼干
力扣题目链接 状态已AC 解题思路是从胃口小的先开始满足
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {// 贪心的思想想要满足最多的孩子就要先从胃口小的孩子开始sort(g.begin(), g.end());sort(s.begin(), s.end());int index 0;for(int i 0; i s.size(); i){if(index g.size() g[index] s[i]){index;}}return index;}
};
三、leetcode 376摆动序列
力扣题目链接 状态没有思路。 这道题如果是在没有做过的情况下遇到首先想到的方法常规解法应该是动态规划
设 dp 状态dp[i][0]表示考虑前 i 个数第 i 个数作为山峰的摆动子序列的最长长度 设 dp 状态dp[i][1]表示考虑前 i 个数第 i 个数作为山谷的摆动子序列的最长长度 动态规划的初始状态dp[0][0] dp[0][1] 1转移方程
dp[i][0] max(dp[i][0], dp[j][1] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山谷后面作为山峰。 dp[i][1] max(dp[i][1], dp[j][0] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山峰后面作为山谷。
class Solution {
public:int dp[1005][2];int wiggleMaxLength(vectorint nums) {memset(dp, 0, sizeof dp);dp[0][0] dp[0][1] 1;for (int i 1; i nums.size(); i) {dp[i][0] dp[i][1] 1;for (int j 0; j i; j) {if (nums[j] nums[i]) dp[i][1] max(dp[i][1], dp[j][0] 1);}for (int j 0; j i; j) {if (nums[j] nums[i]) dp[i][0] max(dp[i][0], dp[j][1] 1);}}return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);}
};
这道题还有优化的空间就是使用贪心算法使用贪心算法要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size() 1) return nums.size();int curDiff 0;int preDiff 0;int res 1;for(int i 0; i nums.size()-1; i){curDiff nums[i1] - nums[i];if((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)){res;preDiff curDiff;}}return res;}
};
四、leetcode 53最大子序和
力扣题目链接 状态暴力解法超时。 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。全局最优选取最大“连续和”
局部最优的情况下并记录最大的“连续和”可以推出全局最优。
class Solution {
public:int maxSubArray(vectorint nums) {int res INT_MIN;int count 0;int len nums.size();for(int i 0; i len; i){count nums[i];if(count res){res count;}if(count 0) count 0;}return res;}
};
