力扣 42th 双周赛

2021-01-06 约 902 字预计阅读 2 分钟

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

Difficulty: 中等

给你一个二进制字符串 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’ 。

解法一

因为是补题，之前在群里有看见讨论，大致的提到了一些，所以这里很快就想到了贪心的思路。首先 01 是无法继续变化的，10 是可以变成 01 的，而开头连续的 1 肯定是不需要再变化的，变化只会使得结果变小，所以我们可以将除了开头连续的 1 以外的所有的 1 都转换到最后（一定是可以的，因为 10 可以变成 01），然后再将中间的 00 都转换成 10 最后剩下的就只有中间的一个 0，这样就使得结果最大了。最终的结果就是 1111…0…111 类似的形式

public class MaximumBinaryString {
    //100101100 --> 100000111 --> 111110111
1   //1100 --> 1110
    public String maximumBinaryString(String binary) {
        int n = binary.length();
        int cnt = 0;
        int i = 0;
        while (i < n && binary.charAt(i) == '1') i++;
        if (i==n) return binary;
        while (i < n) {
            if (binary.charAt(i) == '1') cnt++;
            i++;
        }
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < n-cnt-1; j++) {
            sb.append("1");
        }
        sb.append("0");
        for (int j = 0; j < cnt; j++) {
            sb.append("1");
        }
        return sb.toString();
    }
}

1703. 得到连续 K 个 1 的最少相邻交换次数

Difficulty: 困难

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择相邻两个数字并将它们交换。

请你返回使 nums 中包含 k 个连续 1 的最少交换次数。