復(fù)雜難度貪心算法實戰(zhàn)

在上一節(jié)介紹了一些初級的編程題后，對貪心算法有了初步的理解，接下來我們會用 leetcode 上 3 道中級和困難題目來幫助大家進一步掌握和應(yīng)用貪心算法。

1. 跳躍游戲

這是 leetcode 上算法部分第55題，為中級編程題。題目描述如下：

給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個位置。

示例 1：

輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置。

示例 2：

輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠(yuǎn)不可能到達最后一個位置。

這道題稍微有點復(fù)雜，官方給出的解法正是貪心思路：首先思考對于數(shù)組中任意一個位置 y, 如何判斷它是否可達？根據(jù)題目表示，只要存在一個位置 x，它本身可達，且它跳躍的最大長度為 x + nums[x]，如果這個值大于等于 y，即 x + nums[x] >= y，即位置 y 也可達。對于每一個可以到達的位置 x，它使得 x+1, x+2, ... , x+nums[x] 這些連續(xù)的位置都可以到達。

這樣以來，我們依次遍歷數(shù)組中的每一個位置，并實時維護最遠(yuǎn)可以到達的位置。

對于當(dāng)前遍歷到的位置 x, 如果它在最遠(yuǎn)可以到達的位置的范圍內(nèi)，那么我們就可以從起點通過若干次跳躍到達該位置，因此我們可以用 x + nums[x] 更新最遠(yuǎn)可以到達的位置。

在遍歷的過程中，如果最遠(yuǎn)可以到達的位置大于等于數(shù)組中的最后一個位置，那就說明最后一個位置可達，我們就可以直接返回 True 作為答案。反之，如果在遍歷結(jié)束后，最后一個位置仍然不可達，我們就返回 False 作為答案。這便是官方給出的貪心思路，非常清晰明了。

最后根據(jù)上述思路我們給出完整的 Python 解答，這個題解來自 leetcode 題解中的一個優(yōu)秀回答，和官方給出的貪心思路一致，都是維護一個從起始點出發(fā)可以達到的最遠(yuǎn)坐標(biāo)。

def canJump(nums):
    # 如果數(shù)組中沒有0，則一定可以到達
    if 0 not in nums: return True
    # 如果只有一個元素，也可以到達
    if len(nums) < 2: return True
    # 維護最長距離
    max_distance = 0
    for i in range(len(nums) - 1):
        # i <= max_distance 表明當(dāng)前位置可以到達
        if i <= max_distance:
            # 更新最大距離
            max_distance = max(i + nums[i], max_distance)
        else:
        # 如果當(dāng)前位置無法到達則結(jié)束    
            break
    # 返回能到達的最大距離是否能到最后一位
    return max_distance >= len(nums) - 1 

我們來看看官方給出的示例代碼，也比較精簡，思路和原理一樣，只不過代碼寫法不同。原代碼為 java，現(xiàn)轉(zhuǎn)成 Python，內(nèi)容如下：

def canJump(nums):
    # 維持最大距離
    max_distance = 0
    for i in range(len(nums)):
        # 非常重要，該點必須可達
        if i <= max_distance:
            # 該點可達，更新能到的最大距離
            max_distance = max(i + nums[i], max_distance)
            # 如歸最大距離能到最后一個位置，直接返回 True
            if max_distance >= (len(nums) - 1):
                return True
        else:
            # 如果i位置無法到達，那么可以直接退出循環(huán)，返回False
            break
    # 無法到達最后，返回False
    return False 

2. 情侶牽手

這是 leetcode 上算法部分的第765題，屬于困難級別，題目描述如下：

N 對情侶坐在連續(xù)排列的 2N 個座位上，想要牽到對方的手。 計算最少交換座位的次數(shù)，以便每對情侶可以并肩坐在一起。 一次交換可選擇任意兩人，讓他們站起來交換座位。

人和座位用 0 到 2N-1 的整數(shù)表示，情侶們按順序編號，第一對是 (0, 1)，第二對是 (2, 3)，以此類推，最后一對是 (2N-2, 2N-1)。

