class Solution {
public:
string makeLargestSpecial(string s) {
}
};
761. 特殊的二进制序列
特殊的二进制序列是具有以下两个性质的二进制序列：
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
输入: S = "11011000" 输出: "11100100" 解释: 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。
说明:
S 的长度不超过 50。S 保证为一个满足上述定义的特殊 的二进制序列。相似题目
原站题解
java 解法, 执行用时: 3 ms, 内存消耗: 40.1 MB, 提交时间: 2023-06-12 16:24:17
class Solution {
public String makeLargestSpecial(String s) {
if (s.length() == 0) return s;
List<String> 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 sb.toString();
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 39.8 MB, 提交时间: 2023-06-12 16:23:58
class Solution {
public String makeLargestSpecial(String s) {
if (s.length() <= 2) {
return s;
}
int cnt = 0, left = 0;
List<String> subs = new ArrayList<String>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '1') {
++cnt;
} else {
--cnt;
if (cnt == 0) {
subs.add("1" + makeLargestSpecial(s.substring(left + 1, i)) + "0");
left = i + 1;
}
}
}
Collections.sort(subs, (a, b) -> b.compareTo(a));
StringBuilder ans = new StringBuilder();
for (String sub : subs) {
ans.append(sub);
}
return ans.toString();
}
}
javascript 解法, 执行用时: 84 ms, 内存消耗: 41.3 MB, 提交时间: 2023-06-12 16:23:42
/**
* @param {string} s
* @return {string}
*/
var makeLargestSpecial = function(s) {
if (s.length <= 2) {
return s;
}
let cnt = 0, left = 0;
const subs = [];
for (let i = 0; i < s.length; ++i) {
if (s[i] === '1') {
++cnt;
} else {
--cnt;
if (cnt === 0) {
subs.push("1" + makeLargestSpecial(s.substring(left + 1, i)) + '0');
left = i + 1;
}
}
}
subs.sort().reverse();
return subs.join('');
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-12 16:23:24
func makeLargestSpecial(s string) string {
if len(s) <= 2 {
return s
}
subs := sort.StringSlice{}
cnt, left := 0, 0
for i, ch := range s {
if ch == '1' {
cnt++
} else if cnt--; cnt == 0 {
subs = append(subs, "1"+makeLargestSpecial(s[left+1:i])+"0")
left = i + 1
}
}
sort.Sort(sort.Reverse(subs))
return strings.Join(subs, "")
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-12 16:23:08
# 分治
class Solution:
def makeLargestSpecial(self, s: str) -> str:
if len(s) <= 2:
return s
cnt = left = 0
subs = list()
for i, ch in enumerate(s):
if ch == "1":
cnt += 1
else:
cnt -= 1
if cnt == 0:
subs.append("1" + self.makeLargestSpecial(s[left+1:i]) + "0")
left = i + 1
subs.sort(reverse=True)
return "".join(subs)