Python貪心算法Greedy Algorithm解決案例小結

更新時間：2023年06月16日 15:18:40 作者：ShowMeCoding

這篇文章主要為大家介紹了Python貪心算法Greedy Algorithm解決案例小結，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

貪心算法

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

分發(fā)餅干

455. 分發(fā)餅干

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

# 最好的選擇是不要浪費餅干
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
        # 計數(shù)
        count = 0
        # 終止條件：孩子數(shù) 和 餅干數(shù)是否在條件內
        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

無重疊區(qū)間

435. 無重疊區(qū)間

給定一個區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除區(qū)間的最小數(shù)量，使剩余區(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

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

檸檬水找零

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

以上就是Python貪心算法Greedy Algorithm解決案例小結的詳細內容，更多關于Python貪心算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: