当前位置：首页 > news >正文

豆包力扣 761. 特殊的二进制字符串 public String makeLargestSpecial(String s)

news 2026/3/26 21:59:09

你想要解决力扣 761 题「特殊的二进制字符串」，核心需求是找到给定特殊二进制字符串能重排得到的最大字典序字符串。

问题背景与解题思路

首先明确特殊的二进制字符串定义：

前缀中 ‘1’ 的数量始终不少于 ‘0’ 的数量；
整个字符串中 ‘1’ 和 ‘0’ 的数量相等。

解题核心思路（分治 + 贪心）：

拆分：将原字符串拆分为若干个不可再分的「最小特殊二进制子串」（形如1...0，且内部无法再拆分为更小的特殊子串）；
递归处理：对每个最小特殊子串的内部（去掉首尾的 1 和 0 后）递归处理，保证内部也是最大字典序；
排序拼接：将所有处理后的最小特殊子串按字典序降序排列，拼接后即为结果。

完整可运行代码

classSolution{publicStringmakeLargestSpecial(Strings){// 递归终止条件：空字符串或长度为0，直接返回if(s==null||s.length()==0){return"";}// 存储拆分后的最小特殊二进制子串List<String>parts=newArrayList<>();// 记录当前前缀中1的数量 - 0的数量（平衡值）intbalance=0;// 记录每个最小特殊子串的起始位置intstart=0;for(inti=0;i<s.length();i++){// 遇到1，平衡值+1；遇到0，平衡值-1balance+=s.charAt(i)=='1'?1:-1;// 当平衡值回到0时，说明找到了一个最小特殊子串 [start, i]if(balance==0){// 对该子串的内部（去掉首尾的1和0）递归处理，再拼接首尾Stringsub="1"+makeLargestSpecial(s.substring(start+1,i))+"0";parts.add(sub);// 更新下一个子串的起始位置start=i+1;}}// 将拆分后的子串按字典序降序排列（贪心：大的子串放前面，整体字典序最大）Collections.sort(parts,Collections.reverseOrder());// 拼接所有排序后的子串，得到最终结果StringBuildersb=newStringBuilder();for(Stringpart:parts){sb.append(part);}returnsb.toString();}}

代码关键部分解释

平衡值（balance）：
- 遍历字符串时，遇到 ‘1’ 加 1，遇到 ‘0’ 减 1；
- 当balance == 0时，说明从start到当前位置是一个最小特殊二进制子串（无法再拆分为更小的特殊子串）。
递归处理子串内部：
- 对于找到的最小子串s[start..i]，去掉首尾的 ‘1’ 和 ‘0’（即s[start+1..i-1]），递归调用函数处理内部，保证内部也是最大字典序；
- 处理后再拼接回首尾的 ‘1’ 和 ‘0’，得到该子串的最大形式。
贪心排序：
- 将所有处理后的最小子串按字典序降序排列，拼接后整体字典序最大（例如1100比1010字典序大，应放在前面）。