func pushDominoes(dominoes string) string {
n := len(dominoes)
q := []int{}
time := make([]int, n)
for i := range time {
time[i] = -1
}
force := make([][]byte, n)
for i, ch := range dominoes {
if ch != '.' {
q = append(q, i)
time[i] = 0
force[i] = append(force[i], byte(ch))
}
}
ans := bytes.Repeat([]byte{'.'}, n)
for len(q) > 0 {
i := q[0]
q = q[1:]
if len(force[i]) > 1 {
continue
}
f := force[i][0]
ans[i] = f
ni := i - 1
if f == 'R' {
ni = i + 1
}
if 0 <= ni && ni < n {
t := time[i]
if time[ni] == -1 {
q = append(q, ni)
time[ni] = t + 1
force[ni] = append(force[ni], f)
} else if time[ni] == t+1 {
force[ni] = append(force[ni], f)
}
}
}
return string(ans)
}
class Solution {
public String pushDominoes(String dominoes) {
int n = dominoes.length();
Deque<Integer> queue = new ArrayDeque<Integer>();
int[] time = new int[n];
Arrays.fill(time, -1);
List<Character>[] force = new List[n];
for (int i = 0; i < n; i++) {
force[i] = new ArrayList<Character>();
}
for (int i = 0; i < n; i++) {
char f = dominoes.charAt(i);
if (f != '.') {
queue.offer(i);
time[i] = 0;
force[i].add(f);
}
}
char[] res = new char[n];
Arrays.fill(res, '.');
while (!queue.isEmpty()) {
int i = queue.poll();
if (force[i].size() == 1) {
char f = force[i].get(0);
res[i] = f;
int ni = f == 'L' ? i - 1 : i + 1;
if (ni >= 0 && ni < n) {
int t = time[i];
if (time[ni] == -1) {
queue.offer(ni);
time[ni] = t + 1;
force[ni].add(f);
} else if (time[ni] == t + 1) {
force[ni].add(f);
}
}
}
}
return new String(res);
}
}
class Solution:
def pushDominoes(self, dominoes: str) -> str:
n = len(dominoes)
q = deque()
time = [-1] * n
force = [[] for _ in range(n)]
for i, f in enumerate(dominoes):
if f != '.':
q.append(i)
time[i] = 0
force[i].append(f)
res = ['.'] * n
while q:
i = q.popleft()
if len(force[i]) == 1:
res[i] = f = force[i][0]
ni = i - 1 if f == 'L' else i + 1
if 0 <= ni < n:
t = time[i]
if time[ni] == -1:
q.append(ni)
time[ni] = t + 1
force[ni].append(f)
elif time[ni] == t + 1:
force[ni].append(f)
return ''.join(res)
class Solution:
def pushDominoes(self, dominoes: str) -> str:
s = list(dominoes)
n, i, left = len(s), 0, 'L'
while i < n:
j = i
while j < n and s[j] == '.': # 找到一段连续的没有被推动的骨牌
j += 1
right = s[j] if j < n else 'R'
if left == right: # 方向相同，那么这些竖立骨牌也会倒向同一方向
while i < j:
s[i] = right
i += 1
elif left == 'R' and right == 'L': # 方向相对，那么就从两侧向中间倒
k = j - 1
while i < k:
s[i] = 'R'
s[k] = 'L'
i += 1
k -= 1
left = right
i = j + 1
return ''.join(s)
class Solution {
public String pushDominoes(String dominoes) {
char[] s = dominoes.toCharArray();
int n = s.length, i = 0;
char left = 'L';
while (i < n) {
int j = i;
while (j < n && s[j] == '.') { // 找到一段连续的没有被推动的骨牌
j++;
}
char right = j < n ? s[j] : 'R';
if (left == right) { // 方向相同，那么这些竖立骨牌也会倒向同一方向
while (i < j) {
s[i++] = right;
}
} else if (left == 'R' && right == 'L') { // 方向相对，那么就从两侧向中间倒
int k = j - 1;
while (i < k) {
s[i++] = 'R';
s[k--] = 'L';
}
}
left = right;
i = j + 1;
}
return new String(s);
}
}
func pushDominoes(dominoes string) string {
s := []byte(dominoes)
i, n, left := 0, len(s), byte('L')
for i < n {
j := i
for j < n && s[j] == '.' { // 找到一段连续的没有被推动的骨牌
j++
}
right := byte('R')
if j < n {
right = s[j]
}
if left == right { // 方向相同，那么这些竖立骨牌也会倒向同一方向
for i < j {
s[i] = right
i++
}
} else if left == 'R' && right == 'L' { // 方向相对，那么就从两侧向中间倒
k := j - 1
for i < k {
s[i] = 'R'
s[k] = 'L'
i++
k--
}
}
left = right
i = j + 1
}
return string(s)
}
/**
* @param {string} dominoes
* @return {string}
*/
var pushDominoes = function(dominoes) {
const s = [...dominoes];
let n = s.length, i = 0;
let left = 'L';
while (i < n) {
let j = i;
while (j < n && s[j] == '.') { // 找到一段连续的没有被推动的骨牌
j++;
}
const right = j < n ? s[j] : 'R';
if (left === right) { // 方向相同，那么这些竖立骨牌也会倒向同一方向
while (i < j) {
s[i++] = right;
}
} else if (left === 'R' && right === 'L') { // 方向相对，那么就从两侧向中间倒
let k = j - 1;
while (i < k) {
s[i++] = 'R';
s[k--] = 'L';
}
}
left = right;
i = j + 1;
}
return s.join('');
};
