网站的ftp服务器,微信crm系统软件,长春百度搜索排名,学校网站的平台用途及建设规划一、贪心算法
贪心没有套路#xff0c;只有碰运气#xff08;bushi#xff09;#xff0c;举反例看看是否可行#xff0c;#xff08;运气好#xff09;刚好贪心策略的局部最优就是全局最优。
1、分发饼干 455
思路#xff1a;按照孩子的胃口从小到大的顺序依次满足…一、贪心算法
贪心没有套路只有碰运气bushi举反例看看是否可行运气好刚好贪心策略的局部最优就是全局最优。
1、分发饼干 455
思路按照孩子的胃口从小到大的顺序依次满足每个孩子对于每个孩子应该选择可以满足这个孩子的胃口且尺寸最小的饼干
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int d1 0, d2 0;int cnt 0;while(d2 s.size() d1 g.size()){if(g[d1] s[d2]){cnt;d1;}}return cnt;}
};2、摆动序列 376
贪心删除单调坡度上的节点这个坡度就可以有两个局部峰值。所以求长度的问题变成求峰值个数。
class Solution {
public:int wiggleMaxLength(vectorint nums) {int cur 0, pre 0;int ans 1;for(int i0; inums.size()-1; i){cur nums[i1] - nums[i]; // 当前的差值// 差值正负出现变化--峰值出现if((cur 0 pre 0) || (cur 0 pre 0)){ans;pre cur; // 只在摆动的时候更新}}return ans;}
};3、最大子序和 53
思路负的子序和只会拉低最大子序和
class Solution {
public:int maxSubArray(vectorint nums) {int ans INT_MIN, s 0;for(int i0; inums.size(); i){s nums[i];if(s ans)ans s;if(s 0)s 0;}return ans;}
};二、写在后面
贪心得多练。今天的摆动序列一开始没想出来。
