LeetCode 1007 行相等的最少多米諾旋轉
原題英文：Minimum Domino Rotations For Equal Row
難度：中等 | 標簽：數組、貪心
1?題目重述
給定兩行長度相同的多米諾骨牌：
tops[i]表示第?i?張骨牌上面的數字；bottoms[i]表示第?i?張骨牌下面的數字。
你可以任選一些骨牌把它們翻轉（即交換這一張牌的上下數字）。
請返回 最少需要翻轉多少次，才能讓 上面一行全部相等 或 下面一行全部相等。
如果無論怎么翻也做不到，返回 -1。
2?解題思路
2.1 關鍵觀察
-
候選數字只有 2 個
假設最終能讓某一行全部等于x，那么x必定出現在第一張牌的上面或下面。
因此我們只需要檢驗tops[0]和bottoms[0]這兩個數字即可。 -
一次掃描即可統計旋轉次數
對于候選數x，我們同時統計：rotateTop——讓 上排 都變成x需要翻多少次；rotateBottom——讓 下排 都變成x需要翻多少次。
遍歷時若發現某張牌兩面都不是x，說明x不可能完成統一，直接失敗即可。
-
答案 = 這兩個候選數字的最小可行翻轉數
若兩個候選都失敗，則返回-1。
2.2 時間復雜度
我們只掃描兩遍數組，時間 O(n)，空間 O(1)。
3?常見坑點
| 坑 | 說明 |
|---|---|
| 把整條數組與數字比較 | bottoms == b 永遠為 False，正確寫法應為 bottoms[i] == b |
| 忘記處理 0 次翻轉 | if tmp: 會把 tmp == 0 的有效解過濾掉，應直接比較最小值 |
| 發現失敗仍更新答案 | 一旦遇到兩面都不是候選數，應立即 return 而不是繼續用臨時統計結果更新全局答案 |
4?AC 代碼（Python 3）
from typing import Listclass Solution:def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:def check(x: int) -> int:""" 返回讓某一行全變成 x 的最小翻轉數；若不可行返回 inf """rot_top = rot_bot = 0for t, b in zip(tops, bottoms):if t != x and b != x: # 這張牌兩面都不是 x，不可行return float('inf')if t != x: # 讓上排 = x 需翻一次rot_top += 1if b != x: # 讓下排 = x 需翻一次rot_bot += 1return min(rot_top, rot_bot)cand = {tops[0], bottoms[0]} # 只需檢驗這兩個數ans = min(check(c) for c in cand)return -1 if ans == float('inf') else ans
5?個人踩坑記錄
原始嘗試（WA 78/84）：
elif bottoms==b: # 我把整個列表跟數字比了
- Bug 1：比較對象寫錯導致第二個候選數統計永遠失效。
- Bug 2：遇到失敗只把
tmp置零然后break，后面依舊用它去更新答案，錯誤寫入了res。 - Bug 3：
if tmp:把 0?次翻轉的情況漏掉。
修改這三處后一次 AC。
6?總結
- 看到“讓整行相等”這類題，第一步先想 “候選值能否極度縮小”；本題直接鎖定兩種數字。
- 寫多分支判斷時務必小心 索引 vs 整體，這是數組題最易犯的錯。
- 當循環里一旦出現 判定失敗條件，應及時
return，不要讓無效結果繼續污染后續邏輯。
感謝閱讀，祝早日 AK LeetCode!
By @迪小莫學AI
