[Swift]LeetCode838.推多米诺|PushDominoes

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10577534.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

There are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L', 'R' and '.'

一行中有 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'; 以及 '.';

Runtime: 284 ms

Memory Usage: 20.8 MB

 1 class Solution {
 2     func pushDominoes(_ dominoes: String) -> String {
 3         var n:Int = dominoes.count
 4         var arrChar = Array(dominoes)
 5         var cnt:[Int] = [Int](repeating:0,count:n)
 6         for i in 1..<n
 7         {
 8             if arrChar[i - 1] == "R" && arrChar[i] == "."
 9             {
10                 arrChar[i] = "R"
11                 cnt[i] = cnt[i - 1] + 1
12             }
13         }
14         var cur:Int = 0
15         for i in stride(from:n - 2,through:0,by:-1)
16         {
17             if arrChar[i + 1] != "L" {continue}
18             cur = cnt[i + 1] + 1
19             if arrChar[i] == "." || cnt[i] > cur
20             {
21                 arrChar[i] = "L"
22                 cnt[i] = cur
23             }
24             else if arrChar[i] == "R" && cnt[i] == cur
25             {
26                  arrChar[i] = "."
27             }            
28         }
29         return String(arrChar)
30     }
31 }

308ms

  1 class Solution {
  2     func pushDominoes(_ dominoes: String) -> String {
  3     guard dominoes.count > 1 else{
  4         return dominoes
  5     }
  6     var dominoes = Array(dominoes)
  7     var startIndex = 0
  8     var movingIndex = 0
  9 
 10     while movingIndex < dominoes.count{
 11         if dominoes[startIndex] == "."{
 12             if dominoes[movingIndex] == "."{
 13                 movingIndex += 1
 14             }else if dominoes[movingIndex] == "L"{
 15                 pushLeft(dominoes: &dominoes, startIndex: startIndex, endIndex: movingIndex)
 16                 movingIndex += 1
 17                 startIndex = movingIndex
 18             }else{
 19                 // if dominoes[movingIndex] = right
 20                 startIndex = movingIndex
 21             }
 22         }else if dominoes[startIndex] == "L"{
 23             if dominoes[movingIndex] == "L"{
 24                 if startIndex != movingIndex{
 25                     pushLeft(dominoes: &dominoes, startIndex: startIndex, endIndex: movingIndex)
 26                     startIndex = movingIndex
 27                 }
 28                 movingIndex += 1
 29             }else if dominoes[movingIndex] == "."{
 30                 movingIndex += 1
 31             }else{
 32                 // now we R
 33                 startIndex = movingIndex
 34             }
 35         }else{
 36             // if dominoes[startIndex] = R
 37             // then what do we do
 38             if dominoes[movingIndex] == "R"{
 39                 if startIndex != movingIndex{
 40                     pushRight(dominoes: &dominoes, startIndex: startIndex, endIndex: movingIndex)
 41                     startIndex = movingIndex
 42                 }
 43                 movingIndex += 1
 44             }else if dominoes[movingIndex] == "."{
 45                 movingIndex += 1
 46             }else{
 47                 // we meet L
 48                 pushRightLeft(dominoes: &dominoes, startIndex: startIndex, endIndex: movingIndex)
 49                 movingIndex += 1
 50                 startIndex = movingIndex
 51             }
 52         }
 53     }
 54     
 55     if startIndex < movingIndex && dominoes[startIndex] == "R"{
 56         while startIndex < movingIndex{
 57             dominoes[startIndex] = "R"
 58             startIndex += 1
 59         }
 60     }
 61     
 62   
 63     return String(dominoes)
 64 }
 65 func pushLeft(dominoes : inout [Character], startIndex : Int, endIndex : Int){
 66     guard startIndex >= 0 && endIndex < dominoes.count && startIndex < endIndex else{
 67         fatalError("Index Not Correct")
 68     }
 69     var startIndex = startIndex
 70     while startIndex < endIndex{
 71         dominoes[startIndex] = "L"
 72         startIndex += 1
 73     }
 74 }
 75 
 76 func pushRight(dominoes : inout [Character], startIndex : Int, endIndex : Int){
 77     guard startIndex >= 0 && endIndex < dominoes.count && startIndex < endIndex else{
 78         fatalError("Index Not Correct")
 79     }
 80     var startIndex = startIndex
 81     while startIndex < endIndex{
 82         dominoes[startIndex] = "R"
 83         startIndex += 1
 84     }
 85 }
 86 
 87 func pushRightLeft(dominoes : inout [Character], startIndex : Int, endIndex : Int){
 88     guard startIndex >= 0 && endIndex < dominoes.count && startIndex < endIndex else{
 89         fatalError("Index Not Correct")
 90     }
 91     
 92     var startIndex = startIndex
 93     var endIndex = endIndex
 94     while startIndex < endIndex{
 95         dominoes[startIndex] = "R"
 96         dominoes[endIndex] = "L"
 97         startIndex += 1
 98         endIndex -= 1
 99     }
100   }
101 }