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

题目描述

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。
- 比方说， "00010" -> "10010"
操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。
- 比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：

输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

提示：

1 <= binary.length <= 10⁵
binary 仅包含 '0' 和 '1' 。

解法

方法一：脑筋急转弯

我们观察发现，操作 \(2\) 可以把所有的 \(1\) 都移动到字符串的末尾，而操作 \(1\) 可以把所有的 0000..000 串变为 111..110。

因此，要想得到最大的二进制串，我们应该把所有不在开头的 \(1\) 移动到字符串末尾，使得字符串变为 111..11...000..00..11 的形式，然后借助操作 \(1\) 把中间的 000..00 变为 111..10。这样我们最终可以得到一个最多包含一个 \(0\) 的二进制字符串，这个字符串就是我们要求的最大二进制串。

在代码实现上，我们首先判断字符串是否包含 \(0\)，如果不包含，直接返回原字符串。否则，我们找到第一个 \(0\) 的位置 \(k\)，加上该位置之后的 \(0\) 的个数，得到的就是修改后的字符串的 \(0\) 所在的位置，其余位置都是 \(1\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串的长度。

Python3JavaC++GoTypeScriptRustC#

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        k = binary.find('0')
        if k == -1:
            return binary
        k += binary[k + 1 :].count('0')
        return '1' * k + '0' + '1' * (len(binary) - k - 1)

class Solution {
    public String maximumBinaryString(String binary) {
        int k = binary.indexOf('0');
        if (k == -1) {
            return binary;
        }
        int n = binary.length();
        for (int i = k + 1; i < n; ++i) {
            if (binary.charAt(i) == '0') {
                ++k;
            }
        }
        char[] ans = binary.toCharArray();
        Arrays.fill(ans, '1');
        ans[k] = '0';
        return String.valueOf(ans);
    }
}

class Solution {
public:
    string maximumBinaryString(string binary) {
        int k = binary.find('0');
        if (k == binary.npos) {
            return binary;
        }
        int n = binary.size();
        for (int i = k + 1; i < n; ++i) {
            if (binary[i] == '0') {
                ++k;
            }
        }
        return string(k, '1') + '0' + string(n - k - 1, '1');
    }
};

func maximumBinaryString(binary string) string {
    k := strings.IndexByte(binary, '0')
    if k == -1 {
        return binary
    }
    for _, c := range binary[k+1:] {
        if c == '0' {
            k++
        }
    }
    ans := []byte(binary)
    for i := range ans {
        ans[i] = '1'
    }
    ans[k] = '0'
    return string(ans)
}

function maximumBinaryString(binary: string): string {
    let k = binary.indexOf('0');
    if (k === -1) {
        return binary;
    }
    k += binary.slice(k + 1).split('0').length - 1;
    return '1'.repeat(k) + '0' + '1'.repeat(binary.length - k - 1);
}

impl Solution {
    pub fn maximum_binary_string(binary: String) -> String {
        if let Some(k) = binary.find('0') {
            let k = k + binary[k + 1..].chars().filter(|&c| c == '0').count();
            return format!(
                "{}{}{}",
                "1".repeat(k),
                "0",
                "1".repeat(binary.len() - k - 1)
            );
        }
        binary
    }
}

public class Solution {
    public string MaximumBinaryString(string binary) {
        int k = binary.IndexOf('0');
        if (k == -1) {
            return binary;
        }
        k += binary.Substring(k + 1).Count(c => c == '0');
        return new string('1', k) + '0' + new string('1', binary.Length - k - 1);
    }
}

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

题目描述

解法

方法一：脑筋急转弯

评论