761. 特殊的二进制序列 : 经典构造题

761. 特殊的二进制序列 : 经典构造题

题目描述

这是 LeetCode 上的 ​​761. 特殊的二进制序列​​ ，难度为 困难。

Tag : 「构造」

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

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

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

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

示例 1:

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

说明:

构造

每次操作可以将相邻特殊字符串进行交换，于是问题转换为将 ​​s​​ 进行重排，求其重排后字典序最大的方案。

因此可将构造分两步进行：

对于每个​​item​​ 进行重排，使其调整为字典序最大对于​​item​​ 之间的位置进行重排，使其整体字典序最大

由于题目没有规定重排后的性质，为第一步调整和第二步调整的保持相对独立，我们只能对 ​​item​​​ 中的 ​​1...0​​ 中的非边缘部分进行调整（递归处理子串部分）。

假设所有 ​​item​​ 均被处理后，考虑如何进行重排能够使得最终方案字典序最大。

若有两个 ​​item​​​，分别为 ​​a​​​ 和 ​​b​​​，我们可以根据拼接结果 ​​ab​​​ 和 ​​ba​​ 的字典序大小来决定将谁放在前面。

这样根据「排序比较逻辑」需要证明在集合上具有​​「全序关系」​​:

2.1 完全性

2.2 反对称性

2.3 传递性

最终，我们证明了该「排序比较逻辑」必然能排序出字典序最大的方案。

Java 代码：

class Solution { public String makeLargestSpecial(String s) { if (s.length() == 0) return s; List list = new ArrayList<>(); char[] cs = s.toCharArray(); for (int i = 0, j = 0, k = 0; i < cs.length; i++) { k += cs[i] == '1' ? 1 : -1; if (k == 0) { list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0"); j = i + 1; } } Collections.sort(list, (a, b)->(b + a).compareTo(a + b)); StringBuilder sb = new StringBuilder(); for (String str : list) sb.append(str); return

TypeScript 代码：

function makeLargestSpecial(s: string): string { const list = new Array() for (let i = 0, j = 0, k = 0; i < s.length; i++) { k += s[i] == '1' ? 1 : -1 if (k == 0) { list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0') j = i + 1 } } list.sort((a, b)=>(b + a).localeCompare(a + b)); return [...list].join("")};

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.761​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。