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 <= 105
  • 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 的最少交换次数。

示例 1:

输入:nums = [1,0,0,1,0,1], k = 2
输出:1
解释:在第一次操作时,nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1

示例 2:

输入:nums = [1,0,0,0,0,0,1,1], k = 3
输出:5
解释:通过 5 次操作,最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3:

输入:nums = [1,1,0,1], k = 2
输出:0
解释:nums 已经有连续 21 了。

提示:

  • 1 <= nums.length <= 105
  • nums[i] 要么是 0 ,要么是 1 。
  • 1 <= k <= sum(nums)

解法一

单独写了一篇文章整理类似的题,详见