大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

推多米诺骨牌。

在起始的时候，都是站着的，然后同时像某些方向推，L代表向左边推，R代表向右边推，.代表不推。

如果.左右两次的牌都撞到了自己身上，那么 . 就受力平衡所以仍然站着。

另外，很重要的一点，如果一个牌倒在了另外一个已经倒了的牌上，不会给它施加任何力。换句话说，一个推倒了的牌（"L"或"R"）只能对另一个站着的牌（"."）起作用。

解题方法

如果理解了「一个推倒了的牌只能对另一个站着的牌起作用」这句话那么基本上就能做出来这个题了，否则是做不出来的。

含义是：

  1. 两个相邻的被推倒的牌互不影响。
  2. 一张站立的牌（"."）的最终状态与离其两侧最近的 "L" 或 "R" 有关。

所以我们应该找出每个（"."）左右两边最近的两个被推倒了的牌，然后判断这两个牌是什么样子的即可，不用考虑这个区间以外的牌。因为这两张牌被推倒了，而这个区间外的其他牌不会对推倒了的牌起作用。

838. 推多米诺 - 图1

双指针

可以使用「双指针」的方式寻找 "."左右两边距离最近的被推倒的牌，形成"X....Y"型的区间。

在这两个被推倒了牌形成的区间里，根据左右两端的牌不同，有四种可能性：

  1. 'R......R' => 'RRRRRRRR'
  2. 'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
  3. 'L......R' => 'L......R'
  4. 'L......L' => 'LLLLLLLL'

使用双指针算法：

  1. l指向区间的开始（指向 "L" 或者 "R"）；
  2. r跳过所有的 "."，指向区间的结束（也指向 "L" 或者 "R"）。
  3. 此时区间的形状为 "X....Y"，判断这个区间左右端点的 "X"、 "Y"是什么，确定中间的 "."的状态。

838. 推多米诺 - 图2

代码

由于可能存在输入的dominoes的最左边和最右边都是 "."，那么形成不了"X....Y" 这样的区间。所以，下面的代码中，给dominoes最左边添加了一个 "L"，最右边添加了一个 "R"，添加的这两个虚拟的牌不会影响dominoes内部所有的牌的倒向，但是有助于我们形成区间，而且这两个添加的牌，也不会放到最终结果里。

838. 推多米诺 - 图3

在每个 for 循环中，向 res 添加结果只添加区间的 [l, r) 部分，即左闭右开。而且注意当 l = 0 的位置，是我们虚拟的牌，不要向 res 中添加。

代码如下：

class Solution(object):
    def pushDominoes(self, d):
        """
        :type dominoes: str
        :rtype: str
        """
        d = "L" + d + "R"
        res = []
        l = 0
        for r in range(1, len(d)):
            if d[r] == '.':
                continue
            mid = r - l - 1
            if l: # 虚拟的牌不放入结果
                res.append(d[l])
            if d[l] == d[r]:
                res.append(d[l] * mid)
            elif d[l] == 'L' and d[r] == 'R':
                res.append('.' * mid)
            else:
                res.append('R' * (mid // 2) + '.' * (mid % 2) + 'L' * (mid // 2))
            l = r
        return "".join(res)

class Solution {
public:
    string pushDominoes(string dominoes) {
        dominoes = "L" + dominoes + "R";
        int l = 0;
        string res = "";
        for (int r = 1; r < dominoes.size(); ++r) {
            if (dominoes[r] == '.') {
                continue;
            }
            if (l != 0) { // 虚拟的牌不放入结果
                res += dominoes[l];
            }
            int mid = r - l - 1;
            if (dominoes[l] == dominoes[r]) {
                res += string(mid, dominoes[l]);
            } else if (dominoes[l] == 'L' && dominoes[r] == 'R') {
                res += string(mid, '.');
            } else {
                res += string(mid / 2, 'R') + (mid % 2 == 1? "." : "") + string(mid / 2, 'L');
            }
            // cout << dominoes[l] << " " << dominoes[r] << " " << res << endl;
            l = r;
        }
        return res;
    }
};

class Solution {
    public String pushDominoes(String dominoes) {
        dominoes = "L" + dominoes + "R";
        int l = 0;
        StringBuilder res = new StringBuilder();
        for (int r = 1; r < dominoes.length(); ++r) {
            if (dominoes.charAt(r) == '.') {
                continue;
            }
            if (l != 0) { // 虚拟的牌不放入结果
                res.append(dominoes.charAt(l));
            }
            int mid = r - l - 1;
            if (dominoes.charAt(l) == dominoes.charAt(r)) {
                for (int i = 0; i < mid; ++i) {
                    res.append(dominoes.charAt(l));
                }
            } else if (dominoes.charAt(l) == 'L' && dominoes.charAt(r) == 'R') {
                for (int i = 0; i < mid; ++i) {
                    res.append('.');
                }
            } else {
                for (int i = 0; i < mid / 2; ++i) {
                    res.append('R');
                }
                if (mid % 2 == 1) {
                    res.append('.');
                }
                for (int i = 0; i < mid / 2; ++i) {
                    res.append('L');
                }
            }
            l = r;
        }
        return res.toString();
    }
}

参考资料：
https://leetcode.com/problems/push-dominoes/discuss/132332/C++JavaPython-Two-Pointers

时间复杂度

  • 时间复杂度：838. 推多米诺 - 图4#card=math&code=O%28N%29&id=SmOtx)，其中 838. 推多米诺 - 图5 是数组长度；
  • 空间复杂度：结果不算的话，是 838. 推多米诺 - 图6#card=math&code=O%281%29&id=Pz3XE)。

总结

  1. 重要的永远是题意！理解题意，成功大半！
  2. 不妨向我一样画个图，能清晰很多！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。