算法练习Day25 （Leetcode/Python-贪心算法）

贪心算法基本概念：

贪心的本质是通过选取局部最优达到全局最优。

并没有固定的套路，检验的算法正确性的办法可以是举反例。

455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child?i?has a greed factor?g[i], which is the minimum size of a cookie that the child will be content with; and each cookie?j?has a size?s[j]. If?s[j] >= g[i], we can assign the cookie?j?to the child?i, and the child?i?will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

思路：分饼干，一个饼干最多分给一个人，若饼干大小>=孩子胃口则该孩子获得满足，设计算法尽可能满足更多的孩子。

这道题用贪心算法做，先对饼干和孩子排序。可以从大饼干和胃口大的孩子开始遍历，本着不浪费的原则，大饼干优先满足大胃口的孩子，对于每一块饼干，将胃口从大到小的孩子和它一一对应，如果满足了一个孩子，则move to下一块次大的饼干。

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int] # children 
        :type s: List[int] # cookies
        :rtype: int
        """
        g.sort() # small to large 
        s.sort() # small to large 
        j = len(s) - 1  # cookies
        matched = 0
        for i in range(len(g) - 1, -1, -1):
            if j < 0:  # Check if there are any cookies left
                break
            if s[j] >= g[i]:  # If the current cookie satisfies the appetite, move to the next cookie
                matched += 1
                j -= 1
        return matched

时间复杂度的分析：

sort：O(nlogn)，O(mlogm)。n和m分别为人和饼干的个数

for循环：O(n)。

Overall：O(nlogn) + O(mlogm)。对于较小的n值，O(n)和O(n log n)可能相当接近。但随着n的增大，O(n log n)的增长速度将超过O(n)。

53. Maximum Subarray

Given an integer array?nums, find the?

subarray

?with the largest sum, and return?its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

思路：求最大连续子序列之和。暴力解法O(n^2)的复杂度，做两次循环，遍历所有可能的子序列。但是也可以用一个count逐位累加，在这个过程中不断更新max_count的值。若累加值为负数，则清空重开一局，也就是以之后一个元素为新的子序列开头，防止之前子序列的负数造成拖累。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        max_count = float('-inf') # 注意这里是float('-inf')而不是0，有可能最大和也是是负数。
        for i in range(len(nums)):
            count += nums[i]
            if count > max_count: # 注意这两个if的顺序不可以颠倒
                max_count = count
            if count <= 0: # 若当前子序列累加和都小于0了，对继续延长的序列的也是拖累，不如重新开始。
                           # 重新开始计数之前这个子序列的最大和已经被记录下来了。
                count = 0 
        return max_count 
        # 时间复杂度O(n)