贪心算法典型例题

贪心是算法中一种特别基础和重要的思想，下面从几个例题中开始讲解贪心的思想。

1. 分糖果(leetcode455)
题目：已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s>=某个孩子的需求因子g时，代表该糖果可以满足该孩子，求使用这些糖果，最多能满足多少孩子（注意，某个孩子最多只能用1个糖果满足）

思考：

• 当某个孩子可以被多个糖果满足时，是否需要优先用某个糖果满足这个孩子？
• 当某个糖果可以满足多个孩子时，是否需要优先满足某个孩子？

• 贪心规律是什么？

  贪心规律：

• 某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子

• 某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果满足需求因子更大的孩子
• 孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正确的结果(因为我们追求更多的孩子被满足，所以用一个糖果满足需求因子较小或较大的孩子都是一样的)。

算法设计：

1. 对需求因子数组g和糖果大小数组s进行从小到大的排序
2. 按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次，只有尝试成功时，换下一个孩子尝试，直到发现没更多的孩子或者没有更多的糖果，循环结束。

代码实现(python)

class Solution:
    def findContentChild(self,g,s):
        g = sorted(g)
        s = sorted(s)
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if g[child] <= s[cookie]:
                child +=1
            cookie+=1
        return child
if __name__ =="__main__":
    g = [5,10,2,9,15,9]
    s = [6,1,20,3,8]
    S = Solution()
    result = S.findContentChild(g,s)
    print(result)

这道题是比较简单的贪心的题目，主要是总结出贪心规律。

2. 摇摆序列(leetcode376)
题目：一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列呗成为摇摆序列，一个小于2个元素的序列直接为摇摆序列，给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。
例如：
序列[1,7,4,9,2,5],相邻元素的差(6,-3,5,-7,3),该序列为摇摆序列
序列[1,4,7,2,5]相差(3,3,-5,3)不是摇摆序列

思考与分析：
[1,17,5,10,13,15,10,5,16,8]，整体不是摇摆序列，但是我们观察该序列的前6位：[1,17,5,10,13,15…];5,10,13,15部分为上升段，其中有三个子序列是摇摆序列：
[1,17,5,10….]
[1,17,5,13,…]
[1,17,5,15…..]
在不清楚原始序列的7为是什么的情况下，只看前6位，摇摆子系列的第四位从10，13，15中选择一个数，我们应该选择那一个？

应该选择使得摇摆子序列长度更长的数，所以应该是15，这样遇到比他小的数的可能性就会大一点，按照这种思路总结出贪心规律

贪心规律：
当序列有一段连续的递增(或递减)时，为形成摇摆子序列，我们只需要保留这段连续的递增(或递减)的首尾元素，这样更有可能使得尾部的后一个元素成为摇摆子序列的下一个元素。

算法设计：

设置最长摇摆子序列长度为max_length，从头到尾扫描原始序列，这个过程中设置三种状态，即起始、上升、下降；不同的状态中，根据当前数字和前一个数字的比较结果进行累加max_length计算或者状态切换

代码实现(python)

class Solution:
    def maxlength(self,nums):
        if len(nums) <2:
            return len(nums)
        BEGIN =0
        UP = 1
        DOWN = 2
        STATE = BEGIN
        max_length = 1
        vision = [UP,BEGIN,DOWN]
        for i in range(1,len(nums)):

                if STATE == 0:
                    if nums[i-1]<nums[i]:
                        STATE = 1
                        max_length+=1
                    elif nums[i-1]>nums[i]:
                        STATE = 2
                        max_length+=1
                if STATE == 1:
                    if nums[i-1] >nums[i]:
                        STATE = 2
                        max_length+=1

                if STATE == 2:
                    if nums[i-1] < nums[i]:
                        STATE = 1
                        max_length +=1
        return max_length
if __name__ == "__main__":
    S = Solution()
    g = [1,17,5,10,13,15,10,5,16,8]
    result = S.maxlength(g)
    print(result)

3. 移除K个数字(leetcode402)
题目：已知一个使用字符串表示非负整数num，将num中的k个数字移除，求移除k个数字后，可以获得的最小的可能的新数字(num不会以0开头，num长度小于10002)

例如：输入：num = “1432219”,k=3
在去掉3个数字后得到的很多可能里，如1432，4322，2219，1219。。。。；去掉数字4、3、2、得到的1219最小

思考与分析：
一个长度为n的数字，去掉k个数字，可以有多少种可能？C(k,n)=n!/(n−k)!∗k!$C(k,n)=n!/(n-k)!\ast k!$种可能
所以用枚举法肯定是不可能的。
若去掉某一位数字，为了使得到的新数字最小，需要尽可能让得到的新数字优先最高位最小，其次次位最小，再其次第三位最小。。。。

例如：一个四位数 “1。。。”，一定比任何“9.。。。”小。
一个四位数若最高位确定，如“51。。”一定比任何“59。。”、“57。。”小。

贪心规律：
从高位向地位遍历，如果对应的数字大于下一位数字，则把该位数字去掉，得到的数字最小。

算法设计：
使用栈存储最终结果或删除工作，从高位向低位遍历num，如果遍历的数字大于栈顶元素，则将该数字push入栈，如果小于栈顶元素则进行pop弹栈，直到栈为空或不能再删除数字(k==0)或栈顶小于当前元素为止。最终栈中从栈底到栈顶存储的数字，即为结果。

下面我们来看看这几个问题：

1. 当所有数字都扫描完成后，K仍然>0，应该做怎么样的处理？
2. 当数字中有0出现时，应该有怎么样的特殊处理？
3. 如何将最后结果存储为字符串并返回？

代码实现(python)：

class Solution:
    def removeknums(self,nums,k):
        s =  []
        nums = list(map(int, nums))
        for i in range(len(nums)):
            number = int(nums[i])
            while len(s)!= 0 and s[len(s)-1]> number and k >0:
                s.pop(-1)
                k -=1
            if number!=0 or len(s)!=0:
                s.append(number)
        while len(s) !=0 and k>0:
            s.pop(-1)
            k-=1
        result = ""

        result = ''.join(str(i) for i in s)

        return result
if __name__ == "__main__":
    S = Solution()
    print(S.removeknums("1432219",2))