leetcode
leetcode 1501 ~ 1550
修改后的最大二进制字符串

修改后的最大二进制字符串

难度:

标签:

题目描述

代码结果

运行时间: 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'吗?这样做的原因是什么?
这是题解中的一个错误。确实根据题目中描述的操作规则,'01'可以通过操作转换成'10',从而得到一个更大的二进制数。正确的处理应该是在遇到'01'这种特殊情况时,直接将其转换成'10'。这种情况可能是题解作者的疏忽或者对题目理解的误解。
🦆
在构造最大二进制字符串的逻辑中,为什么要保留一个'0',而不是将所有的'0'都转换成'1'?
在给定的操作规则下,我们不能随意更改任意位置的'0'为'1',而是要通过特定的操作来实现。操作规则通常允许我们在某些条件下将一个'0'和其后面相邻的'1'交换位置。当所有可操作的'0'都被移动到尽可能靠右的位置后,最后剩余的那个'0'不能再通过任何操作转换为'1',因此需要保留这个'0'。
🦆
题解中提到将第一个'0'之前的所有'1'保持不变,这种策略是否总是能保证得到最大的二进制数?
是的,这种策略能保证得到最大的二进制数。因为第一个'0'之前的所有'1'已经处于最高位,移动这些'1'的位置不会使得二进制数变得更大。我们的目标是尽可能让'1'占据更高的位,因此将第一个'0'之前的'1'保持不变,并尽可能将后续的'0'转换成'1'或移动到较低的位置,是实现这一目标的有效策略。
🦆
如何确定在构建最终结果时,'1'的总数是 first_zero_index + zero_count - 1 而不是其他配置?
这个构造是基于将尽可能多的'0'转换为'1'的目标。首先,first_zero_index表示第一个'0'出现的位置,这之前的所有'1'已经是在尽可能高的位置。zero_count表示总共有多少个'0'。我们的目标是将除了最后一个'0'之外的所有'0'都转换成'1'。因此,在第一个'0'之后的位置上,我们可以有 zero_count - 1 个'0'被转换为'1'。加上原始的 first_zero_index 个'1',总共就是 first_zero_index + zero_count - 1 个'1'。

相关问题