貪心算法

在每一次做決策時，保證當下的決策是最優(yōu)的，從而使得最后的結果是最優(yōu)的。

455. 分發(fā)餅干

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。

# 最好的選擇是不要浪費餅干

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 先對胃口值和餅干尺寸排序
        g.sort()
        s.sort()
        g_l = len(g)
        g_index = 0
        s_l = len(s)
        s_index = 0
        # 計數
        count = 0
        # 終止條件：孩子數 和 餅干數是否在條件內
        while g_index < g_l and s_index < s_l:
            # 胃口小于餅干
            if g[g_index] <= s[s_index]:
                # 餅干被消耗
                count += 1
                g_index += 1
                s_index += 1
            # 胃口大于餅干
            else:
                # 尋求更多的餅干滿足胃口
                s_index += 1
        return count

435. 無重疊區(qū)間

給定一個區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數量，使剩余區(qū)間互不重疊 。
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 判斷是否為空
        if not intervals:
            return 0
        # 對end值進行升序排序
        intervals.sort(key = lambda x: x[1])
        # 維護一個最小值
        end_pos = intervals[0][1]
        # 只有單個區(qū)間時無重疊?。?！因此定義為1
        count = 1
        # 終止條件
        for i in range(1, len(intervals)):
            # 判斷是否連續(xù)
            if end_pos <= intervals[i][0]:
                count += 1
                end_pos = intervals[i][1]
        return len(intervals) - count

二維數組排序的方法：intervals.sort(key = lambda x: x[1])
思路轉換：求最小移除數組，意味著求最大連續(xù)數組

860. 檸檬水找零

輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten, twenty = 0, 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            if bill == 10:
                # 是否可以找回
                if five <= 0:
                    return False
                # 收下 10 元
                ten += 1
                # 找回 5 元
                five -= 1
            if bill == 20:
                # 是否可以找回一張5元和一張10元
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                    twenty += 1
                # 是否可以找回三張 5 元
                elif five >= 3:
                    five -= 3
                    twenty += 1
                else:
                    return False
        return True