這些情侶的初始座位 row[i] 是由最初始坐在第 i 個座位上的人決定的。

示例 1：

輸入: row = [0, 2, 1, 3]
輸出: 1
解釋: 我們只需要交換row[1]和row[2]的位置即可。

示例 2：

輸入: row = [3, 2, 0, 1]
輸出: 0
解釋: 無需交換座位，所有的情侶都已經(jīng)可以手牽手了。

Tips：

• len(row) 是偶數(shù)且數(shù)值在 [4, 60]范圍內(nèi)；

• 可以保證row 是序列 0...len(row)-1 的一個全排列。

這道題雖然給出困難級別，但是主要是針對使用 O(n) 的算法。如果使用簡單的貪心算法，時間復(fù)雜度為 $O(n^2)$，且解題思路非常清晰。

官方給出的第三種解法正是貪心算法，其思路為：每處理一對元素，如果第二個元素不是第一個元素的情侶，那么就在全局找到第一個元素的情侶，交換他們的位置；依此操作，知道最后一對情侶被安排好。

其中對于位置編號為 x 的人，其情侶編號為 x^1 (^表示異或)，這樣的寫法比較精妙，難以想到，也算是一個小的技巧。有了這個思路，來直接寫出相應(yīng)的 Python 代碼，如下：

def minSwapsCouples(row):
    if len(row) <= 2:
        return 0

    res = 0
    for i in range(0, len(row), 2):
        # row[i]的情侶編號
        couple_id = row[i] ^ 1
        # 如果旁邊正好是他的情侶，直接下一對繼續(xù)判斷
        if row[i + 1] == couple_id:
            continue
        # 如果不是，則需要一次交換
        res += 1
        # 遍歷后續(xù)的人，找到row[i]的情侶，然后交換和row[i+1]的位置
        for j in range(i + 2, len(row)):
            if row[j] == couple_id:
                row[i + 1], row[j] = row[j], row[i + 1]
                break
    # 返回總的交換次數(shù)
    return res

從上面可以看到，算法使用了兩個 for 循環(huán)，時間復(fù)雜度為 O(n^2)。第二個 for 循環(huán)是找對應(yīng) row[i] 的情侶，有沒有辦法加快查找速度呢？在 leetcode 的題解中，有人給出了一個優(yōu)化的解法：將編號和其當(dāng)前所在位置的映射關(guān)系單獨使用一個列表保存，這樣我們查找比如編號為 i 的所在的位置時只需要 O(1) 的復(fù)雜度即可：

for j in range(len(row)):
    seatmap[row[j]] = j

之所以能這樣做的原因就在于題目說明中的第二點：row 中元素的編號是序列 0...len(row)-1 的一個全排列。這是一個典型的用空間換時間的方式。這樣優(yōu)化后的時間復(fù)雜度為 O(n)，空間復(fù)雜度也為 O(n)。具體的實現(xiàn)代碼如下：

def minSwapsCouples2(row):
    res = 0
    seatmap= [0 for _ in range(len(row))]
    for j in range(len(row)):
        # 序號為row[j]的人的座位號為j
        seatmap[row[j]] = j 

    for i in range(0, len(row), 2):
        # 得到row[i]對應(yīng)的情侶編號
        x = row[i]^1
        if x == row[i+1]:
            continue
        # 找到序號為x的人對應(yīng)的座位號
        index = seatmap[x]
        # 交換座位使情侶坐一起
        row[i+1], row[index] = row[index], row[i+1]
        # 更新seatmap，序號為row[index]的人現(xiàn)在在index上
        seatmap[row[index]] = index
        # 對于編號為x人交換到了i+1，這個動作可以不做，因為已經(jīng)配對后續(xù)不會再找編號為x的人
        # seatmap[x] = i + 1
        res += 1
    return res

3. 分發(fā)糖果

這題是 leetcode 算法部分的135題，難度級別為困難。題目描述如下：

老師給孩子們分發(fā)糖果，有 N 個孩子站成了一條直線，老師根據(jù)每個孩子的表現(xiàn)，預(yù)先給他們評分。你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：

