题目描述

在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。

返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

样例

图片示例

示例 1：

输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
输出：2
解释：
图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
示例 2：

输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
输出：-1
解释：
在这种情况下，不可能旋转多米诺牌使一行的值相等。


提示：

1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000

算法1

(直接递推) $O(n)$

假设A、B的第一个数分别是a、b,如果最后能旋转成功，那么最少的旋转次数只可能是以下四种情况之一：
1. 将A中所有不是a的都变成了a;
2. 将A中所有不是b的都变成了b;
3. 将B中所有不是b的都变成了b;
4. 将B中所有不是a的都变成了a。
只需要取上述四种情况中能够实现的最小次数即可。

时间复杂度分析：每个多米诺骨牌被遍历了常数次，所以时间复杂度是$O(n)$

Python3 代码

class Solution:
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        l = len(A)
        ans = -1
        flg = A[0]
        cnt1 = 0
        cnt2 = 1 if A[0] != B[0] else 0
        pA = True
        for i in range(1, l):
            if A[i] == flg and B[i] != flg:
                cnt2 += 1
            elif B[i] == flg and A[i] != flg:
                cnt1 += 1
            elif A[i] != flg and B[i] != flg:
                pA = False
                break
        if pA:
            ans = min(cnt1, cnt2)
        flg = B[0]
        cnt1 = 0
        cnt2 = 1 if A[0] != B[0] else 0
        pB = True
        for i in range(1, l):
            if B[i] == flg and A[i] != flg:
                cnt2 += 1
            elif A[i] == flg and B[i] != flg:
                cnt1 += 1
            elif A[i] != flg and B[i] != flg:
                pB = False
                break
        if pB:
            ans = min(cnt1, cnt2)
        return ans

算法2

(直接枚举) $O(n)$

由于多米诺骨牌的点数只有1到6，所以我们直接枚举翻转之后对齐的点数就可以了。

时间复杂度分析：多米诺骨牌被遍历了6次，所以时间复杂度为$O(n)$

Python3 代码

class Solution(object):
    def minDominoRotations(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        n = len(A)
        ans = float('inf')
        for i in range(6):
            a = 0
            b = 0
            for j in range(n):
                if A[j] == i:
                    if B[j] != i:
                        b += 1
                if B[j] == i:
                    if A[j] != i:
                        a += 1
                if A[j] != i and B[j] != i:
                    a = b = float('inf')
                    break
            ans = min(ans, a ,b)

        if ans == float('inf'):
            return -1