题目简介：
特殊的二进制序列是具有以下两个性质的二进制序列：
- 0 的数量与 1 的数量相等。
- 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
1
2
3
4
5
| 输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。
|
说明:
S 的长度不超过 50。S 保证为一个满足上述定义的特殊的二进制序列。
思路：
首先我们可以把”1”看成”(“，把”0”看成”)”，那么我们所需要找到的便是左括号最多的，且符合括号逻辑的字符串。
所以，我们需要遍历字符串，首先找到符合逻辑的子字符串（也就是符合括号逻辑的子字符串），然后将其降序排序，最后合并就行了。
同时，这些子串内部也可使用相同的方法进行上述操作，从而变成最大的字符串，因此需要使用递归。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
string makeLargestSpecial(string s) {
if(s.size() <= 2)
return s;
vector<string> res;
int left = 0;
int count = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '1')
count++;
else{
count--;
if(count == 0){
string temp = "1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0";
res.push_back(temp);
left = i + 1;
}
}
}
sort(res.begin(), res.end(), greater<string>{});
string ans = accumulate(res.begin(), res.end(), ""s);
return ans;
}
};
|
