朝阳区住房和城乡建设部网站,网站推广联系磁遁8刺盾云,网站数据分析表格,网站底部图标代码题目#xff1a;455. 分发饼干
贪心第一题
这里的局部最优就是大饼干喂给胃口大的#xff0c;充分利用饼干尺寸喂饱一个#xff0c;全局最优就是喂饱尽可能多的小孩。或者小饼干先喂饱小胃口
首先要对 g 和 s进行排序这样才能知道最大的胃口和最大的饼干然后进行遍历即可…题目455. 分发饼干
贪心第一题
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。或者小饼干先喂饱小胃口
首先要对 g 和 s进行排序这样才能知道最大的胃口和最大的饼干然后进行遍历即可
两种方法代码如下
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;}
};class Solution {
public:int findContentChildren(vectorint g, vectorint 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;}
};
题目376. 摆动序列
这题确实自己想复杂了 自己在想如何删除元素 因为最后只要计数确实最简单的方法就是遇到峰值就 单调的就不
但是这道题目写代码的话细节还是很多的 需要看视频考虑多种情况
这里的局部最优删除单调坡度上的节点不包括单调坡度两端的节点这个坡度就可以有两个局部峰值
这是我们思考本题的一个大体思路但本题要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
完整代码如下
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;}
};
题目53. 最大子数组和
暴力解法的思路第一层 for 就是设置起始位置第二层 for 循环遍历数组寻找最大值
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) { // 设置起始位置count 0;for (int j i; j nums.size(); j) { // 每次从起始位置i开始遍历寻找最大值count nums[j];result count result ? count : result;}}return result;}
};
使用贪心的话 就是寻找局部极大值
如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是贪心贪的地方
局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
全局最优选取最大“连续和”
局部最优的情况下并记录最大的“连续和”可以推出全局最优。
那有同学问了区间终止位置不用调整么 如何才能得到最大“连续和”呢
区间的终止位置其实就是如果 count 取到最大值了及时记录下来了。
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;}
};
