跳到主要内容

838.推多米诺

链接:838.推多米诺
难度:Medium
标签:双指针、字符串、动态规划
简介:返回表示最终状态的字符串。

题解 1 - cpp

  • 编辑时间:2022-02-21
  • 执行用时:80ms
  • 内存消耗:15.3MB
  • 编程语言:cpp
  • 解法介绍:dp, 统计每秒钟的状态进行推导。
class Solution {
public:
string pushDominoes(string dominoes) {
int n = dominoes.size(), change, cnt = 0;
string dp[2];
dp[0] = dominoes;
do {
change = 0;
int idx = cnt & 1, nidx = (cnt + 1) & 1;
dp[nidx] = dp[idx];
for (int i = 0; i < n; i++) {
if (dp[idx][i] == '.') {
if (i > 0 && dp[idx][i - 1] == 'R' && i < n - 1 &&
dp[idx][i + 1] == 'L')
dp[idx][i] = '.';
else if (i > 0 && dp[idx][i - 1] == 'R') {
change = 1;
dp[nidx][i] = 'R';
} else if (i < n - 1 && dp[idx][i + 1] == 'L') {
change = 1;
dp[nidx][i] = 'L';
} else if (i > 0 && dp[idx][i - 1] == '.' ||
i < n - 1 && dp[idx][i + 1] == '.')
dp[idx][i] = '.';
}
}
cnt++;
} while (change);
return dp[cnt & 1];
}
};