行相等的最少多米诺旋转

难度: Medium

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

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

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

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

示例 1：

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

示例 2：

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

提示：

2 <= tops.length <= 2 * 10⁴
bottoms.length == tops.length
1 <= tops[i], bottoms[i] <= 6

Submission

运行时间: 57 ms

内存: 16.8 MB

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        n=len(tops)
        ans=inf
        for i in range(1,7):
            a,b=0,0
            for j in range(n):
                if tops[j]!=i:
                    if bottoms[j]!=i:
                        break
                    a+=1
                if bottoms[j]!=i:
                    if tops[j]!=i:
                        break
                    b+=1
            else:
                ans=min(a,b)
        return ans if ans<inf else -1

Explain

这道题的思路是尝试使得所有多米诺骨牌的上半部分或下半部分的数字都变成相同的。因为每个多米诺骨牌的数字范围是1到6，所以我们只需要尝试这6种可能的数字。对于每一种数字，我们遍历整个多米诺骨牌数组，如果当前多米诺的上半部分不等于这个数字，就检查其下半部分是否等于这个数字，如果是，就将旋转次数加1；同理，如果下半部分不等于这个数字，就检查上半部分并相应增加旋转次数。如果遍历完整个数组后没有中断（即没有遇到无法通过旋转使某个多米诺的两部分之一等于目标数字的情况），就更新最小旋转次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        n = len(tops)  # 获取多米诺骨牌的数量
        ans = inf  # 初始化最小旋转次数为无穷大
        for i in range(1, 7):  # 尝试1到6这6个数字
            a, b = 0, 0  # 初始化两种旋转次数
            for j in range(n):  # 遍历多米诺骨牌
                if tops[j] != i:  # 检查上半部分是否等于目标数字
                    if bottoms[j] != i:  # 检查下半部分是否等于目标数字
                        break  # 无法通过旋转使得某一部分等于目标数字
                    a += 1  # 增加上半部分的旋转次数
                if bottoms[j] != i:  # 检查下半部分是否等于目标数字
                    if tops[j] != i:  # 检查上半部分是否等于目标数字
                        break  # 无法通过旋转使得某一部分等于目标数字
                    b += 1  # 增加下半部分的旋转次数
            else:  # 如果没有中断循环
                ans = min(a, b)  # 更新最小旋转次数
        return ans if ans < inf else -1  # 如果找到了合适的旋转次数，则返回最小值，否则返回-1

Explore

在检查过程中，如果遇到某个多米诺骨牌的上下部分都不等于目标数字且不能通过旋转达到目标，那么这个目标数字是无法通过旋转使得所有多米诺骨牌的上半部分或下半部分统一的。此时，继续检查剩余的多米诺骨牌是没有意义的，因为已经确定无法达成目标。因此，程序通过中断循环来避免无用的计算，提高效率。

是的，可能存在这样的情况。因为多米诺骨牌的每一半可以是1到6中的任何一个数字，对于某一个特定的数字，可能存在多米诺骨牌的上下两部分都不是这个数字，且无法通过旋转使其任一部分成为这个数字。而对于另一个数字，可能通过旋转可以实现让所有多米诺骨牌的上半部分或下半部分统一。因此，算法需要尝试所有6种可能的数字，以找到可能的最小旋转次数。

在题解中，变量`a`和`b`分别记录将多米诺骨牌上半部分或下半部分全部旋转成目标数字需要的最小旋转次数。如果在检查所有多米诺骨牌后没有中断过循环（即所有多米诺骨牌至少有一部分是目标数字或可以通过旋转成为目标数字），则说明目标数字可行。此时用`min(a, b)`更新最小旋转次数，因为我们只需要选择上半部分统一或下半部分统一的最小旋转次数。这样可以确保我们得到的是所有尝试中的最小旋转次数。

在题目的假设中，`tops`和`bottoms`数组的长度应该是相等的，因为每个多米诺骨牌都有一个上半部分和一个下半部分。如果在实际应用中遇到`tops`和`bottoms`长度不相等的情况，这通常指示着输入数据有误或不完整。在这种情况下，应当首先验证输入数据的正确性和完整性。如果确认数据错误，需要进行适当的错误处理，如抛出异常或返回错误信息，而不应继续执行旋转逻辑。