class Solution {
public:
int minLength(string s, int numOps) {
}
};
3398. 字符相同的最短子字符串 I
给你一个长度为 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 <= 1000s 仅由 '0' 和 '1' 组成。0 <= numOps <= n原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 10.4 MB, 提交时间: 2024-12-26 07:39:26
class Solution {
public:
int minLength(string s, int numOps) {
int n = s.length();
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += (s[i] ^ i) & 1;
}
if (min(cnt, n - cnt) <= numOps) {
return 1;
}
vector<vector<pair<int, int>>> buckets(n + 1);
int k = 0;
for (int i = 0; i < n; i++) {
k++;
// 到达连续相同子串的末尾
if (i == n - 1 || s[i] != s[i + 1]) {
buckets[k].emplace_back(k, 1); // 原始子串长度，段数
k = 0;
}
}
int i = n;
while (numOps--) {
while (buckets[i].empty()) {
i--;
}
if (i == 2) {
return 2;
}
auto [k, seg] = buckets[i].back();
buckets[i].pop_back();
buckets[k / (seg + 1)].emplace_back(k, seg + 1);
}
while (buckets[i].empty()) {
i--;
}
return i;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 42.2 MB, 提交时间: 2024-12-26 07:39:13
class Solution {
public int minLength(String S, int numOps) {
char[] s = S.toCharArray();
int n = s.length;
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += (s[i] ^ i) & 1;
}
if (Math.min(cnt, n - cnt) <= numOps) {
return 1;
}
List<int[]>[] buckets = new ArrayList[n + 1];
Arrays.setAll(buckets, i -> new ArrayList<>());
int k = 0;
for (int i = 0; i < n; i++) {
k++;
// 到达连续相同子串的末尾
if (i == n - 1 || s[i] != s[i + 1]) {
buckets[k].add(new int[]{k, 1}); // 原始子串长度，段数
k = 0;
}
}
int i = n;
while (numOps-- > 0) {
while (buckets[i].isEmpty()) {
i--;
}
if (i == 2) {
return 2;
}
int[] p = buckets[i].remove(buckets[i].size() - 1);
buckets[p[0] / ++p[1]].add(p);
}
while (buckets[i].isEmpty()) {
i--;
}
return i;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 4.5 MB, 提交时间: 2024-12-26 07:38:57
func minLength(s string, numOps int) int {
n := len(s)
cnt := 0
for i, b := range s {
cnt += (int(b) ^ i) & 1
}
if min(cnt, n-cnt) <= numOps {
return 1
}
type pair struct{ k, seg int }
h := make([][]pair, n+1)
k := 0
for i := 0; i < n; i++ {
k++
// 到达连续相同子串的末尾
if i == n-1 || s[i] != s[i+1] {
h[k] = append(h[k], pair{k, 1}) // 原始子串长度，段数
k = 0
}
}
i := n
for range numOps {
for len(h[i]) == 0 {
i--
}
if i == 2 {
return 2
}
p := h[i][len(h[i])-1]
h[i] = h[i][:len(h[i])-1]
p.seg++
maxSeg := p.k / p.seg
h[maxSeg] = append(h[maxSeg], p)
}
for len(h[i]) == 0 {
i--
}
return i
}
python3 解法, 执行用时: 0 ms, 内存消耗: 17.6 MB, 提交时间: 2024-12-26 07:38:33
class Solution:
def minLength1(self, s: str, numOps: int) -> int:
cnt = sum((ord(b) ^ i) & 1 for i, b in enumerate(s))
if min(cnt, len(s) - cnt) <= numOps:
return 1
g = (list(t) for _, t in groupby(s))
# 子串操作后的最长子段长度，原始子串长度，段数
h = [(-k, k, 1) for k in map(len, g)]
heapify(h)
for _ in range(numOps):
max_seg, k, seg = h[0]
if max_seg == -2:
return 2
heapreplace(h, (-(k // (seg + 1)), k, seg + 1)) # 重新分割
return -h[0][0]
# 分桶优化
def minLength(self, s: str, numOps: int) -> int:
n = len(s)
cnt = sum((ord(b) ^ i) & 1 for i, b in enumerate(s))
if min(cnt, n - cnt) <= numOps:
return 1
buckets = [[] for _ in range(n + 1)]
for _, t in groupby(s):
k = len(list(t))
buckets[k].append((k, 1)) # 原始子串长度，段数
i = n
for _ in range(numOps):
while not buckets[i]:
i -= 1
if i == 2:
return 2
k, seg = buckets[i].pop()
buckets[k // (seg + 1)].append((k, seg + 1))
while not buckets[i]:
i -= 1
return i