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

[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. 1 <= text.length <= 1000
  2. text consists of lowercase English letters.

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

示例 1:

输入:"cdadabcc"
输出:"adbc"

示例 2:

输入:"abcd"
输出:"abcd"

示例 3:

输入:"ecbacba"
输出:"eacb"

示例 4:

输入:"leetcode"
输出:"letcod" 

提示:

  1. 1 <= text.length <= 1000
  2. 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 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
SwiftArraycopy的线程安全问题发布时间:2022-07-13
下一篇:
Swift写的超级简单的五子棋发布时间: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