每天一道算法题——推多米诺

WenJGo

已于 2025-05-02 16:36:12 修改

阅读量1k

点赞数 24

分类专栏：我的算法记录 Java之路 C++之路文章标签：算法 leetcode 动态规划贪心算法蓝桥杯

于 2025-05-02 14:33:00 首次发布

本文链接：https://blog.csdn.net/DDDDWJDDDD/article/details/147664295

版权

我的算法记录同时被 3 个专栏收录

206 篇文章

订阅专栏

Java之路

28 篇文章

订阅专栏

C++之路

11 篇文章

订阅专栏

题目链接：838. 推多米诺 - 力扣（LeetCode）

题目描述

分析

解题思路 1：两次遍历（贪心 + 力传播）

题目链接：838. 推多米诺 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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' 或 '.'

分析

这个问题是一个经典的模拟类题目，关键在于如何高效地模拟多米诺骨牌倒下的过程。我们希望找出每个多米诺骨牌最终的状态（L、R 或 .）。下面是解决该问题的几种常见思路：

解题思路 1：两次遍历（贪心 + 力传播）

核心思想：

每张未被推倒的多米诺骨牌会受到左右最近的“力”的影响。
如果我们知道每个位置离它最近的左边的 R 和 最近的右边的 L 的距离，就可以判断它会被推向哪边。
如果两个方向的力同时作用（距离相等），则保持直立。

🔧 实现步骤：

第一次从左到右扫描：
- 记录每个位置被左边最近的 'R' 推动的时间（即距离）。
第二次从右到左扫描：
- 记录每个位置被右边最近的 'L' 推动的时间（即距离）。
综合两个方向的力决定最终状态。

📌 示例说明：

输入："RR.L"

索引0: 'R'，向右推
索引1: 'R'，向右推
索引2: '.'，受索引1的R影响，继续向右倒
索引3: 'L'

最终输出："RR.L"

✅ 解题思路 2：动态规划

🧠 核心思想：

类似于双指针，但用 DP 数组记录每个位置最近的左/右施力点的距离。
最后根据左右距离比较得出结果。

✅ 总结

方法	时间复杂度	空间复杂度	是否推荐
双遍历法	O(n)	O(n)	✅ 推荐，实现简单，效率高
BFS 法	O(n)	O(n)	✅ 推荐，逻辑清晰
动态规划	O(n)	O(n)	⭕ 可行，略复杂

解法一：动态规划

Java写法：

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        int[] leftForce = new int[n];
        int force = 0;

        // 从左向右计算右向力
        for (int i = 0; i < n; i++) {
            if (dominoes.charAt(i) == 'R') {
                force = n; // 表示很强的右向力
            } else if (dominoes.charAt(i) == 'L') {
                force = 0; // 遇到L，清除右向力
            } else {
                force = Math.max(force - 1, 0);
            }
            leftForce[i] = force;
        }

        // 从右向左计算左向力，并比较决定最终方向
        force = 0;
        StringBuilder res = new StringBuilder();

        for (int i = n - 1; i >= 0; i--) {
            if (dominoes.charAt(i) == 'L') {
                force = n;
            } else if (dominoes.charAt(i) == 'R') {
                force = 0;
            } else {
                force = Math.max(force - 1, 0);
            }

            int diff = leftForce[i] - force;
            if (diff > 0) {
                res.append('R');
            } else if (diff < 0) {
                res.append('L');
            } else {
                res.append('.');
            }
        }

        return res.reverse().toString();
    }
}

C++写法：

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string pushDominoes(std::string dominoes) {
        int n = dominoes.size();
        const int INF = n + 1;
        std::vector<int> left(n, INF), right(n, INF);

        // 从左到右计算右侧力
        int force = INF;
        for (int i = 0; i < n; ++i) {
            if (dominoes[i] == 'R') {
                force = 0;
            } else if (dominoes[i] == 'L') {
                force = INF;
            } else {
                force = force == INF ? INF : force + 1;
            }
            right[i] = force;
        }

        // 从右到左计算左侧力
        force = INF;
        for (int i = n - 1; i >= 0; --i) {
            if (dominoes[i] == 'L') {
                force = 0;
            } else if (dominoes[i] == 'R') {
                force = INF;
            } else {
                force = force == INF ? INF : force + 1;
            }
            left[i] = force;
        }

        // 构造最终结果
        for (int i = 0; i < n; ++i) {
            if (right[i] < left[i]) {
                dominoes[i] = 'R';
            } else if (left[i] < right[i]) {
                dominoes[i] = 'L';
            } else {
                dominoes[i] = '.';
            }
        }

        return dominoes;
    }
};

运行时间

时间复杂度和空间复杂度

时间复杂度: O(n)，同样地，我们也进行了三次线性扫描，分别用于初始化、从左到右计算以及从右到左计算。
空间复杂度: O(n)，使用了两个辅助数组来存储每个位置的左右力值。

解法二：双遍历（贪心 + 力传播）

Java写法：

class Solution {
    public String pushDominoes(String dominoes) {
        int n = dominoes.length();
        char[] d = dominoes.toCharArray();
        int[] rightForce = new int[n];
        int[] leftForce = new int[n];

        // 从左到右计算右边方向的力
        int force = 0;
        for (int i = 0; i < n; i++) {
            if (d[i] == 'R') {
                force = n;  // 最强向右力
            } else if (d[i] == 'L') {
                force = 0;  // 遇到L则清除向右力
            } else {
                force = Math.max(force - 1, 0);
            }
            rightForce[i] = force;
        }

        // 从右到左计算左边方向的力
        force = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (d[i] == 'L') {
                force = n;  // 最强向左力
            } else if (d[i] == 'R') {
                force = 0;  // 遇到R则清除向左力
            } else {
                force = Math.max(force - 1, 0);
            }
            leftForce[i] = force;
        }

        // 比较左右力决定结果
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (rightForce[i] > leftForce[i]) {
                res.append('R');
            } else if (rightForce[i] < leftForce[i]) {
                res.append('L');
            } else {
                res.append('.');
            }
        }

        return res.toString();
    }
}

C++写法：

#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::string pushDominoes(std::string dominoes) {
        int n = dominoes.size();
        std::vector<int> rightForce(n, 0);
        std::vector<int> leftForce(n, 0);

        // 计算右侧力
        int force = 0;
        for (int i = 0; i < n; ++i) {
            if (dominoes[i] == 'R') {
                force = n; // 强右向力
            } else if (dominoes[i] == 'L') {
                force = 0; // 清除右向力
            } else {
                force = std::max(force - 1, 0);
            }
            rightForce[i] = force;
        }

        // 计算左侧力
        force = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (dominoes[i] == 'L') {
                force = n; // 强左向力
            } else if (dominoes[i] == 'R') {
                force = 0; // 清除左向力
            } else {
                force = std::max(force - 1, 0);
            }
            leftForce[i] = force;
        }

        // 根据左右力决定最终状态
        for (int i = 0; i < n; ++i) {
            if (rightForce[i] > leftForce[i]) {
                dominoes[i] = 'R';
            } else if (leftForce[i] > rightForce[i]) {
                dominoes[i] = 'L';
            } else {
                dominoes[i] = '.';
            }
        }

        return dominoes;
    }
};