思路:
想要数变大,应该尽可能将 0 变换为 1
而且从直观上想,我们应该从左往右考虑,当遇到某一位为 0 的时候,需要尽可能的把该位变为 1 ,而不管后面发生什么变化,因为 xxx1yyy 总是大于 xxx0yyy
想要将该位从 0 变为 1,我们需要利用 (00 -> 10) 的规则,即需要它的下一位为 0
但它下一位不一定就直接是 0,我们先将该位置记为 i,这时候我们可以找距离 i 最近的下一位 0 的位置,记为 j
既然 j 是 距离 i 的第一个 0,那么说明 i 到 j 之间必然全是 1
这时候我们可以利用 (10 -> 01) 的规则,将 j 位置的 0 “传递”到 i 的下一个位置,从而实现将 i 位置的 0 变为 1
举例来说,也就是我们会进行这样的变化:
11101110 -> 11101101 -> 11101011 -> 11100111 -> 11110111
再思考,我们会发现,某一位 0 能够被变为 1 的前提:该位的后面仍然存在 0;并且转换成 1 后等效于将后面的最近的 0 移动到了 i + 1 的位置
所以最优解中,最多只会存在 1 个 0。
所以我们可以先找到第一个 0 的位置,记为 k,然后找到后面还有多少位 0,数量记为 cnt
那么就意味着,最终 0 的位置为 k + cnt,其余全是 1
代码如下
class Solution {
public String maximumBinaryString(String s) {
int n = s.length();
char[] cs = s.toCharArray();
int k = -1;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (cs[i] == '0') {
if (k == -1) k = i;
cnt++;
}
}
if (cnt == 0) return s;
cnt--; // 减去第一个 0
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (i != k + cnt) {
sb.append('1');
} else {
sb.append('0');
}
}
return sb.toString();
}
}