• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. S will have length in range [1, 500].
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
关于Swift的闭包(closure)以及其在可选(Optional)类型中的应用 ...发布时间:2022-07-13
下一篇:
Swift#ApplePay集成发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap