iT邦幫忙

0

貪婪法- 用田忌賽馬的智謀解掉LeetCode三道類似題

今天要分享一道蠻有名的歷史故事- 田忌賽馬,
沒想到這個思維還能夠幫助我們解leetcode?

田忌喜歡和齊威王賽馬賭錢。
他們約定每人都出三匹馬,
用上等對上等,中等對中等,下等對下等。
結果田忌的馬每一匹都跑不過齊威王的馬,輸了不少錢。
孫臏知道後,對田忌說,這次你儘管下注,我保證能讓你贏。
孫臏的辦法是,
用下等馬對齊威王上等馬,
然後用上等馬對齊威王中等馬,
用中等馬對齊威王下等馬。
田忌聽了孫臏的話,結果贏了齊威王兩場,輸了一場。

這個故事跟leetcode什麼關係呢?
我們看這道題870. Advantage Shuffle

Leetcode 870. Advantage Shuffle解析

題意:

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

範例:
Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

這時關聯性出來了,
我們可以把陣列B想成是齊威王的馬,
數字是每匹馬的戰鬥力,比如說[13,25,32,11]
然後我們是田忌,馬兒的戰力為[12,24,8,32]
然後我們要安排一個合理的出戰順序,
讓田忌的馬贏過齊威王的馬的場數愈多愈好

這個範例也是經典的田忌的馬每一匹都跑不過齊威王的馬的情況
若是把A, B陣列先排序過就看的很清楚,
排序A: [8,12,24,32]
排序B: [11,13,25,32]

田忌的馬每一匹都跑不過齊威王的馬那怎麼辦呢?
根據田忌賽馬思維,對於每匹齊威王的馬,我們儘量派出能剛好贏一點的馬就好了,
真的跑不過就派最差的馬去送投

比如說11是齊威王的下馬,以中馬對下馬,
派出剛好贏它一點的馬12

13是齊威王的第二弱的馬,
派出剛好贏它一點的馬24

以推類推,我們讓[12,24,32,8]的順序對陣[11,13,25,32]
贏了三場輸了一場,
皆大歡喜

思路優化,其實不用先對齊威王的馬排序,省時

我們甚至不用對齊威王的馬排序,
田忌的馬排序就行,
反正思路是我們儘量派出能剛好贏一點的馬就好了,
隊伍裡沒有跑的過的馬就放棄
(對田忌的馬排序是因為可以用二分搜索找到剛好贏一點的馬)

為什麼不用先對齊威王的馬排序呢?,
回來看題目的例子,用它的順序
A = [12,24,8,32]
B[0] = 13

我們想要跑贏13這匹馬,
隊伍裡還有[12,24,8,32]四匹馬可用,
在想贏的狀況下一定是派剛好會贏的馬就好,
這邊是派24,不可能派32,過於浪費戰力

棄賽有沒有可能更好呢?
比如說為了保留戰力,故意派最弱的8去對抗13
但是這樣可能結果會更差,
因為有可能後面齊威王的馬還有一隻更弱的,比如說6
送投就白白浪費一隻能夠贏齊威王「下馬」的戰力

結論是能贏的話就小贏一點下來,沒必要保留,
能贏就不必要棄賽,留給真的沒有馬可以贏的時候再棄,效益更大

有了這個策略,
也就不必事先對陣列B做排序了

程式解析

想法有了,但是程式碼怎麼做呢?
我們定義一個函數more_A_bigger_than_B
陣列A, B的元素個數相同,
回傳一組A的排列,使得A有最多的元素大於B

首先對A排序,
我們可以用內建模組bisect
在陣列中查找第一個比指定元素大的數字,
用pop刪除陣列內的元素,
這個做完本題就解了

程式碼內寫i = bisect_right(A, n)%len(A)是因為若bisect_right(A, n)的值為len(A)的話,
表示陣列A沒有一個元素是大於n的,
故策略是派出最弱的A[0]

from bisect import bisect_right
def more_A_bigger_than_B(A,B):
    """
    陣列A, B的元素個數相同,
    回傳一組A的排列,使得A有最多的元素大於B
    """
    A.sort()
    res = []
    for n in B:
        i = bisect_right(A, n)%len(A)
        res.append(A.pop(i))
    return res

類似題分享

上述程式碼只有短短六行,不過很實用,
類似的思路可以解底下兩題,
有興趣的同學可以試試
455. Assign Cookies
1433. Check If a String Can Break Another String


尚未有邦友留言

立即登入留言