行相等的最少多米诺旋转 图解题解
这道题到底在问什么
- 输入
- tops=[2,1,2,4,2,2], bottoms=[5,2,6,2,3,2]
- 输出
- 2 （把上行统一成 2，翻两张）
- 输入
- tops=[3,5,1,2,3], bottoms=[3,6,3,3,4]
- 输出
- -1 （没有数字能盖住每一列）
- 输入
- tops=[1,1,1], bottoms=[1,2,3]
- 输出
- 0 （上行已经全是 1）
最优解：一步一步想明白
- 3记住这套「候选只有第 0 列的两个数 → 对每个候选扫一遍数翻转」，下面每帧都在套它。
- 4先看第 0 列：上是 2、下是 5。整行要统一成 x，第 0 列必须出得了 x，所以 x 只能是 2 或 5。我们先试 x = 2。
- 5开扫候选 x=2：用 top 记「想统一上行需翻几张」，bottom 记「想统一下行需翻几张」，两个都从 0 开始。
- 6看第 0 列：上 2、下 5。只要上或下里有一个是 2，这列就有救。
- 7第 0 列：上是 2、下是 5：上行不用翻；若想让下行变 2，这列得翻一张（bottom+1）。 累计 top=0、bottom=1。
- 8看第 1 列：上 1、下 2。只要上或下里有一个是 2，这列就有救。
- 9第 1 列：上是 1（不是 2），但下是 2：若想让上行变 2，这列得翻一张（top+1）；下行本就是 2，下行不用翻。 累计 top=1、bottom=1。
- 10看第 2 列：上 2、下 6。只要上或下里有一个是 2，这列就有救。
- 11第 2 列：上是 2、下是 6：上行不用翻；若想让下行变 2，这列得翻一张（bottom+1）。 累计 top=1、bottom=2。
- 12看第 3 列：上 4、下 2。只要上或下里有一个是 2，这列就有救。
- 13第 3 列：上是 4（不是 2），但下是 2：若想让上行变 2，这列得翻一张（top+1）；下行本就是 2，下行不用翻。 累计 top=2、bottom=2。
- 14看第 4 列：上 2、下 3。只要上或下里有一个是 2，这列就有救。
- 15第 4 列：上是 2、下是 3：上行不用翻；若想让下行变 2，这列得翻一张（bottom+1）。 累计 top=2、bottom=3。
- 16看第 5 列：上 2、下 2。只要上或下里有一个是 2，这列就有救。
- 17第 5 列：上下都是 2，怎么放都行，两边都不用翻。 累计 top=2、bottom=3。
- 18候选 x=2 全列都过关。凑上行要翻 2 张、凑下行要翻 3 张，取较小的 → 2 张。这就是 x=2 的代价。
- 19别忘了还有第二个候选：把整行统一成下行第 0 个的值 x=5。计数器清零，从第 0 列重新扫。
- 20候选 5：看第 0 列，上 2、下 5。这一列里有没有 5？
- 21第 0 列有 5，本列过关。累计 top=1、bottom=0。
- 22候选 5：看第 1 列，上 1、下 2。这一列里有没有 5？
- 23第 1 列上 1、下 2，两个都不是 5：无论翻不翻，这列都出不来 5。候选 5 当场出局（红色那列卡死）。
- 24两个候选里：x=2 要 2 张，x=5 出局。取能成的最小值 → 答案 2。若两个候选都出局，则返回 -1。
⚠️ 容易写错的地方
✗ 错：枚举 1 到 6 所有点数当候选
✓ 对：候选只可能是 tops[0] 或 bottoms[0]
第 0 列出不了 x，整行就不可能全是 x，其它值不用试
✗ 错：只算「上行变 x」忘了「下行变 x」
✓ 对：同一个 x 分别算 top 与 bottom 取最小
统一上行和统一下行翻的张数不同，必须都算
✗ 错：某列上下都不是 x 还继续算，或无解返回 0
✓ 对：该列立即判候选无解；两候选都无解才返回 -1
0 是本就相同，-1 是做不到，含义完全不同
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
def check(x):
top = bottom = 0
for a, b in zip(tops, bottoms):
if a != x and b != x:
return 10**9
if a != x:
top += 1
if b != x:
bottom += 1
return min(top, bottom)
ans = min(check(tops[0]), check(bottoms[0]))
return -1 if ans == 10**9 else ansC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
auto check = [&](int x) {
int top = 0, bottom = 0;
for (int i = 0; i < (int)tops.size(); ++i) {
if (tops[i] != x && bottoms[i] != x) return 1000000000;
if (tops[i] != x) top++;
if (bottoms[i] != x) bottom++;
}
return min(top, bottom);
};
int ans = min(check(tops[0]), check(bottoms[0]));
return ans == 1000000000 ? -1 : ans;
}
};Java
import java.util.*;
class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int ans = Math.min(check(tops, bottoms, tops[0]), check(tops, bottoms, bottoms[0]));
return ans >= 1_000_000_000 ? -1 : ans;
}
private int check(int[] tops, int[] bottoms, int x) {
int top = 0, bottom = 0;
for (int i = 0; i < tops.length; i++) {
if (tops[i] != x && bottoms[i] != x) return 1_000_000_000;
if (tops[i] != x) top++;
if (bottoms[i] != x) bottom++;
}
return Math.min(top, bottom);
}
}复杂度
时间
O(n)
最多两个候选，每个扫一遍 n 列，共 2n
空间
O(1)
只用 top、bottom 几个计数器
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 行相等的最少多米诺旋转 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果只试 tops[0] 一个候选，会漏答案吗？+
会。可能存在一个 x，它在第 0 列只出现在下面（即 x = bottoms[0] ≠ tops[0]），统一成它才最优甚至才可行。所以必须把 tops[0] 与 bottoms[0] 两个候选都试一遍取最优。
为什么用「极大值」当无解标记，而不是直接 return -1？+
为了让 check 的返回值能统一参与 min 比较：无解的候选返回一个大到不可能被选中的数，主函数对两个候选取 min 后，再判断结果是不是仍等于这个极大值，是则说明两个候选都无解，返回 -1。这样逻辑更干净，不用在 check 里区分多种返回类型。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 行相等的最少多米诺旋转 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。