贪心算法

算法简介

• 贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。
• 贪心算法每一步必须满足一下条件：
  1、可行的：即它必须满足问题的约束。
  2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
  3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

例题

(1) 分发饼干

解题步骤：
a. 对需求因子数组g与饼干大小数组s进行从小到大排序；
b.按照从小到大的顺序使用各饼干尝试是否满足某个孩子，每个饼干只尝试一次。若尝试成功，则换下一个孩子尝试，直到发现没有更多的孩子或者没有更多的饼干，循环结束。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        
        int count = 0;
        
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        
        vector<int>::iterator itg = g.begin();
        vector<int>::iterator its = s.begin();
        
        while( (itg != g.end()) && (its != s.end()) )
        {
            if( *itg <= *its )
            {
                count++;
                ++itg;
            }
            ++its;
        }
        
        return count;
    }
};

（2）摆动序列

自动机自动转换

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        
        if( nums.size() < 2)
        {
            return nums.size();
        }
        
        const static int BEGIN = 0;
        const static int UP = 1;
        const static int DOWN = 2;
        
        int STAT = BEGIN;
        int count = 1;
        
        for(int i=1; i<nums.size(); ++i)
        {
            switch( STAT )
            {
                case BEGIN:
                    if( nums[i] > nums[i-1] )
                    {
                        STAT = UP;
                        ++count;
                    }
                    else if( nums[i] < nums[i-1] )
                    {
                        STAT = DOWN;
                        ++count;
                    }
                    break;
                case UP:
                    if( nums[i] < nums[i-1] )
                    {
                        STAT = DOWN;
                        ++count;
                    }
                    break;
                case DOWN:
                    if( nums[i] > nums[i-1] )
                    {
                        STAT = UP;
                        ++count;
                    }
                    break;
            }
        }
        
        return count;
    }
};

（3）移除K位数字

思想：从高位向低位遍历，如果对应的数字大于下一位数字，则把该位数字去掉，得到数字最小。
最暴力的方法：去掉k个数字，即从最高位遍历k次。时间复杂度高。
使用栈存储最终结果或删除工作，从高位向低位遍历num，如果遍历的数字大于栈顶元素，则将该数字push入栈，如果小于栈顶元素，则进行pop弹栈，直到栈为空或不能再删除数据（k==0）或栈顶小于当前元素为止。

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<int> s;      // 用来存储数字的栈
        string str = "";    // 用来存储返回值的字符串
        
        for(int i=0; i<num.size(); ++i)
        {
            int number = num[i] - '0';      // 字符转整数
            while((s.size() != 0) && (s.back() > number) && (k > 0))    // 栈不为空且栈顶元素大于number且k大于0时，需要弹出栈顶元素
            {
                s.pop_back();
                k--;
            }
            
            if( s.size() != 0 || number != 0)   // 当栈不为空或者number不为0时，入栈
            {
                s.push_back(number);
            }
        }
        
        while( s.size() != 0 && k > 0 )     // 如果栈不为空，且还有数字可以删除，从尾部删除
        {
            s.pop_back();
            k--;
        }
        
        if( s.size() == 0 )
        {
            return "0";
        }
        
        for(int i=0; i<s.size(); ++i)
        {
                str += (s[i] + '0');    // 数字转换为字符串
        }
        
        return str;
    }
};

（4）跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_index = 0;
        int i = 0;
        
        for(; (i<nums.size()) && (i<=max_index); ++i)
        {
            int index = i + nums[i];
            if( index > max_index )
            {
                max_index = index;
            }
        }
        
        
        if( i == nums.size() )
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};