局部最优解,是一种感觉
455.分发饼干
链接:455. 分发饼干
thought:
如何让更多的孩子吃到合适的饼干呢,重排来实现局部最优,每次我们都挑出当前胃口最小的孩子,从小到大找饼干,只要满足就res++,当最大的饼干都不能满足当前孩子时,返回结果
完整C++代码如下:
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int res=0;sort(g.begin(),g.end());sort(s.begin(),s.end());for(int i=0,j=0;i<s.size()&&j<g.size();i++){if(s[i]>=g[j]){j++;res++;}}return res;}
};
376. 摆动序列
链接:376. 摆动序列
thought:
摆动中,如何始终保持局部最优,只要不断寻找下一个差值不同的即可,这个过程中,用reverse记录即可
完整C++代码如下:
class Solution {
public:int wiggleMaxLength(vector<int>& 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; }
};
53. 最大子数组和
链接:53. 最大子数组和
thought:
- 本题的精髓在于如何在不断遍历中始终记录最大值,答案是用一个相同长度的数组逐个记录当前遍历过的nums和
- 可以建立一个与原数组长度等长的数组,把新数组的值依次更新为(新数组的上一个元素的值与原数组当前索引处元素相加)与(原数组当前元素值)的最大值 最后再遍历新数组的最大值即为解
完整C++代码如下:
class Solution {
public:int maxSubArray(vector<int>& nums) {int size=nums.size();if(size==1)return nums[0];vector<int>nums2(size);nums2[0]=nums[0];for(int i=1;i<size;i++){if(nums2[i-1]<0){nums2[i]=nums[i];}else{nums2[i]=nums[i]+nums2[i-1];}}int max=nums2[0];for(int i=1;i<size;i++){if(max<nums2[i]){max=nums2[i];}}return max;}
};