838.推多米诺.md

838.推多米诺

/*
 * @lc app=leetcode.cn id=838 lang=typescript
 *
 * [838] 推多米诺
 */

// @lc code=start
function pushDominoes(dominoes: string): string {}
// @lc code=end

解法 1: 统计左右距离

统计左边向右倒以及右边向左倒的牌到当前位置的距离,哪边距离近,则当前位置会优先被那边推倒,如果距离相等,则保持不变

function pushDominoes(dominoes: string): string {
  const n = dominoes.length,
    r: number[] = new Array(n).fill(0),
    l: number[] = new Array(n).fill(0)

  let prer = Infinity,
    prel = Infinity
  for (let i = 0; i < n; i++) {
    if (dominoes[i] === 'R') prer = i
    else if (dominoes[i] === 'L') prer = Infinity
    r[i] = prer === Infinity ? Infinity : i - prer

    const j = n - 1 - i
    if (dominoes[j] === 'L') prel = j
    else if (dominoes[j] === 'R') prel = Infinity
    l[j] = prel === Infinity ? Infinity : prel - j
  }

  let res: string[] = []
  for (let i = 0; i < r.length; i++) {
    res.push(l[i] > r[i] ? 'R' : l[i] < r[i] ? 'L' : '.')
  }
  return res.join('')
}

Case

test.each([
  { input: { dominoes: 'RR.L' }, output: 'RR.L' },
  { input: { dominoes: '.L.R...LR..L..' }, output: 'LL.RR.LLRRLL..' },
])('input: dominoes = $input.dominoes', ({ input: { dominoes }, output }) => {
  expect(pushDominoes(dominoes)).toEqual(output)
})