修改后的最大二进制字符串
难度:
标签:
题目描述
代码结果
运行时间: 49 ms, 内存: 16.9 MB
// 思路:
// 1. 我们的目标是尽可能将 '0' 转换为 '1',以获得最大二进制字符串。
// 2. 使用 Java Stream API 来计算 '0' 的数量和第一个 '0' 的位置。
// 3. 构建新的字符串,最终得到一个以 '1' 开头,紧随其后的都是 '0' 的字符串。注意最后一个 '1' 可以保持原位。
import java.util.stream.IntStream;
public class Solution {
public String maximumBinaryString(String binary) {
int zeroCount = (int) binary.chars().filter(ch -> ch == '0').count();
int firstZeroIndex = IntStream.range(0, binary.length()).filter(i -> binary.charAt(i) == '0').findFirst().orElse(-1);
if (zeroCount == 0) {
return binary;
}
StringBuilder sb = new StringBuilder(binary);
for (int i = firstZeroIndex; i < binary.length(); i++) {
if (i < firstZeroIndex + zeroCount - 1) {
sb.setCharAt(i, '1');
} else {
sb.setCharAt(i, '0');
}
}
sb.setCharAt(firstZeroIndex + zeroCount - 1, '1');
return sb.toString();
}
}
解释
方法:
题解采用的是直接计算最终结果的方法,而不是模拟每一步操作。首先,如果字符串中没有'0',或者字符串为'01',则直接返回原字符串,因为没有需要进行的操作。接着,计算字符串中'0'的总数量和第一个'0'出现的位置。最终结果可以通过以下方式构造:将第一个'0'之前所有的'1'保持不变,随后的所有'0'(除了最后一个'0'之外)都可以变为'1',最后保留一个'0',其余部分全部为'1'。这样构造的结果是在不违背操作规则的前提下,可以得到的最大二进制串。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到如果输入字符串为'01'就直接返回原字符串,但是根据操作规则不是可以将'01'改为'10'吗?这样做的原因是什么?
▷🦆
在构造最大二进制字符串的逻辑中,为什么要保留一个'0',而不是将所有的'0'都转换成'1'?
▷🦆
题解中提到将第一个'0'之前的所有'1'保持不变,这种策略是否总是能保证得到最大的二进制数?
▷🦆
如何确定在构建最终结果时,'1'的总数是 first_zero_index + zero_count - 1 而不是其他配置?
▷