普通视图

发现新文章,点击刷新页面。
今天 — 2026年2月20日首页

特殊的二进制序列【递归】

2022年8月8日 07:58

方法一:递归

我们可以把特殊的二进制序列看作"有效的括号",1代表左括号,0代表右括号。

  • 0的数量与1的数量相等,代表左右括号数量相等。
  • 二进制序列的每一个前缀码中1的数量要大于等于0的数量,代表有效的括号,每一个左括号都有右括号匹配,并且左括号在前。

比如:"11011000"可以看作"(()(()))"。

两个连续且非空的特殊的子串,然后将它们交换,代表着交换两个相邻的两个有效括号。

我们可以将题进行如下划分,把每一个有效的括号匹配都看作一部分,然后进行排序,内部也进行排序处理,例如:
image.png

代码如下

###java

    public String makeLargestSpecial(String s) {
        if (s.length() == 0) {
            return "";
        }
        List<String> list = new ArrayList<>();
        int count = 0, last = 0;
        for (int i = 0, cur = 0; i < s.length(); i++, cur++) {
            if (s.charAt(i) == '1') {
                count++;
            } else {
                count--;
            }
            //一组有效的括号匹配 去掉括号进行 内部排序
            if (count == 0) {
                String str = "1" + makeLargestSpecial(s.substring(last + 1, cur)) + "0";
                list.add(str);
                last = cur + 1;
            }
        }
        //进行排序,根据冒泡排序,交换两个相邻的元素进行排序,总能让内部的括号由大到小排列
        list.sort(Comparator.reverseOrder());
        //拼成完整的字符串
        StringBuilder sb = new StringBuilder();
        for (String str : list) {
            sb.append(str);
        }
        return sb.toString();
    }

写题解不易,如果对您有帮助,记得关注 + 点赞 + 收藏呦!!!
每天都会更新每日一题题解,大家加油!!

❌
❌