leetcode838_go_推多米诺

题目

一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。

在开始时，我们同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。

同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡，该骨牌仍然保持不变。

就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。

给定表示初始状态的字符串 "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'; 以及 '.';

解题思路分析

1、模拟；时间复杂度O(n^2)，空间复杂度O(n)

func pushDominoes(dominoes string) string {
   n := len(dominoes)
   arr := append([]byte{'L'}, dominoes...)
   arr = append(arr, 'R') // 前面补1个L，后面补1个R
   temp := make([]byte, n+2)
   for string(temp) != string(arr) { // 模拟每一秒：当没有变化的时候退出
      copy(temp, arr) // 存储之前1秒的情况
      for i := 1; i <= n; i++ {
         if arr[i] == '.' { // 当前位置为.进行判断2边情况
            // 讨论2种变的情况
            if temp[i-1] == 'R' && temp[i+1] != 'L' {
               arr[i] = 'R' // 1、左边向右边倒，右边为R或者.
            } else if temp[i+1] == 'L' && temp[i-1] != 'R' {
               arr[i] = 'L' // 2、右边向左边倒，左边为L或者.
            }
         }
      }
   }
   return string(arr[1 : n+1])
}

2、计算；时间复杂度O(n)，空间复杂度O(n)

func pushDominoes(dominoes string) string {
   n := len(dominoes)
   arr := make([]int, n)
   value := 0
   for i := 0; i < n; i++ { // 1、从左往右
      // 计算左边的受力，R=n，L=0，.的时候随距离减1
      if dominoes[i] == 'R' {
         value = n
      } else if dominoes[i] == 'L' {
         value = 0
      } else {
         value = max(0, value-1)
      }
      arr[i] = arr[i] + value
   }
   value = 0
   for i := n - 1; i >= 0; i-- { // 2、从右往左
      // 计算右边的受力，R=0，L=R，.的时候随距离减1
      if dominoes[i] == 'L' {
         value = n
      } else if dominoes[i] == 'R' {
         value = 0
      } else {
         value = max(0, value-1)
      }
      arr[i] = arr[i] - value
   }
   res := []byte(dominoes)
   for i := 0; i < n; i++ {
      // 哪边受力大，结果随哪边
      if arr[i] > 0 {
         res[i] = 'R'
      } else if arr[i] < 0 {
         res[i] = 'L'
      } else {
         res[i] = '.'
      }
   }
   return string(res)
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、模拟；时间复杂度O(n^2)，空间复杂度O(n)

func pushDominoes(dominoes string) string {
   s := ""
   for s != dominoes { // 模拟每一秒：当没有变化的时候退出
      s = dominoes
      dominoes = strings.ReplaceAll(dominoes, "R.L", "X") // 把R.L这种不变的临时替换为1个不影响的X
      dominoes = strings.ReplaceAll(dominoes, ".L", "LL") // 向左倒
      dominoes = strings.ReplaceAll(dominoes, "R.", "RR") // 向右倒
      dominoes = strings.ReplaceAll(dominoes, "X", "R.L") // 替换回来
   }
   return dominoes
}