特殊的二进制序列【递归】
2022年8月8日 07:58
方法一:递归
我们可以把特殊的二进制序列看作"有效的括号",1代表左括号,0代表右括号。
- 0的数量与1的数量相等,代表左右括号数量相等。
- 二进制序列的每一个前缀码中1的数量要大于等于0的数量,代表有效的括号,每一个左括号都有右括号匹配,并且左括号在前。
比如:"11011000"可以看作"(()(()))"。
两个连续且非空的特殊的子串,然后将它们交换,代表着交换两个相邻的两个有效括号。
我们可以将题进行如下划分,把每一个有效的括号匹配都看作一部分,然后进行排序,内部也进行排序处理,例如:![]()
代码如下
###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();
}
写题解不易,如果对您有帮助,记得关注 + 点赞 + 收藏呦!!!
每天都会更新每日一题题解,大家加油!!