題目

1007. Minimum Domino Rotations For Equal Row

題目給定兩個矩陣tops跟bottoms，長度相同，每次翻轉可以將tops[i]跟bottoms[i]的值對調，問有沒有解能以最少次的翻轉使得tops的值全部相同，或bottoms的值全部相同

解題思路

我們可以先來思考一下值域，我們看i=0位置有兩個值為tops[0]跟bottoms[0]

如果題目要有解，那麼(0, n]位置的值都應該會有值等於tops[0]或者bottoms[0]其一

如果不是的話，則無法透過翻轉得到值

在有解的情況，我們可以列舉出共有四種可能的答案解

解用的是tops[0]的值，並翻轉至上
解用的是tops[0]的值，並翻轉至下
解用的是bottoms[0]的值，並翻轉至上
解用的是bottoms[0]的值，並翻轉至下

不會有非這四種狀況但為解的情況，所以我們只要跑四次迴圈，並取min即可得解

程式碼

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        n = len(tops)
        answer = n + 1
        for target in [tops[0], bottoms[0]]:
            num_flips = 0
            for i in range(n):
                if tops[i] == target:
                    continue
                elif bottoms[i] == target:
                    num_flips += 1
                else:
                    break
            else:
                answer = min(answer, num_flips)
        
        for target in [tops[0], bottoms[0]]:
            num_flips = 0
            for i in range(n):
                if bottoms[i] == target:
                    continue
                elif tops[i] == target:
                    num_flips += 1
                else:
                    break
            else:
                answer = min(answer, num_flips)
        
        if answer == n + 1:
            return -1
        return answer