【C/C++】761. 特殊的二进制序列

---

题目链接：761. 特殊的二进制序列

题目描述

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

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

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

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

提示:

• S 的长度不超过 50。
• s[i] is either '0' or '1'.
• S 保证为一个满足上述定义的 特殊 的二进制序列。

示例 1：

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

示例 2：

输入: s = "10"
输出: "10"

整理题意

题目给定一个仅含有 0 和 1 的特殊的二进制序列，规定这个特殊的二进制序列 0 的数量与 1 的数量相等，且二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。现在规定我们可以对该字符串进行操作：选择两个连续且相邻的 特殊二进制序列 子串进行交换。

可以进行任意次数的操作，返回字符串按照字典序排列的最大的结果。

解题思路分析

我们将题目规定的特殊的二进制序列中 1 看成左括号 '('，0 看成右括号 ')'，那么根据题意描述特殊的二进制序列就是合法的括号序列。那么可以进行的操作就可以看成，选择两个相邻的且合法的括号序列进行交换。使得最后交换结果字典序排列最大也就是左括号尽量靠前。

将题目这样进行转换后，我们可以对每个合法括号序列内部的合法括号序列进行排序，也就是将左括号尽可能多的序列排在前面，那么对于括号内部的合法括号序列也要按照当前操作进行排序，即为子问题，我们可以采取 递归 的方法来完成。

具体实现

对于当前的字符串序列，我们遍历该字符串，寻找所有合法的括号序列，也就是把 1 看成左括号 '('，0 看成右括号 ')' 后形成的合法括号序列，同时对每个合法的括号列继续进行递归处理。

对当前字符串中每个合法的括号序列进行排序处理，按照字典序降序排序，然后再将这些括号序列合并连接起来作为返回值返回。

由于每一次我们可以交换两个相邻的特殊序列，因此按照冒泡排序的方法，我们可以将这些特殊序列任意进行的排列，也就一定能得到字典序最大的字符串。

如何找到合法的括号序列：

• 在编写代码时，我们可以使用一个计数器，并从头遍历给定的字符串。当我们遇到 1 时计数器加 1，遇到 0 时计数器减 1。
• 当计数器为 0 时，我们就拆分除了一个 合法 的括号序列，也就是特殊的二进制子串。

复杂度分析

• 时间复杂度：O(n2)O(n^2)O(n2)，其中 n 是字符串 s 的长度。在最坏的情况下，s 由 n2\dfrac{n}{2}2n​ 个 1 接着 n2\dfrac{n}{2}2n​ 个 0 拼接而成，每次递归仅减少 2 的字符串长度，需要进行 n2\dfrac{n}{2}2n​ 次递归。同时每次递归需要 O(n)O(n)O(n) 的时间进行拼接并返回答案，因此总时间复杂度为 O(n2)O(n^2)O(n2)。
• 空间复杂度：O(n)O(n)O(n)，即为递归需要的栈空间以及存储递归返回的字符串需要的临时空间。

代码实现

class Solution {
public:
    string makeLargestSpecial(string s) {
        // 当字符串长度为 2 或 0 时无需排序直接返回
        if(s.length() <= 2) return s;
        vector<string> res; res.clear();
        int cnt = 0;
        int n = s.length(), left = 0;
        // 取出字符串s中每个特殊的子串
        for(int i = 0; i < n; i++){
            if(s[i] == '1') cnt++;
            else cnt--;
            if(cnt == 0){
                res.emplace_back("1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0");
                left = i + 1;
            }
        }
        // 对所有特殊子串进行排序，按照字典序降序排序
        sort(res.begin(), res.end(), greater<string>());
        string ans = "";
        for(auto &t : res) ans += t;
        return ans;
    }
};

总结

• 该题难点在于题目理解上，如何理解 特殊的二进制序列，将其看为合法的括号序列成为解题关键。
• 核心思想：对每个合法括号序列内部进行 拆分，拆分为一个一个连续的合法括号序列，然后对其进行 排序 处理，最后将排序后的合法括号序列进行 合并 连接，最后返回即可。对于每个合法的括号序列可以看作一个新的子问题，所以可以采用 递归 的思想进行解决。
• 测试结果：

结束语

人生路上，每个人都在奔跑，我们会赶超一些人，也会被一些人超越。有的人想要尽早抵达目的地，有的人偏爱欣赏沿途的风景。试着寻找一种最适合自己的速度，莫因疾进而不堪重荷，莫因迟缓而空耗生命。新的一天，加油！