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

[Swift]LeetCode761.特殊的二进制序列|SpecialBinaryString

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Special binary strings are binary strings with the following two properties:

  • The number of 0's is equal to the number of 1's.
  • Every prefix of the binary string has at least as many 1's as 0's.

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them.(Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

Example 1:

Input: S = "11011000"
Output: "11100100"
Explanation:
The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Note:

  1. S has length at most 50.
  2. S is guaranteed to be a special binary string as defined above.

特殊的二进制序列是具有以下两个性质的二进制序列:

  • 0 的数量与 1 的数量相等。
  • 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S,以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串,然后将它们交换。(两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后,交换后的字符串按照字典序排列的最大的结果是什么?

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" (在S[1]出现) 和 "1100" (在S[3]出现)进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

说明:

  1. S 的长度不超过 50
  2. S 保证为一个满足上述定义的特殊 的二进制序列。

Runtime: 8 ms
Memory Usage: 19.9 MB
 1 class Solution {
 2     func makeLargestSpecial(_ S: String) -> String {
 3         var cnt:Int = 0
 4         var i:Int = 0
 5         var v:[String] = [String]()
 6         var res:String = String()
 7         for j in 0..<S.count
 8         {
 9             cnt += (S[j] == "1") ? 1 : -1
10             if cnt == 0
11             {
12                 v.append("1" + makeLargestSpecial(S.subString(i + 1, j - i - 1)) + "0");
13                 i = j + 1
14             }
15         }
16         v = v.sorted(by:>)
17         for i in 0..<v.count
18         {
19             res += v[i]
20         }
21         return res
22     }
23 }
24 
25 extension String {
26     //subscript函数可以检索数组中的值
27     //直接按照索引方式截取指定索引的字符
28     subscript (_ i: Int) -> Character {
29         //读取字符
30         get {return self[index(startIndex, offsetBy: i)]}
31     }
32     
33     // 截取字符串:指定索引和字符数
34     // - begin: 开始截取处索引
35     // - count: 截取的字符数量
36     func subString(_ begin:Int,_ count:Int) -> String {
37         let start = self.index(self.startIndex, offsetBy: max(0, begin))
38         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
39         return String(self[start..<end]) 
40     }
41     
42 }

12ms

 1 class Solution {    
 2     func makeLargestSpecial(_ S: String) -> String {
 3         if (S.count == 0) {return S}
 4         var cnt = 0, i = 0
 5         var S = Array(S)
 6         var v = [String]()
 7         var res = ""
 8         for j in 0 ..< S.count {
 9             cnt += (S[j] == "1" ? 1 : -1)
10             if cnt == 0 {
11                 if (i + 1 <= j) {
12                     let tempStr = "1" + makeLargestSpecial(String(S[i + 1 ..< j])) + "0"
13                     v.append(tempStr)
14                     i = j + 1 
15                 }
16             }
17         }    
18         v.sort{$0 > $1}
19         for i in 0 ..< v.count {
20             res += v[i]
21         }
22         return res  
23     }
24 }

16ms

 1 class Solution {
 2     func makeLargestSpecial(_ str: String) -> String {
 3         var count = 0
 4         var i = 0
 5 
 6         var strings = [String]()
 7 
 8         for j in 0..<str.count {
 9             if str[j] == "1" {
10                 count += 1
11             } else {
12                 count -= 1
13             }
14 
15             if count == 0 {
16                 strings.append("1\(makeLargestSpecial(str[i + 1, j]))0")
17                 i = j + 1
18             }
19         }
20 
21         strings.sort { $0 > $1 }
22         return strings.joined()
23     }
24 }
25 
26 extension String {
27     subscript (i: Int) -> Character {
28         return self[index(startIndex, offsetBy: i)]
29     }
30 
31     subscript (start: Int, end: Int) -> String {
32         let s = self.index(self.startIndex, offsetBy: start)
33         let e = self.index(self.startIndex, offsetBy: end)
34 
35         return String(self[s...e])
36     }
37 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift4.0复习闭包发布时间:2022-07-13
下一篇:
[Swift]LeetCode1130.叶值的最小代价生成树|MinimumCostTreeFromLeafValues发布时间: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