[Swift]LeetCode763.划分字母区间|PartitionLabels

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

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

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

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

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

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

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.

Runtime: 20 ms

Memory Usage: 20 MB

 1 class Solution {
 2     func partitionLabels(_ S: String) -> [Int] {
 3         var res:[Int] = [Int]()
 4         var n:Int = S.count
 5         var start:Int = 0
 6         var last:Int = 0
 7         var m:[Character:Int] = [Character:Int]()
 8         var arr:[Character] = Array(S)
 9         for i in 0..<n
10         {
11             m[arr[i]] = i
12         }
13         for i in 0..<n
14         {
15             last = max(last, m[arr[i],default:0])
16             if i == last
17             {
18                 res.append(i - start + 1)
19                 start = i + 1
20             }
21         }
22         return res
23     }
24 }

20ms

 1 class Solution {
 2 func partitionLabels(_ S: String) -> [Int] {
 3     let arr = Array(S)
 4     var dict:[Character:Int] = [:]
 5     
 6     for i in 0 ..< arr.count {
 7         dict[arr[i]] = i
 8     }
 9     
10     var result :[Int] = []
11     var temp: Int = 0
12     var index: Int = 0
13     while index < arr.count {
14         temp = dict[arr[index]]!
15         index += 1
16         while index <= temp {
17             if dict[arr[index]]! > temp {
18                 temp = dict[arr[index]]!
19             }
20             index += 1
21         }
22         result.append(temp+1 - result.reduce(0,+))
23     }
24     
25     return result
26   }
27 }

20ms

 1 class Solution {    
 2     func partitionLabels(_ S: String) -> [Int] {
 3         var stringEndDic : [Int] = Array(repeating: -1, count: 128)
 4 
 5         var idx : Int = 0
 6         for unicode in S.unicodeScalars {
 7             stringEndDic[Int(unicode.value)] = idx
 8             idx += 1
 9         }
10         
11         var begin : Int = 0
12         var end : Int = 0
13         
14         var result:[Int] = []
15         
16         idx = 0
17         for unicode in S.unicodeScalars {
18             if end < stringEndDic[Int(unicode.value)] {
19                 end = stringEndDic[Int(unicode.value)]
20             }
21             idx += 1
22             if idx > end{
23                 result.append(idx-begin)
24                 begin = idx
25                 end = idx
26             }
27         }
28         
29         return result
30     }
31 }

24ms

 1 class Solution {
 2     func partitionLabels(_ s: String) -> [Int] {
 3     var hash = Array(repeating: (-1, -1), count: 26)
 4     for (i, char) in s.unicodeScalars.enumerated() {
 5         let n = Int(char.value) - 97
 6         if hash[n].0 == -1 {
 7             hash[n] = (i, i)
 8         } else {
 9             hash[n].1 = i
10         }
11     }
12     
13     var index = 0
14     while index < hash.count {
15         if hash[index].0 == -1 {
16             hash.remove(at: index)
17         } else {
18             index += 1
19         }
20     }
21     hash.sort { $0.0 < $1.0 }
22     
23     var ans = [Int]()
24     var maxIndex = 0
25     var minIndex = 0
26     
27     for (start, end) in hash {
28         
29         if start > maxIndex {
30             ans.append(maxIndex - minIndex + 1)
31             maxIndex = end
32             minIndex = start
33         } else {
34             maxIndex = max(maxIndex, end)
35         }
36     }
37     
38     ans.append(maxIndex - minIndex + 1)
39     return ans
40     }
41 }

24ms

 1 class Solution {
 2     func partitionLabels(_ S: String) -> [Int] {
 3         let S = S.map{$0}
 4         var dict = [Character:Int]()
 5         
 6         var index = 0
 7         for char in S {
 8             dict[char] = index
 9             index += 1
10         }
11         
12         var ans = [Int]()
13         var maxIndex = 0; var tmpIndex = -1
14         index = 0
15         for char in S {
16             maxIndex = max(maxIndex, dict[char]!)
17             if (index == maxIndex) {
18                 ans.append(index - tmpIndex)
19                 tmpIndex = index
20             }
21             index += 1
22         }
23         
24         return ans
25     }
26 }

40ms

 1 class Solution {    
 2     func partitionLabels(_ S: String) -> [Int] {
 3         var dict = [String: Int]()
 4         for (index, item) in Array(S).enumerated() {
 5             dict[String(item)] = index
 6         }
 7         var returnArr = [Int]()
 8         var maxIndex = 0
 9         var anchor = 0
10         for (index, item) in Array(S).enumerated() {
11             guard let indexInDict = dict[String(item)] else {
12                 continue
13             }
14             maxIndex = max(maxIndex, indexInDict)
15             if index == maxIndex {
16                 returnArr.append(index-anchor+1)
17                 anchor = index+1
18             }
19         }
20         return returnArr
21     }
22 }