行相等的最少多米诺旋转 图解题解

两行多米诺，要让某一行的点数全相同

给两个等长数组 tops 和 bottoms，tops[i] 是第 i 列上面的点数，bottoms[i] 是下面的点数。每次操作能把某一列翻过来（上下点数对调），问最少翻几列，能让上行或下行全相同；做不到返回 -1。题面给 tops=[2,1,2,4,2,2]、bottoms=[5,2,6,2,3,2]，答案是 2；若像 tops=[3,5,1,2,3]、bottoms=[3,6,3,3,4] 没有数盖得住每一列，就返回 -1；而 tops=[1,1,1] 上行本就全是 1，一次不用翻，返回 0。

要统一成哪个数，难道 1 到 6 挨个试

点数就 1 到 6 六种，一个笨办法是拿每个数轮流当目标 x，扫一遍全列数需要翻几列，六个候选挑翻得最少的。这能算出答案，但多数候选一上手就没戏、白扫一趟，得先看清哪些 x 不可能成。

能成的目标值，只可能是第一列的两个数

盯住第 0 列：上是 2、下是 5。整行若要全变成 x，第 0 列也必须出得了 x——要么上面本就是 x，要么翻过来让下面的 x 顶上去。可这列只有 2 和 5，x 就只能是 2 或 5，别的值第 0 列出不来、整行凑不齐。六选一坍缩成二选一：把 x=tops[0] 和 x=bottoms[0] 各验一遍，谁翻得少取谁，都不行才返回 -1。

定住一个候选 x，上行下行各要翻几列

验候选 x 时，top、bottom 两个计数器都从 0 起，分别记「上行全变成 x 要翻几列」和「下行全变成 x 要翻几列」。逐列看，只要上或下有一个是 x 就有救——上面已是 x 则 top 不动、否则加 1，下面已是 x 则 bottom 不动、否则加 1。某列上下都不是 x，候选当场作废。走完全列，min(top, bottom) 就是 x 的代价。

x=2 和 x=5 各要数几张翻转

先试 x=2。第 0 列上 2 下 5，下行要翻，top=0、bottom=1；第 1 列上 1 下 2，上行要翻，top=1、bottom=1；第 2 列上 2 下 6，下行翻，top=1、bottom=2；第 3 列上 4 下 2，上行翻，top=2、bottom=2；第 4 列上 2 下 3，下行翻，top=2、bottom=3；第 5 列上下都是 2，两边不动，top=2、bottom=3，全列过关，min(2,3)=2。

再试 x=5。第 0 列上 2 下 5，上面要翻，top=1、bottom=0；到第 1 列上 1 下 2 都不是 5，这列出不来 5，候选 5 作废。两候选里 x=2 要 2 张、x=5 灭，答案就是 2。

把 -1 当成 0，或只算半边账

枚举 1 到 6 每个点数当候选纯属白费，第 0 列出不了的值整行都出不来，锁死成两个候选就够。同一个 x 若只数上行、忘了下行，可能上行翻 3 列而下行只翻 1 列，更省的那半就漏了。某列上下都不是 x 时把无解写成返回 0 也不对：0 是本来就相同、-1 是根本做不到，两者反着来。全程最多两个候选各扫一遍 n 列，共 2n 次，时间 O(n)，空间 O(1)。

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 ans

C++

#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);
    }
}