• 每個孩子至少分配到 1 個糖果；

• 相鄰的孩子中，評分高的孩子必須獲得更多的糖果；

• 那么這樣下來，老師至少需要準(zhǔn)備多少顆糖果呢？

示例 1：

輸入: [1,0,2]
輸出: 5
解釋: 你可以分別給這三個孩子分發(fā) 2、1、2 顆糖果。

示例 2：

輸入: [1,2,2]
輸出: 4
解釋: 你可以分別給這三個孩子分發(fā) 1、2、1 顆糖果。第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件。

對于這題，官方給出了 4 種解法，其中解法 2 是使用了貪心算法的思想?，F(xiàn)在我們重點介紹下官方的解法 2 以及其貪心點。

在解法 2 中，使用兩個一維數(shù)組 left 和 right。數(shù)組 left 用來存儲每名學(xué)生只與左邊鄰居有關(guān)的所需糖果數(shù)。也就是假設(shè)規(guī)則為：如果一名學(xué)生評分比他左邊學(xué)生高，那么他應(yīng)該比他左邊學(xué)生得到更多糖果。類似的，right 數(shù)組用來保存只與右邊鄰居有關(guān)的所需糖果數(shù)。也就是假設(shè)規(guī)則為：如果一名學(xué)生評分比他右邊學(xué)生高，那么他應(yīng)該比他右邊學(xué)生得到更多糖果。

首先，在 left 和 right 數(shù)組中，給每個學(xué)生 1 個糖果。然后從左向右遍歷整個數(shù)組，只要當(dāng)前學(xué)生評分比他左鄰居高，我們在 left 數(shù)組中更新當(dāng)前學(xué)生的糖果數(shù) left[i] = left[i-1] + 1，這是因為在每次更新前，當(dāng)前學(xué)生的糖果數(shù)一定小于等于他左鄰居的糖果數(shù)。

接下來用同樣的方法從右到左，只要當(dāng)前學(xué)生的評分比他右邊（第 i+1 個）學(xué)生高，就更新 right[i] 為 right[i] = right[i + 1] + 1。現(xiàn)在，對于數(shù)組中第 i 個學(xué)生，為了滿足題中條件，我們需要給他 max(left[i], right[i]) 個糖果。因此，最后我們得到最少糖果數(shù)：

最少糖果數(shù) = $\sum^{n-1}_{i=0}max(left[i], right[i])$，其中， nn 是評分?jǐn)?shù)組的長度。

上述算法在遍歷過程中，每一步都盡量少給糖，必須加的時候加一個，這便體現(xiàn)了貪心思想：且在每次選擇時，以局部最優(yōu)為導(dǎo)向，而不考慮此次操作對以后操作的影響。有了上面的題解思路，我們的 Python 的代碼就能理解寫出，如下：

def candy(ratings):
    # 初始化值
    left = [1] * len(ratings)
    right = [1] * len(ratings)
    # 從左到右，只要當(dāng)前學(xué)生評分比他左鄰居高，則該學(xué)生糖果數(shù)相比左鄰居加1
    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i - 1]:
            left[i] = left[i - 1] + 1
    # 從右到左，只要當(dāng)前學(xué)生評分比他右鄰居高，則該學(xué)生糖果數(shù)相比右鄰居加1
    for i in range(len(ratings) - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            right[i] = right[i + 1] + 1
    # 最后得到最少糖果數(shù)
    return sum([max(left[i], right[i]) for i in range(len(ratings))])

這里的貪心過程會有些難以理解，需要仔細(xì)揣摩。

4. 小結(jié)

本小節(jié)繼續(xù)實戰(zhàn)了貪心算法相關(guān)的編程題，這一次難度相比上一節(jié)有所加深。在 leetcode 上大約 80 道標(biāo)簽為貪心算法的編程題，解題思路都是類似的。再掌握了貪心的解題思路后，大家可以多多嘗試解答 leetcode 上的其他編程題，達到熟能生巧的地步。