题目描述
给定一个二进制字符串 binary
,它仅由 0
或者 1
组成。你可以使用下面的操作任意次对它进行修改:
- 操作 1 :如果二进制串包含子字符串
"00"
,你可以用"10"
将其替换。- 比方说,
"00010" -> "10010"
- 比方说,
- 操作 2 :如果二进制串包含子字符串
"10"
,你可以用"01"
将其替换。- 比方说,
"00010" -> "00001"
- 比方说,
请你返回执行上述操作任意次以后能得到的 最大二进制字符串。如果二进制字符串 x
对应的十进制数字大于二进制字符串 y
对应的十进制数字,那么我们称二进制字符串 x
大于二进制字符串 y
。
样例
输入:binary = "000110"
输出:"111011"
解释:一个可行的转换为:
"000110" -> "000101"
"000101" -> "100101"
"100101" -> "110101"
"110101" -> "110011"
"110011" -> "111011"
输入:binary = "01"
输出:"01"
解释:"01" 没办法进行任何转换。
限制
1 <= binary.length <= 10^5
binary
仅包含'0'
和'1'
。
算法
(贪心) $O(n)$
- 抽象一下给定的两种操作:第一种是添加 1,第二种是将高位的 1 借助 0 向低位移动。
- 容易发现,最终的最大的二进制串,最多只有一个 0。否则,总可以将两个以上的 0 放在一起,让原先在高位的 0 变为 1。而且,如果原字符串存在 0,则最终的答案也一定存在 0。
- 如果字符串全为 1,则直接返回原串。接下来考察最后的 0 出现的位置。
- 从高位往低位考虑,高位开始的连续的 1 是不需要移动的,也不可能是最后出现 0 的位置。从高位开始,找到第一个 0 的位置,此时,可以不断的寻找更低位的 0,移动到当前 0 的后边,构成
"00"
,变为"10"
。 - 发现规律,只需要将 不在高位中连续 的 1 都移动尽可能低的位上,最后的 0 出现在这些连续低位的 1 的高一位上。
- 例如
"11101001101"
,高位三个连续的 1 不动,剩下的 1 都放尽可能低的位上,变为"11100001111"
。最后变为"11111101111"
。
时间复杂度
- 遍历字符串一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
string maximumBinaryString(string binary) {
const int n = binary.size();
int ones = 0, continous_ones = 0;
bool continous = true;
for (int i = 0; i < n; i++) {
if (binary[i] == '1') {
ones++;
if (continous)
continous_ones++;
} else {
continous = false;
binary[i] = '1';
}
}
if (ones == n)
return binary;
binary[continous_ones + n - ones - 1] = '0';
return binary;
}
};