【八月】每日一题 - 761. 特殊的二进制序列

问题描述

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

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

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

示例 1:

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

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

链接：leetcode.cn/problems/sp…

解题思路

本题最难的不是如何实现代码，而是如何“看懂”题意。“特殊”的二进制序列看的人一懵一懵的，我们不如换个思路看问题。

• 将字符1看为左括号，字符0看为右括号。
• 0 的数量与 1 的数量相等，二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。意味着括号都是成对出现的，每一个左括号必须有其能匹配的右括号，并且满足这种“特殊”的二进制序列不会存在类似)(的case，因为需要前缀码的1 数量大于 0。

那这样我们的问题就很好解决了，确定一下函数的输出内容，我们需要输出字符串按照字典序排列的最大的结果，其实就是找到其中可交换并且成对的括号进行排序，确保每一对括号内的“特殊”字符是有序的。直接看代码，带着注释会很好理解的。

AC代码

var makeLargestSpecial = function(s) {
    if(s.length <= 2) return s // 递归终止条件
    // 0 - left 保证其中的字典结果是最大的
    let left = 0,cnt = 0
    const result = []
    for(let i = 0; i < s.length; i++){
        if(s[i] === '1'){
            cnt++ // 遇到左括号 + 1
        }else{
            cnt-- 
            if(cnt === 0){ // 匹配的括号结束 如 （（ ）） （）
                // 这里是抽出中间的子括号，保证在当前（ 。。。。）括号内的结果都是字典结果最大的 
                result.push('1' + makeLargestSpecial(s.substring(left + 1,i)) + '0') 
                left = i + 1
            }
        }
    }
    result.sort().reverse()
    return result.join('')
};
``