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

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

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

S has length at most 50.
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]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

说明:

S 的长度不超过 50。
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 }