Question

838. 推多米诺

English Version

题目描述

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 <= 105
• dominoes[i] 为 'L'、'R' 或 '.'

解法

方法一

class Solution:
  def pushDominoes(self, dominoes: str) -> str:
    n = len(dominoes)
    q = deque()
    time = [-1] * n
    force = defaultdict(list)
    for i, f in enumerate(dominoes):
      if f != '.':
        q.append(i)
        time[i] = 0
        force[i].append(f)
    ans = ['.'] * n
    while q:
      i = q.popleft()
      if len(force[i]) == 1:
        ans[i] = f = force[i][0]
        j = i - 1 if f == 'L' else i + 1
        if 0 <= j < n:
          t = time[i]
          if time[j] == -1:
            q.append(j)
            time[j] = t + 1
            force[j].append(f)
          elif time[j] == t + 1:
            force[j].append(f)
    return ''.join(ans)

class Solution {
  public String pushDominoes(String dominoes) {
    int n = dominoes.length();
    Deque<Integer> q = new ArrayDeque<>();
    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<>();
    }
    for (int i = 0; i < n; ++i) {
      char f = dominoes.charAt(i);
      if (f != '.') {
        q.offer(i);
        time[i] = 0;
        force[i].add(f);
      }
    }
    char[] ans = new char[n];
    Arrays.fill(ans, '.');
    while (!q.isEmpty()) {
      int i = q.poll();
      if (force[i].size() == 1) {
        ans[i] = force[i].get(0);
        char f = ans[i];
        int j = f == 'L' ? i - 1 : i + 1;
        if (j >= 0 && j < n) {
          int t = time[i];
          if (time[j] == -1) {
            q.offer(j);
            time[j] = t + 1;
            force[j].add(f);
          } else if (time[j] == t + 1) {
            force[j].add(f);
          }
        }
      }
    }
    return new String(ans);
  }
}

class Solution {
public:
  string pushDominoes(string dominoes) {
    int n = dominoes.size();
    queue<int> q;
    vector<int> time(n, -1);
    vector<string> force(n);
    for (int i = 0; i < n; i++) {
      if (dominoes[i] == '.') continue;
      q.emplace(i);
      time[i] = 0;
      force[i].push_back(dominoes[i]);
    }

    string ans(n, '.');
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      if (force[i].size() == 1) {
        char f = force[i][0];
        ans[i] = f;
        int j = (f == 'L') ? (i - 1) : (i + 1);
        if (j >= 0 && j < n) {
          int t = time[i];
          if (time[j] == -1) {
            q.emplace(j);
            time[j] = t + 1;
            force[j].push_back(f);
          } else if (time[j] == t + 1)
            force[j].push_back(f);
        }
      }
    }
    return ans;
  }
};

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, c := range dominoes {
    if c != '.' {
      q = append(q, i)
      time[i] = 0
      force[i] = append(force[i], byte(c))
    }
  }

  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
    j := i - 1
    if f == 'R' {
      j = i + 1
    }
    if 0 <= j && j < n {
      t := time[i]
      if time[j] == -1 {
        q = append(q, j)
        time[j] = t + 1
        force[j] = append(force[j], f)
      } else if time[j] == t+1 {
        force[j] = append(force[j], f)
      }
    }
  }
  return string(ans)
}

function pushDominoes(dominoes: string): string {
  const n = dominoes.length;
  const map = {
    L: -1,
    R: 1,
    '.': 0,
  };
  let ans = new Array(n).fill(0);
  let visited = new Array(n).fill(0);
  let queue = [];
  let depth = 1;
  for (let i = 0; i < n; i++) {
    let cur = map[dominoes.charAt(i)];
    if (cur) {
      queue.push(i);
      visited[i] = depth;
      ans[i] = cur;
    }
  }
  while (queue.length) {
    depth++;
    let nextLevel = [];
    for (let i of queue) {
      const dx = ans[i];
      let x = i + dx;
      if (x >= 0 && x < n && [0, depth].includes(visited[x])) {
        ans[x] += dx;
        visited[x] = depth;
        nextLevel.push(x);
      }
    }
    queue = nextLevel;
  }
  return ans
    .map(d => {
      if (!d) return '.';
      else if (d < 0) return 'L';
      else return 'R';
    })
    .join('');
}