class Solution {
public:
int minLength(string s, int numOps) {
}
};
3399. 字符相同的最短子字符串 II
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。
你可以对 s 执行以下操作，最多 numOps 次：
i（其中 0 <= i < n），并 翻转 s[i]，即如果 s[i] == '1'，则将 s[i] 改为 '0'，反之亦然。你需要 最小化 s 的最长 相同子字符串 的长度，相同子字符串是指子字符串中的所有字符都相同。
返回执行所有操作后可获得的 最小 长度。
子字符串 是字符串中一个连续、 非空 的字符序列。
示例 1：
输入: s = "000001", numOps = 1
输出: 2
解释:
将 s[2] 改为 '1'，s 变为 "001001"。最长的所有字符相同的子串为 s[0..1] 和 s[3..4]。
示例 2：
输入: s = "0000", numOps = 2
输出: 1
解释:
将 s[0] 和 s[2] 改为 '1'，s 变为 "1010"。
示例 3：
输入: s = "0101", numOps = 0
输出: 1
提示：
1 <= n == s.length <= 105s 仅由 '0' 和 '1' 组成。0 <= numOps <= n原站题解
golang 解法, 执行用时: 84 ms, 内存消耗: 8.1 MB, 提交时间: 2024-12-26 07:37:25
func minLength(s string, numOps int) int {
n := len(s)
return 1 + sort.Search(n-1, func(m int) bool {
m++
cnt := 0
if m == 1 {
// 改成 0101...
for i, b := range s {
// 如果 s[i] 和 i 的奇偶性不同，cnt 加一
cnt += (int(b) ^ i) & 1
}
// n-cnt 表示改成 1010...
cnt = min(cnt, n-cnt)
} else {
k := 0
for i := range n {
k++
// 到达连续相同子串的末尾
if i == n-1 || s[i] != s[i+1] {
cnt += k / (m + 1)
k = 0
}
}
}
return cnt <= numOps
})
}
cpp 解法, 执行用时: 129 ms, 内存消耗: 18.1 MB, 提交时间: 2024-12-26 07:37:10
class Solution {
public:
int minLength(string s, int numOps) {
int n = s.length();
auto check = [&](int m) -> bool {
int cnt = 0;
if (m == 1) {
// 改成 0101...
for (int i = 0; i < n; i++) {
// 如果 s[i] 和 i 的奇偶性不同，cnt 加一
cnt += (s[i] ^ i) & 1;
}
// n-cnt 表示改成 1010...
cnt = min(cnt, n - cnt);
} else {
int k = 0;
for (int i = 0; i < n; i++) {
k++;
// 到达连续相同子串的末尾
if (i == n - 1 || s[i] != s[i + 1]) {
cnt += k / (m + 1);
k = 0;
}
}
}
return cnt <= numOps;
};
int left = 0, right = n;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
(check(mid) ? right : left) = mid;
}
return right;
}
};
java 解法, 执行用时: 73 ms, 内存消耗: 44.7 MB, 提交时间: 2024-12-26 07:36:56
class Solution {
public int minLength(String S, int numOps) {
char[] s = S.toCharArray();
int left = 0;
int right = s.length;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
if (check(mid, s, numOps)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int m, char[] s, int numOps) {
int n = s.length;
int cnt = 0;
if (m == 1) {
// 改成 0101...
for (int i = 0; i < n; i++) {
// 如果 s[i] 和 i 的奇偶性不同，cnt 加一
cnt += (s[i] ^ i) & 1;
}
// n-cnt 表示改成 1010...
cnt = Math.min(cnt, n - cnt);
} else {
int k = 0;
for (int i = 0; i < n; i++) {
k++;
// 到达连续相同子串的末尾
if (i == n - 1 || s[i] != s[i + 1]) {
cnt += k / (m + 1);
k = 0;
}
}
}
return cnt <= numOps;
}
}
python3 解法, 执行用时: 2265 ms, 内存消耗: 17.8 MB, 提交时间: 2024-12-26 07:36:40
class Solution:
def minLength(self, s: str, numOps: int) -> int:
n = len(s)
def check(m: int) -> bool:
cnt = 0
if m == 1:
# 改成 0101...
# 如果 s[i] 和 i 的奇偶性不同，cnt 加一
cnt = sum((ord(b) ^ i) & 1 for i, b in enumerate(s))
# n-cnt 表示改成 1010...
cnt = min(cnt, n - cnt)
else:
k = 0
for i, b in enumerate(s):
k += 1
# 到达连续相同子串的末尾
if i == n - 1 or b != s[i + 1]:
cnt += k // (m + 1)
k = 0
return cnt <= numOps
return bisect_left(range(n), True, 1, key=check)
# groupby
def minLength2(self, s: str, numOps: int) -> int:
n = len(s)
def check(m: int) -> bool:
if m == 1:
# 改成 0101...
# 如果 s[i] 和 i 的奇偶性不同，cnt 加一
cnt = sum((ord(b) ^ i) & 1 for i, b in enumerate(s))
# n-cnt 表示改成 1010...
cnt = min(cnt, n - cnt)
else:
cnt = sum(len(list(t)) // (m + 1) for _, t in groupby(s))
return cnt <= numOps
return bisect_left(range(n), True, 1, key=check)