月度归档： 2025 年 5 月

目标

在一排多米诺骨牌中，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^4
• bottoms.length == tops.length
• 1 <= tops[i], bottoms[i] <= 6

思路

有两个长度相同的数组，数组元素 1 ~ 6，每次操作可以交换这两个数组相同下标的元素值，求使其中任意数组的元素值全部相同所需的最小操作数。

由于最终需要任一数组的元素值完全相同，不是 tops[0] 就是 bottoms[0]。分别计算将这两个数组变成这两个值的最小操作数即可。

代码

/**
 * @date 2025-05-03 20:46
 */
public class MinDominoRotations1007 {

    public int minDominoRotations_v2(int[] tops, int[] bottoms) {
        int res = Math.min(ops(tops, bottoms, tops[0]), ops(tops, bottoms, bottoms[0]));
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public int ops(int[] tops, int[] bottoms, int target) {
        int topCnt = 0;
        int bottomCnt = 0;
        for (int i = 0; i < tops.length; i++) {
            if (target != tops[i] && target != bottoms[i]) {
                return Integer.MAX_VALUE;
            }
            if (target != tops[i]) {
                topCnt++;
            } else if (target != bottoms[i]) {
                bottomCnt++;
            }
        }
        return Math.min(topCnt, bottomCnt);
    }

}

性能

目标

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

• dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
• dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
• dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：

输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."

说明：

• n == dominoes.length
• 1 <= n <= 10^5
• dominoes[i] 为 'L'、'R' 或 '.'

思路

已知多米诺骨牌的初始状态，求最终状态。

分类讨论，使用变量 prevIndex 记录前一个非 '.' 的位置，根据 prev = chars[prevIndex] 与 cur = chars[curIndex] 来填充 (prevIndex, curIndex)。

• prev = 'R'，cur = 'R'，填充为 'R'
• prev = 'R'，cur = 'L'，前半部分填充 'R'，后半部分填充 'L'
• prev = 'L'，cur = 'L'，填充为 'L'
• prev = 'L'，cur = 'R'，保持不变

代码

/**
 * @date 2025-05-02 22:06
 */
public class PushDominoes838 {

    public String pushDominoes(String dominoes) {
        char[] chars = dominoes.toCharArray();
        int n = chars.length;
        int prevIndex = -1;
        char prev = 'L';
        char[] res = dominoes.toCharArray();
        for (int curIndex = 0; curIndex <= n; curIndex++) {
            char cur;
            if (curIndex == n) {
                cur = 'R';
            } else {
                cur = chars[curIndex];
            }
            if (prev == 'R' && cur == 'L') {
                int cnt = (curIndex - 1 - prevIndex) / 2;
                Arrays.fill(res, prevIndex + 1, prevIndex + cnt + 1, 'R');
                Arrays.fill(res, curIndex - cnt, curIndex, 'L');
            } else if (prev == cur) {
                Arrays.fill(res, prevIndex + 1, curIndex, cur);
            }
            if (cur != '.') {
                prevIndex = curIndex;
                prev = cur;
            }
        }
        return new String(res);
    }

}

性能