贪心系列专题篇一

目录

最长递增子序列

买卖股票的最佳时机

买卖股票的最佳时机II

优势洗牌（田忌赛马）

分发饼干

声明：接下来主要使用贪心法来解决问题！！！

最长递增子序列

题目

思路

之前的博客是使用动态规划来解决这道题的，切入点是找到一个子序列满足最后一个数小于当前位置的数，下面使用贪心法来解决时也是以次为切入点

我们知道，对于一个递增子序列，如果递增子序列某个位置的数在原始数组中该数后面的数比它小，那么可以以这个较小的数替换它，显而易见是可以的，不过这样找出来的结果虽然不是对应的最长递增子序列所对应的数，但是长度是一致的。

更新规则如下：从前往后扫描数组，当找到的数大于已记录的数，就把这个数放到长度更长的对应位置；如果找到的数大于某个位置的数，就往后找到合适的位置；当找到的数小于等于某个位置的数，就覆盖这个位置的数。

优化：扫描整个数组是必不可少的，可优化的地方就是找对应合适的位置，可使用二分查找代替再次遍历整个数组。

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> v;
        v.push_back(nums[0]);
        for(int i=1;i<n;i++){
            if(nums[i]>v.back())
                v.push_back(nums[i]);
            else{
                int left=0,right=v.size()-1;
                while(left<right){
                    int mid=(left+right)>>1;
                    if(nums[i]>v[mid])
                        left=mid+1;
                    else
                        right=mid;
                }
                v[left]=nums[i];
            }
        }
        return v.size();
    }
};//贪心

买卖股票的最佳时机

题目

思路

之前的博客是使用动态规划来解决这道题的，下面将使用贪心法解决这道题

我们能想到的是：从头到尾扫描整个数组，当扫描到某个位置时，找到该位置之前的最小值，这个过程是遍历前面的数，然后让这个数减去前面位置的最小值，不断更新最大利润，但是这种方法的时间复杂度是O(N^2)，对于本道题是会超时的，下面进行优化。

优化：从头到尾扫描整个数组是必不可少的，可优化的地方就是找当前位置之前的数的最小值，我们可以在从前往后扫描过程中使用一个变量来记录当前位置之前的数的最小值；也可以在最开始的时候，先从头到尾遍历整个数组，使用一个数组保存当前位置之前的数的最小值。这样就可以在O(1)的时间复杂度找到当前位置之前的数的最小值。整体时间复杂度是O(N*logN)的，是可以的。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int profit=0,minprice=prices[0];
        for(int i=1;i<n;i++){
            minprice=min(prices[i-1],minprice);
            profit=max(profit,prices[i]-minprice);
        }
        return profit;
    }
};//贪心

买卖股票的最佳时机II

题目

思路

之前的博客是使用动态规划来解决这道题的，下面将使用贪心法解决这道题

我们可以将每一天股票的价格抽象为平面直角坐标系上的一个点。

我们需要做的就是找到所有呈现“上升”趋势的点。

方法一：双指针，定义左右两个指针left和right，初始两个指针在同一位置，当right的下一个数大于当前right的数，right右移；否则，right指针右移，left指针移到和right同样的位置。

方法二：将所有的点划分为一天一天的，只要后一个数大于当前的数，就加上差值。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ret=0;
        int left=0,right=0;
        while(right<n){
            if(right<n-1 && prices[right+1]>prices[right])
                right++;
            else{
                ret+=(prices[right]-prices[left]);
                left=right=right+1;
            }
        }
        return ret;
    }
};//贪心（双指针）








class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ret=0;
        for(int i=0;i<n-1;i++)
            ret+=(prices[i+1]-prices[i]>0?prices[i+1]-prices[i]:0);
        return ret;
    }
};//贪心1（拆分成一天一天）

优势洗牌（田忌赛马）

题目

思路

田忌赛马故事引入

齐王的下中上三种等级的马都各自优于田忌下中上三种等级的马，故各等级的马相斗，田忌输；

但是如果让田忌的中和齐王的下，田忌的上和齐王的中，田忌的下和齐王的上，田忌赢。

利用上面这种思想，我们先对两个数组进行排序，但是这样直接进行排序后虽然结果对应的关系是正确的，但是并不是题目要求的顺序，因此我们对nums1直接排序，对name2的下标进行排序【还是按照nums2数的大小关系】，然后通过比较排完序的nums1和排完序的nums2的下标，给nums1的每个数找对应的位置。

代码

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        vector<int> index(n);
        vector<int> ret(n);
        for(int i=0;i<n;i++)
            index[i]=i;
        sort(nums1.begin(),nums1.end());
        sort(index.begin(),index.end(),[&](int i,int j){
            return nums2[i]<nums2[j];
        });
        int left=0,right=n-1;
        for(int i=0;i<n;i++){
            if(nums1[i]<=nums2[index[left]])
                ret[index[right--]]=nums1[i];
            else
                ret[index[left++]]=nums1[i];
        }
        return ret;
    }
};

分发饼干

题目

思路

这道题采用贪心法，而且这道题和上一道题《优势洗牌（田忌赛马）》非常类似，只是稍有不同。

本道题的贪心策略：

先对两个数组分别进行排升序，使用“双指针” i  和  j，使用ret进行统计可满足孩子的最大数量，如果s[j]>=g[i]，ret++,i++,j++;

否则，j++。当然还需要判断 j 是否小于n.最后返回ret即可。

代码

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int m=g.size(),n=s.size();
        if(n==0) return 0;
        int ret=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int i=0,j=0;
        while(i<m){
            if(s[j]>=g[i])
                ret++,j++,i++;
            else j++;
            if(j>=n)
                break;
        }
        return ret;
    }
};




//or



class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int m=g.size(),n=s.size();
        int ret=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        for(int i=0,j=0;i<m && j<n;i++,j++){
            while(j<n && s[j]<g[i]) j++;
            if(j<n) ret++;
        }
        return ret;
    }
};