点击获取AI摘要

1007. 行相等的最少多米诺旋转 M

在一排多米诺骨牌中，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

问题分析

给定两条长度相同的数组 tops 和 bottoms，表示一排多米诺骨牌的上下数字。你可以对任意一张牌做“旋转”操作（即上下数字交换位置）。目标是让 整条“上行” 或 整条“下行” 的数字都相同，求所需的最少旋转次数；如果做不到，则返回 -1。

算法思路

假设最终我们要把上行全部变成某个数字 x。那么对于第 1 张牌，它转前在上行是 tops[0]，转后可能是拿下面的 bottoms[0] 过来。

  • 如果最终目标行全是 x，第 1 张牌要么原本上面就是 x（即 tops[0] == x），要么通过旋转后上面成为 bottoms[0] == x。
  • 因此，唯一可能的候选 x 就是 { tops[0], bottoms[0] } 两个值之一。
  • 其它任何值作为目标，都不可能同时兼顾第 1 张牌。

时间复杂度

时间复杂度：O(n)O(n)，其中 nn 是多米诺数量。至多对两个候选各做一次「线性遍历」。

空间复杂度：O(1)O(1)，只用了常数级额外变量（两个计数器和一个候选集合）。

代码分解

  1. 确定候选目标值
    只可能让最终整行相同的值是第一张牌上或下的数字，记为 x1 = tops[0]、x2 = bottoms[0]。

  2. 对每个候选值 x，遍历整排牌

    • 用两个计数器 rot_top 和 rot_bot 分别记录：
      • rot_top：若想让 上行tops 全部变为 x，需要旋转的次数；
      • rot_bot：若想让 下行bottoms 全部变为 x，需要旋转的次数。
    • 遍历索引 i，对每一张牌：
      • 若 tops[i]≠x 且 bottoms[i]≠x，说明这张牌无论如何（原地或旋转）都无法在上行或下行出现 x，立即返回不可行（记为无穷大，最后结果取最小会被过滤）。
      • 否则：
        • 想让上行变成 x：如果 tops[i]≠x，则必须旋转这一张，令 rot_top++。
        • 想让下行变成 x：如果 bottoms[i]≠x，则必须旋转这一张，令 rot_bot++。

  3. 取两条方案中的最小值

    • 对候选 x1、x2 分别计算后（要么把上行全换成 x，需要 rot_top 次旋转；
      要么把下行全换成 x，需要 rot_bot 次旋转），
    • 答案为其中较小的旋转次数；
    • 若都是无穷大，则返回 -1。

  4. 小结

    1. 从 { tops[0], bottoms[0] } 中拿到至多两个候选 x。
    2. 对每个候选值调用上面“检查并计数”逻辑，得到一个旋转次数（或“无解”标记）。
    3. 在这两个结果中取最小，若都是“无解”，则返回 -1，否则返回该最小值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from typing import List

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        # 内部函数：给定目标 x，返回让上行或下行全为 x 的最少旋转次数
        # 如果无解，则返回 float('inf')
        def check(x: int) -> int:
            rot_top = 0   # 让 tops 全为 x，需要的旋转次数
            rot_bot = 0   # 让 bottoms 全为 x，需要的旋转次数

            for t, b in zip(tops, bottoms):
                # 如果这张牌两面都不是 x，就不可能通过任何旋转获得 x
                if t != x and b != x:
                    return float('inf')  # 无解

                # 若上面不是 x，则必须旋转一次
                if t != x:
                    rot_top += 1
                # 若下面不是 x，则必须旋转一次
                if b != x:
                    rot_bot += 1

            # 返回两种方案的较小旋转次数
            return min(rot_top, rot_bot)

        # 仅需检查前第一张牌的两个面
        candidates = {tops[0], bottoms[0]}
        ans = float('inf')

        # 分别试每个候选值
        for x in candidates:
            ans = min(ans, check(x))

        # 若仍是无穷，说明两个候选都无解
        return -1 if ans == float('inf') else ans

以 tops = [2,1,2,4,2,2]，bottoms = [5,2,6,2,3,2] 为例：

  • 候选集合：{ 2, 5 }

试 x = 2

i tops[i] bottoms[i] tops[i]==2? bottoms[i]==2? rot_top 增量 rot_bot 增量
0 2 5 是 否 0 1
1 1 2 否 是 1 0
2 2 6 是 否 0 1
3 4 2 否 是 1 0
4 2 3 是 否 0 1
5 2 2 是 是 0 0
合计 2 3

试 x = 5

检查到 tops[1]=1 且 bottoms[1]=2 都不是 5，立即判定无解（记作 ∞）。

最终在 {2, ∞} 中取最小，就是 2。