【LeetCode】761.特殊的二进制序列

题目

特殊的二进制序列是具有以下两个性质的二进制序列：
0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

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

示例 1:

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

说明:

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

题解

评价：题都看不懂，逻辑不懂。看了题解才知道题是什么意思

这里的前缀码容易误导人，理解为前缀比较合适，<=n-1的前缀

主要就是理解特殊二进制序列：

• 1和0数目相等
• 1开始，0结尾
• 类似括号，必须“（”开始，“）”结尾

class Solution {
public:
    string makeLargestSpecial(string s) {
        int len = s.size();
        if(len<=2)
            return s;

        vector<string> myvec;
        int cnt = 0;
        int pre = 0;
        for(int i=0;i<len;i++)
        {
            if(s[i] == '1')
            {
                cnt++;
            }
            else
            {
                cnt--;
                if(cnt==0)
                {
                    myvec.push_back("1" + makeLargestSpecial(s.substr(pre + 1, i - pre - 1)) + "0");
                    pre = i+1;
                }
            }
        }
        
        sort(myvec.begin(),myvec.end(),greater<string>{});
        // for(auto ss:myvec)
        //     cout<
        return accumulate(myvec.begin(),myvec.end(),string(""));
    }
};
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