[Swift]LeetCode1081. 不同字符的最小子序列 | Smallest Subsequence of Distinct Cha ... - Swift 教程-OStack程序员社区-中国程序员成长平台

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

[Swift]LeetCode1081. 不同字符的最小子序列 | Smallest Subsequence of Distinct Cha ...

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

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

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

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

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

Return the lexicographically smallest subsequence of text that contains all the distinct characters of textexactly once.

Example 1:

Input:

Example 2:

Input:

Example 3:

Input:

Example 4:

Input:

Note:

1 <= text.length <= 1000
text consists of lowercase English letters.

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。

示例 1：

输入："cdadabcc"
输出："adbc"

示例 2：

输入："abcd"
输出："abcd"

示例 3：

输入："ecbacba"
输出："eacb"

示例 4：

输入："leetcode"
输出："letcod"

提示：

1 <= text.length <= 1000
text 由小写英文字母组成

12ms

 1 class Solution {
 2 
 3     func smallestSubsequence(_ text: String) -> String {
 4         var cnt = [Int](repeating: 0, count: 26) , used = cnt
 5         var idx = 0, dic = [Character: Int](), chars = Array(text)
 6         _ = "abcdefghijklmnopqrstuvwxyz".map { dic[$0] = idx; idx += 1 }
 7         for ch in chars {
 8             let idx = dic[ch]!
 9             let ct = cnt[idx]
10             cnt[idx] = ct + 1
11         }
12 
13         var ans = ""
14         for ch in chars {
15             let idx = dic[ch]!
16             let ct = cnt[idx]
17             cnt[idx] = ct - 1
18 
19             let uct = used[idx]
20             used[idx] = uct + 1
21             if uct > 0 { continue }
22             while !ans.isEmpty && ans.last! > ch && cnt[dic[ans.last!]!] > 0 {
23                 used[dic[ans.last!]!] = 0
24                 ans.removeLast()
25             }
26             ans += "\(ch)"
27         }
28         return ans
29     }
30 }

Runtime: 16 ms

Memory Usage: 21.4 MB

 1 class Solution {
 2     func smallestSubsequence(_ text: String) -> String {
 3         var cnt:[Int] = [Int](repeating:0,count:26)
 4         var used:[Int] = [Int](repeating:0,count:26)
 5         var res:[Character] = [Character]()
 6         let arrText:[Character] = Array(text)
 7         let arrIndex:[Int] = Array(text).map{$0.ascii - 97}
 8         for i in arrIndex
 9         {
10             cnt[i] += 1
11         }
12         for (index,i) in arrIndex.enumerated()
13         {
14             cnt[i] -= 1
15             if used[i]++ > 0 {continue}
16             while(!res.isEmpty && (res.last!.ascii - 97) > i && cnt[res.last!.ascii - 97] > 0)
17             {
18                 used[res.last!.ascii - 97] = 0
19                 res.popLast()
20             }
21             res.append(arrText[index])
22         }
23         return String(res)
24     }
25 }
26 
27 //Character扩展
28 extension Character
29 {
30     //Character转ASCII整数值(定义小写为整数值)
31     var ascii: Int {
32         get {
33             return Int(self.unicodeScalars.first?.value ?? 0)
34         }
35     }
36 }
37 
38 /*扩展Int类，实现自增++、自减--运算符*/
39 extension Int{
40     //后缀++:先执行表达式后再自增
41     static postfix func ++(num:inout Int) -> Int {
42         //输入输出参数num
43         let temp = num
44         //num加1
45         num += 1
46         //返回加1前的数值
47         return temp
48     }
49 }