题目：推多米诺

  • 一行中有N张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
  • 在开始时，我们同时把一些多米诺骨牌向左或向右推。
  • image
    image
  • 每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
  • 同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
  • 如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
  • 就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
  • 给定表示初始状态的字符串 “S” 。如果第 i 张多米诺骨牌被推向左边，则S[i] = 'L'；如果第 i 张多米诺骨牌被推向右边，则S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则S[i] = '.'。
  • 返回表示最终状态的字符串。
示例 1：
输入：".L.R...LR..L.."
输出："LL.RR.LLRRLL.."
示例 2：
输入："RR.L"
输出："RR.L"
说明：第一张多米诺骨牌没有给第二张施加额外的力。
提示：
  • 0 <= N <= 10^5
  • 表示多米诺骨牌状态的字符串只含有 ‘L’，’R’; 以及 ‘.’;

来源：力扣（LeetCode）第838题

链接：https://leetcode-cn.com/problems/push-dominoes

分析：

  • 首先这道题只有’L’ ‘R’ ‘.’ 这三个值，一开始没想到怎么用动态规划
  • 然后想着想着灵光一闪，发现我只要把R变为1，L变为-1，.变为0，就可以使用dp来求解了。
  • 第四行我们先开辟一个和字符串长度一样的dp数组，状态就是当前的位置，值是当前连续的次数。
  • 就是从本来就为L或R的那个数开始，你是第几个倒的。比如有一个’R’,它的右边为2，再右边为3，以此类推。
  • 5-8行为base case，本来就会倒的肯定是1，我们姑且把他们叫做源头，源头如果往旁边移动，则源头的值就变为移到的那个值。
  • 9-21行为解题的主要部分，我们分几种情况
  • 第10行为遍历到源头为R的时候，即dp对应的索引的值大于0，我们判断下一个元素的情况。
  • 只有下一个为.的情况才可以连续，因为如果出现了RR的情况，依然不能连续，根据官方给出的第2个示例，一个点的左边有两个R,右边有1个L时，点不会改变。
  • 11-20行为遍历到源头为L的时候，dp[i] 小于0，我们判断上一个元素的情况。
  • 第11行由于判断源头L需要往前找，所以声明一个变量j，用于往前找。
  • 第12行和前面第10行正好相反，需要注意的是，12行最后多了一个条件，这是因为如果源头R一直向右加，加到了L，那么L应该也要向左减，可是原来可能是0的值被源头R覆盖了，所以我们要做一个判断。
  • 首先如果对于源头L,左边为0，那么可以过去，其次源头R的值比源头L的值大，我们也可以移，直到源头R和源头L的绝对值相等，那么左右两边就平衡了。
  • 不过，还有一种情况，就是中间这个点既不是源头左的，也不是源头右的。
  • 我们在13-15行做一次特殊情况的判断，如果中间有一个值不属于两个源头而是.，我们把这个值叫中间值。
  • 我们先把源头R向右推，再把源头L向左推，那么如果中间存在这个中间值，当左源头不停向左时，在接近中间点的前一个位置，中间点当前的值和它相加一定等于1，因为当前中间点被认为是右源头的。
  • 比如现在是1 2 3 4 -1,左源头往做移动，变为1 2 3 -2 -1。这时我们不能再移了，因为如果移了左右两塬头也不会平衡。因此中间的那个点一定是中间的。所以把它改为0即可。
  • 22-24行为把dp再变为String然后返回，我选择使用StringBuilder,23行用了一个嵌套的三目运算符。
  • 代码的排版可能写的不好看，主要是因为一开始写的时候没想这么多问题，后面想到的时候懒得再去整理代码了。

代码：

class Solution {
    public String pushDominoes(String dominoes) {
        int len = dominoes.length();
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            if (dominoes.charAt(i) == 'R') dp[i] = 1;
            else if (dominoes.charAt(i) == 'L') dp[i] = -1;
        }
        for (int i = 0; i < len; i++) {
            if (dp[i] > 0 &&  i + 1 < len && dp[i+1] == 0) dp[i+1] = dp[i] + 1;
            int j = i;
            while (dp[j] < 0 && j - 1 >= 0 && (dp[j-1] == 0 || dp[j] + dp[j-1] > 0)) {
                if (dp[j] + dp[j-1] == 1) {
                    dp[j-1] = 0;
                    break;
                } else {
                    dp[j-1] = dp[j] - 1;
                }
                --j;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) sb.append(dp[i] > 0 ? 'R' : dp[i] < 0 ? 'L' : '.');
        return sb.toString();
    }
}