赞
踩
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?指定每次拿最大的,最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
拿最大的饼干给胃口最大的孩子,先对数组排序,之后使用双指针思想。
- class Solution {
- public:
- int findContentChildren(vector<int>& g, vector<int>& s) {
- int index1=g.size()-1,index2=s.size()-1;
- int count=0;
- sort(g.begin(),g.end());
- sort(s.begin(),s.end());
- while(index2>=0&&index1>=0){
- if(s[index2]>=g[index1]){
- count++;
- index1--;
- index2--;
- }else index1--;
- }
- return count;
- }
- };

首先假设最前面加一个平坡(解决nums.size()=2的情况),以及最右边有一个摆动res=1(解决所有元素相同的情况),for循环中的if条件preDiff带等号是考虑到有连续相同元素的情况(不带等号就会少加一)。
- class Solution {
- public:
- int wiggleMaxLength(vector<int>& nums) {
- if(nums.size()<=1) return nums.size();
- int curDiff=0,preDiff=0;
- int res=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)){
- res++;
- preDiff=curDiff;
- }
- }
- return res;
- }
- };

如果当前和为负数,那么就放弃从下一个数开始重新累加。
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- //if(nums.size()==1) return nums[0];
- int res=INT_MIN;
- int sum=0;
- for(int i=0;i<nums.size();i++){
- sum+=nums[i];
- if(sum>res) res=sum;
- if(sum<=0) sum=0;
- }
- return res;
- }
- };
把if(sum<=0) sum=0;写在if(sum>res) res=sum;前面,应该先判断当前和与res的大小并对res赋值,如果都是负数的情况下,输出就是0,其实应该输出数组中第一个负数。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。