主題

LeetCode - 914. X of a Kind in a Deck of Cards 解題心得

Not In My Back Yard | 2021-02-12 00:00:04

題目連結:


題目意譯:
在一疊紙牌中,每張牌上都寫有一個數字。

回傳真(True)若且唯若你可以選擇 X ≧ 2,使得可以將整疊紙牌分割為 1 個或多個群組,其中:
每個群組恰好 X 張牌。
每個群組中的紙牌上的整數皆相同。

限制:
1 ≦ deck.length ≦ 10^4
0 ≦ deck[i] < 10^4



範例測資:
範例 1:
輸入: deck = [1,2,3,4,4,3,2,1]
輸出: true
解釋: 可行的分割為 [1,1][2,2][3,3][4,4]。

範例 2:
輸入: deck = [1,1,1,2,2,2,3,3]
輸出: false´
解釋: 沒有任何可行的分割方式。

範例 3:
輸入: deck = [1]
輸出: false
解釋: 沒有任何可行的分割方式。

範例 4:
輸入: deck = [1,1]
輸出: true
解釋: 可行的分割為 [1,1]。

範例 5:
輸入: deck = [1,1,2,2,2,2]
輸出: true
解釋: 可行的分割為 [1,1][2,2][2,2]。


解題思維:
利用雜湊表(Hash Table)統計每種數字出現之次數,然後將所有出現次數取它們的最大公因數 D(Greatest Common Divisor,GCD)。

因為是所有數字種類數量之公因數,所以至少存在一種方式可以將紙牌分做若干個群組使得每個群組恰好 D 張牌且數字都一樣。所以當 D ≧ 2 時,即是題目所求的 X ≧ 2 之情況,所以回傳真;反之,回傳假。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
30 巴幣: 0

創作回應

相關創作

更多創作