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
解释：
第一个图形代表了给定的多米诺骨牌：旋转前。
如果我们旋转第二个和第四个多米诺，我们可以让上面一行的所有值都等于 2，如第二个图形所示。

示例 2：

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

提示：

  • 2 <= tops.length <= 2 * 10^4
  • bottoms.length == tops.length
  • 1 <= tops[i], bottoms[i] <= 6

解题思路

这道题的关键是理解：只有某个数字能够出现在每个多米诺骨牌的上面或下面时，才可能形成统一的一行。

思路分析：

首先观察约束条件：如果要让所有的 tops 或 bottoms 都变成同一个值 x，那么对于每个位置 i，要么 tops[i] == x，要么 bottoms[i] == x。这意味着 x 必须在每个多米诺骨牌上都出现。

因此我们只需要考虑两个候选值：tops[0] 和 bottoms[0]。因为如果存在解，那么目标值一定是第一个多米诺骨牌上的某个数字。

算法步骤：

  1. 检查 tops[0] 是否可以作为目标值：

    • 遍历所有位置，如果某个位置既不在 tops 也不在 bottoms 中包含这个值，则不可行
    • 否则计算需要的旋转次数

  2. 同样检查 bottoms[0] 是否可以作为目标值

  3. 返回两种方案中的最小旋转次数，如果都不可行则返回 -1

时间复杂度： O(n)，需要遍历数组 空间复杂度： O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int n = tops.size();
        
        auto check = [&](int target) -> int {
            int rotations = 0;
            for (int i = 0; i < n; i++) {
                if (tops[i] != target && bottoms[i] != target) {
                    return -1; // 无法形成目标值
                }
                if (tops[i] != target) {
                    rotations++; // 需要旋转
                }
            }
            return rotations;
        };
        
        // 尝试让所有tops变成tops[0]
        int result1 = check(tops[0]);
        // 尝试让所有tops变成bottoms[0]
        int result2 = check(bottoms[0]);
        
        // 也可能是让所有bottoms变成某个值，但由于对称性，
        // 让bottoms变成x等价于让tops变成x然后总数减去这个值
        auto checkBottom = [&](int target) -> int {
            int rotations = 0;
            for (int i = 0; i < n; i++) {
                if (tops[i] != target && bottoms[i] != target) {
                    return -1;
                }
                if (bottoms[i] != target) {
                    rotations++;
                }
            }
            return rotations;
        };
        
        int result3 = checkBottom(tops[0]);
        int result4 = checkBottom(bottoms[0]);
        
        vector<int> results;
        if (result1 != -1) results.push_back(result1);
        if (result2 != -1) results.push_back(result2);
        if (result3 != -1) results.push_back(result3);
        if (result4 != -1) results.push_back(result4);
        
        return results.empty() ? -1 : *min_element(results.begin(), results.end());
    }
};

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        def check(target, arr1, arr2):
            rotations = 0
            for i in range(len(tops)):
                if arr1[i] != target and arr2[i] != target:
                    return -1
                if arr1[i] != target:
                    rotations += 1
            return rotations
        
        # 尝试所有可能的情况
        results = []
        
        # 让tops全部变成tops[0]
        result1 = check(tops[0], tops, bottoms)
        if result1 != -1:
            results.append(result1)
        
        # 让tops全部变成bottoms[0]
        result2 = check(bottoms[0], tops, bottoms)
        if result2 != -1:
            results.append(result2)
        
        # 让bottoms全部变成tops[0]
        result3 = check(tops[0], bottoms, tops)
        if result3 != -1:
            results.append(result3)
        
        # 让bottoms全部变成bottoms[0]
        result4 = check(bottoms[0], bottoms, tops)
        if result4 != -1:
            results.append(result4)
        
        return min(results) if results else -1

public class Solution {
    public int MinDominoRotations(int[] tops, int[] bottoms) {
        int Check(int target, int[] arr1, int[] arr2) {
            int rotations = 0;
            for (int i = 0; i < tops.Length; i++) {
                if (arr1[i] != target && arr2[i] != target) {
                    return -1;
                }
                if (arr1[i] != target) {
                    rotations++;
                }
            }
            return rotations;
        }
        
        var results = new List<int>();
        
        // 让tops全部变成tops[0]
        int result1 = Check(tops[0], tops, bottoms);
        if (result1 != -1) results.Add(result1);
        
        // 让tops全部变成bottoms[0]
        int result2 = Check(bottoms[0], tops, bottoms);
        if (result2 != -1) results.Add(result2);
        
        // 让bottoms全部变成tops[0]
        int result3 = Check(tops[0], bottoms, tops);
        if (result3 != -1) results.Add(result3);
        
        // 让bottoms全部变成bottoms[0]
        int result4 = Check(bottoms[0], bottoms, tops);
        if (result4 != -1) results.Add(result4);
        
        return results.Count == 0 ? -1 : results.Min();
    }
}

/**
 * @param {number[]} tops
 * @param {number[]} bottoms
 * @return {number}
 */
var minDominoRotations = function(tops, bottoms) {
    const n = tops.length;
    
    function check(target) {
        let topRotations = 0;
        let bottomRotations = 0;
        
        for (let i = 0; i < n; i++) {
            if (tops[i] !== target && bottoms[i] !== target) {
                return -1;
            }
            if (tops[i] !== target) {
                topRotations++;
            }
            if (bottoms[i] !== target) {
                bottomRotations++;
            }
        }
        
        return Math.min(topRotations, bottomRotations);
    }
    
    let result = check(tops[0]);
    if (result !== -1) return result;
    
    return check(bottoms[0]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(1)