iT邦幫忙

0

【LeetCode巧解欣賞】1049. Last Stone Weight II,石頭對撞問題

題目: 1049. Last Stone Weight II
題意: 有一堆石頭,我們可以任意拿兩個石頭對撞,如果兩個石頭一樣重,兩個石頭都會消失; 否則輕的那顆會消失,大的減去小的石頭重量。

例如: Input: [2,7,4,1,8,1]
(1) 2,4對撞=>[2,7,1,8,1]
(2) 7,8對撞=>[2,1,1,1]
(3) 2,1對撞=>[1,1,1]
(4) 1,1對撞=>[1]
對撞到只剩一顆石頭,求最小可能的石頭重量?

解法一、異想天開的隨機演算法

當我一開始看到這一題的時候,完全不知道該怎麼做,
我覺得拿兩個石頭對撞的可能性實在太多了,
不太可能用窮舉的,
我就異想天開的想說那每次都隨便拿兩個石頭出來對撞吧,
每次隨便拿兩個石頭出來對撞會算出一個答案,
只要重複夠多次,
總有機率剛好撞到剩下最小可能的石頭重量

重複一百次,
取最小的那個答案

class Solution:
    def random_smash(self, stones):
        C = stones[:]
        while len(C)>1:
            a = random.choice(C)
            C.pop(C.index(a))
            b = random.choice(C)
            C.pop(C.index(b))
            C.append(abs(a-b))
        return C[0]
    
    def lastStoneWeightII(self, stones: List[int]) -> int:
        m = float('inf')
        for i in range(100):
            m = min(m, self.random_smash(stones))
        return m

有點不可思議的是,我這樣寫竟然過關了
(由於是「隨機演算法」,我想有機率會不過關,但我不知道能過測資的機率為何)

解法二、集合分成兩個子集合,集合和的差最小是多少?

後來當我看了別人的解答之後,真的是嘆為觀止,
實在厲害到很難想到,
這題等價說求把一個集合分成兩個子集合,
集合和的差最小是多少?
(如果把石頭分成兩堆,每次都拿不同兩堆的石頭互撞,剩下石頭一定是集合和的差)

想法如下: 一開始定義集合diffSet = {0},
收集所有可能的子集合和的差,
之後每次加入一顆石頭(想像把石頭分兩堆放到天平上),
要嘛放重的那邊增加差距,要嘛減少

最後的程式碼非常簡潔,大概真的只能用欣賞的角度來看了~

class Solution(object):
    def lastStoneWeightII(self, stones):
        diffSet = {0} # 所有可能的子集合和的差
        for x in stones:
            diffSet = {e for d in diffSet for e in [abs(d - x), abs(d + x)]}
        return min(diffSet)

尚未有邦友留言

立即登入留言