贪心算法

//遵循某种规律，不断贪心的选取当前最优策略的设计算法
//(1)使用钞票
//（2）LeetCode455 AssignCookies
先排序，在一个个糖果判断
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        std::sort(g.begin(),g.end());
        std::sort(s.begin(),s.end());
        int child=0;
        int cookie=0;
        while(child<g.size()&&cookie<s.size())
        {
            if(g[child]<=s[cookie]){
                child++;
            }
            cookie++;

        }
        return child;
        
    }
};
//（3）摇摆序列leetcode376 wiggle subsequence
给一个随机序列，求序列中满足摇摆序列的最长子序列的长度
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<2){
            return nums.size();
        }
        const int BEGIN=0;
        const int UP=1;
        const int DOWN=2;
        int STATE=BEGIN;
        int max_length=1;
        for(int i=1;i<nums.size();i++){
            switch(STATE){
                case BEGIN:
                    if(nums[i]>nums[i-1]){
                        STATE=UP;
                        max_length++;
                    }else if(nums[i]<nums[i-1]){
                        STATE=DOWN;
                        max_length++;
                    }
                    break;
                case UP:
                    if(nums[i]<nums[i-1]){
                        STATE=DOWN;
                        max_length++;
                    }
                    break;
                case DOWN:
                    if(nums[i]>nums[i-1]){
                        STATE=UP;
                        max_length++;
                    }
                    break;
            }
        }
        return max_length;
        
    }
};
(4)移除k个数字
已知一个使用字符串表示的非负整数num，将num中的k个数字移除，求移除k个数字后肯恩获得的最小的肯恩的新数字
LeetCode402   remove K Digits
枚举不可能，天文数字
 (5)跳跃游戏
 LeetCode 55 Jump Game
 class Solution {
public:
    bool canJump(vector<int>& nums) {
        std::vector<int> index;
        for(int i=0;i<nums.size();i++){
            index.push_back(i+nums[i]);
        }
        int jump=0;
        int max_index=index[0];
        while(jump<=max_index&&jump<index.size()){
            if(max_index<index[jump]){
                max_index=index[jump];
            }
            jump++;
        }
        if(jump==index.size()){
            return true;
        }
        return false;
    }
};
(6)跳跃游戏2 LeetCode 45 Jump Game II
确认可以从第一个位置跳跃到最后一个位置，求最少需要跳跃多少次。
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2){
            return 0;
        }
        int current_max_index=nums[0];
        int pre_max_max_index=nums[0];
        int jump_min=1;
        for(int i=1;i<nums.size();i++){
            if(i>current_max_index){
                jump_min++;
                current_max_index=pre_max_max_index;
            }
            if(pre_max_max_index<nums[i]+i){
                pre_max_max_index=nums[i]+i;
            }
        }
        return jump_min;
    }
};
(7)射气球游戏
LeetCode452 Minimum number os Arrows to Burst ballons
bool cmp(const std::pair<int,int> &a,const std::pair<int,int> &b)
{
    return a.first<b.first;
}
class Solution {
public:

    int findMinArrowShots(vector<pair<int, int>>& points) {
        if(points.size()==0)
        {
            return 0;
        }
        std::sort(points.begin(),points.end(),cmp);
        int shoot_num=1;
        int shoot_begin=points[0].first;
        int shoot_end=points[0].second;
        for(int i=1;i<points.size();i++){
            if(points[i].first<=shoot_end){
                shoot_begin=points[i].first;
                if(points[i].second<shoot_end){
                    shoot_end=points[i].second;
                }
            }else
            {
                shoot_num++;
                shoot_begin=points[i].first;
                shoot_end=points[i].second;
            }
        }
        return shoot_num;
    }
};