特殊的二进制序列
解题思路：
-
将 1 看成 “(”，0 看成 “)”，实际上是一道有效的括号问题，最终要让前面左括号尽可能多；
-
将字符串拆分成一段或几段 “不可拆分的有效的括号字符串”；
-
将每一段内部的子串（也是 “有效的括号字符串”）分别重新排列成字典序最大的字符串（解决子问题）；
-
由于每一对相邻的段都可以交换，因此无限次交换相当于可以把各个段以任意顺序排列，找到字典序最大的排列；
图解：
复杂度：
-
时间复杂度：O(n^2)；
-
空间复杂度：O(n)，即为递归需要的栈空间以及存储递归返回的字符串需要的临时空间；
代码实现：
function makeLargestSpecial(s: string): string {
// 1.结束条件
if (s.length <= 1) return s;
// 2.函数主功能：遍历查找子串、子串排序、子串逆序拼接成字符串
let strList: Array<string> = [];
let start: number = 0; // 符合规则特殊字串的起始位置
let countOne: number = 0; // 存放 1、0 的数量差
// 从前往后遍历查找，以 start 开头是否存在符合要求的子串
for (let i = 0; i < s.length; i++) {
// 计算 1、0 的数量差
countOne += s[i] === "1" ? 1 : -1;
// countOne === 0，表示找到第一个特殊字符
if (countOne === 0) {
// 对特殊字符去掉头尾的 1、0 然后递归求解字典序最大
let result = makeLargestSpecial(s.substring(start + 1, i));
// 在递归结果上添加头尾 1、0 放入到字符串数组中
strList.push(`1${result}0`);
// 记录特殊子串下标位置
start = i + 1;
}
}
// 3. 对数组中的连续子串进行冒泡排序
strList.sort((a, b) => b.localeCompare(a));
// 排序后的连续子串，逆序拼成字符串
return strList.join("");
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 位运算基础
上一篇
评论
