[Swift]LeetCode942.增减字符串匹配|DIStringMatch

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

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

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

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

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

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

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]

Example 1:

Input: [0,4,1,3,2]

Example 2:

Input: [0,1,2,3]

Example 3:

Input: [3,2,0,1]

Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。

返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：

如果 S[i] == "I"，那么 A[i] < A[i+1]
如果 S[i] == "D"，那么 A[i] > A[i+1]

示例 1：

输出："IDID"
输出：[0,4,1,3,2]

示例 2：

输出："III"
输出：[0,1,2,3]

示例 3：

输出："DDI"
输出：[3,2,0,1]

提示：

1 <= S.length <= 1000
S 只包含字符 "I" 或 "D"。

68ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3       let N = S.count
 4       var min = 0
 5       var max = N
 6       
 7       var res : [Int] = []
 8       
 9       for c in S {
10         if c == "I" {
11           res.append(min)
12           min += 1
13         } else if c == "D" {
14           res.append(max)
15           max -= 1
16         }
17       }
18       assert(min == max);
19       res.append(min)
20       
21       return res
22     }
23 }

84ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3         let array = Array(0...S.count)
 4         
 5         var left = 0
 6         var right = S.count
 7         
 8         var result = [Int]()
 9         for char in S {
10             if char == "I" {
11                 result.append(array[left])
12                 left += 1
13             } else if char == "D" {
14                 result.append(array[right])
15                 right -= 1
16             }
17         }
18         result.append(array[left])
19         
20         return result
21     }
22 }

88ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3         
 4         var out:[Int] = []
 5         
 6         var i = 0
 7         var d = S.count
 8         
 9         for c in S {
10             
11             if c == "I" {
12                 
13                 out.append(i)
14                 i += 1
15                 
16             } else {
17                 out.append(d)
18                 d -= 1
19             }
20             
21         }
22         
23         if S.last! == "I" {
24              out.append(i)
25                 i += 1
26         } else {
27             out.append(d)
28                 d -= 1
29         }
30         
31         return out
32     }
33 }

120ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3         var arr:[Int] = []
 4         var min = -1, max = S.count + 1
 5         for c in S {
 6             if c == "I" {
 7                 min+=1
 8                 arr.append(min)
 9             } else {
10                 max-=1
11                 arr.append(max)
12             }
13         }
14         arr.append(min+1)
15         return arr
16     }
17 }

312ms

 1 class Solution {
 2     
 3     struct HeapElement {
 4         let idx: Int
 5         let value: Int
 6         init(_ idx: Int, _ value: Int) {
 7             self.idx = idx
 8             self.value = value
 9         }
10     }
11     
12     func diStringMatch(_ S: String) -> [Int] {
13         let N = S.count
14         var heap: [HeapElement] = [HeapElement(0,0)]
15         var prevValue = 0
16         var idx = 1
17         for ch in S {
18             if ch == "I" {
19                 prevValue += 1
20             } else {
21                 prevValue -= 1
22             }
23             heap.append(HeapElement(idx, prevValue))
24             var curInd = heap.count - 1
25             while heap[curInd].value < heap[(curInd - 1) / 2].value && curInd > 0 {
26                 let parentInd = (curInd - 1) / 2
27                 heap.swapAt(curInd, parentInd)
28                 curInd = parentInd
29             }
30             idx += 1
31         }
32         
33         var result: [Int] = Array(repeating: 0, count: N + 1)
34         prevValue = 0
35         while !heap.isEmpty {
36             heap.swapAt(0, heap.count - 1)
37             let element = heap.removeLast()
38             result[element.idx] = prevValue
39             prevValue += 1
40             var curInd = 0
41             while (2*curInd + 1 < heap.count && heap[curInd].value > heap[2*curInd + 1].value) || 
42             (2*curInd + 2 < heap.count && heap[curInd].value > heap[2*curInd + 2].value) {
43                 var childInd = 2*curInd + 1
44                 if 2*curInd + 2 < heap.count {
45                     if heap[childInd].value > heap[2*curInd + 2].value {
46                         childInd = 2*curInd + 2
47                     }
48                 }
49                 heap.swapAt(curInd, childInd)
50                 curInd = childInd
51             }
52         }
53         return result
54     }
55 }

2096ms

 1 class Solution {
 2     func diStringMatch(_ S: String) -> [Int] {
 3         var n:Int = S.count + 1
 4         var ret:[Int] = [Int](repeating: 0,count: n)
 5         var v:Int = n - 1
 6         var pre:Int = 0
 7         for i in 0..<(n - 1)
 8         {
 9             if S[i] == "D"
10             {
11                 for j in (pre...i).reversed()
12                 {
13                     ret[j] = v
14                     v -= 1
15                 }
16                 pre = i + 1
17             }
18         }
19         for j in (pre...(n - 1)).reversed()
20         {
21             ret[j] = v
22             v -= 1
23         }
24         return ret
25     }
26 }
27 
28 extension String {
29     //subscript函数可以检索数组中的值
30     //直接按照索引方式截取指定索引的字符
31     subscript (_ i: Int) -> Character {
32         //读取字符
33         get {return self[index(startIndex, offsetBy: i)]}
34     }
35 }