142 lines
4.9 KiB
Markdown
142 lines
4.9 KiB
Markdown
- [3137. K 周期字符串需要的最少操作次数](https://leetcode.cn/problems/minimum-number-of-operations-to-make-word-k-periodic/description/?envType=daily-question&envId=2024-08-17)
|
||
- 按照 k 长度进行字符串分割
|
||
- 把分割的子串做为hashmap的key，计算不同的key计数
|
||
- 用总的子串数 - 最多计数的子串数
|
||
|
||
### 411 周赛
|
||
|
||
- [100402. 统计满足 K 约束的子字符串数量 I - 力扣（LeetCode）](https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/description/)
|
||
- 使用暴力dp
|
||
|
||
计算 i-j 的 ‘0’ 和 ‘1’ 的数量，通过计算 i-j 之前的子串数量，再求和。最后得到的答案
|
||
|
||
- 使用滑动窗口
|
||
|
||
```rust
|
||
impl Solution {
|
||
pub fn count_k_constraint_substrings(s: String, k: i32) -> i32 {
|
||
let mut ans: i32 = 0;
|
||
let mut left = 0;
|
||
let mut cnt = [0; 2];
|
||
let chars = s.chars().collect::<Vec<char>>();
|
||
for (right, ch) in chars.iter().enumerate() {
|
||
// 计算当前窗口的 '0' '1' 的数量
|
||
cnt[ch.to_digit(10).unwrap() as usize] += 1;
|
||
// 如果窗口内的 '0' '1' 数量不满足条件，则通过 left+=1；移动窗口
|
||
while cnt[0] > k && cnt[1] > k {
|
||
cnt[chars[left].to_digit(10).unwrap() as usize] -= 1;
|
||
left += 1;
|
||
}
|
||
// 把窗口长度加到结果里面，窗口内的符合条件的子串，会被其他窗口添加进去
|
||
ans += (right - left + 1) as i32;
|
||
}
|
||
return ans;
|
||
}
|
||
}
|
||
```
|
||
|
||
## [3306. 元音辅音字符串计数 II - 力扣（LeetCode）](https://leetcode.cn/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/description/)
|
||
|
||
```Rust
|
||
use std::collections::HashMap;
|
||
|
||
impl Solution {
|
||
|
||
pub fn count_of_substrings(word: String, k: i32) -> i64 {
|
||
let len = word.len();
|
||
let word_arr = word.chars().collect::<Vec<char>>();
|
||
let mut vowel_map: HashMap<char, i32> = HashMap::new();
|
||
let mut k_cnt = 0;
|
||
|
||
fn is_vowel(c: &char) -> bool {
|
||
"aeiou".contains(*c)
|
||
}
|
||
|
||
let mut last_next = len;
|
||
let mut cache = vec![0; len];
|
||
for i in (0..len).rev() {
|
||
cache[i] = last_next;
|
||
if !is_vowel(&word_arr[i]) {
|
||
last_next = i;
|
||
}
|
||
}
|
||
|
||
let mut left = 0;
|
||
let mut ans = 0;
|
||
|
||
for right in 0..len {
|
||
if is_vowel(&word_arr[right]) {
|
||
let e = vowel_map.entry(word_arr[right]).or_insert(0);
|
||
*e += 1;
|
||
} else {
|
||
k_cnt += 1;
|
||
}
|
||
|
||
let val = cache[right] - right;
|
||
|
||
while (left <= right && k_cnt > k) || (vowel_map.len() == 5 && k_cnt == k) {
|
||
if vowel_map.len() == 5 && k_cnt == k {
|
||
ans += val as i64;
|
||
}
|
||
let l_ch = &word_arr[left];
|
||
if is_vowel(l_ch) {
|
||
let e = vowel_map.entry(*l_ch).or_insert(0);
|
||
if *e == 1 { vowel_map.remove(&l_ch); } else { *e -= 1; }
|
||
} else {
|
||
k_cnt -= 1;
|
||
}
|
||
left += 1;
|
||
}
|
||
}
|
||
ans
|
||
}
|
||
|
||
}
|
||
```
|
||
第二种，看的大佬的题解：把计算k个辅音字母数，改成至少 k 个辅音字母数，最后可以通过，fn(k) - f(k+1) 计算的到复合预期的子字符串的总数, 代码如下：
|
||
```Rust
|
||
use std::collections::HashMap;
|
||
|
||
impl Solution {
|
||
|
||
pub fn count_of_substrings(word: String, k: i32) -> i64 {
|
||
fn cal(word: &Vec<char>, k: i32) -> i64 {
|
||
let len = word.len();
|
||
let mut vowel_map: HashMap<&char, i32> = HashMap::new();
|
||
let mut k_cnt = 0;
|
||
|
||
fn is_vowel(c: &char) -> bool {
|
||
"aeiou".contains(*c)
|
||
}
|
||
|
||
let mut left = 0;
|
||
let mut ans = 0;
|
||
|
||
for (i, ch) in word.iter().enumerate() {
|
||
if is_vowel(ch) {
|
||
let e = vowel_map.entry(ch).or_insert(0);
|
||
*e += 1;
|
||
} else {
|
||
k_cnt += 1;
|
||
}
|
||
|
||
while vowel_map.len() == 5 && k_cnt >= k {
|
||
let l_ch = &word[left];
|
||
if is_vowel(&l_ch) {
|
||
let e = vowel_map.entry(l_ch).or_insert(0);
|
||
if *e == 1 { vowel_map.remove(&l_ch); } else { *e -= 1; }
|
||
} else {
|
||
k_cnt -= 1;
|
||
}
|
||
left += 1;
|
||
}
|
||
ans += left as i64;
|
||
}
|
||
ans
|
||
}
|
||
let char_arr = word.chars().collect::<Vec<char>>();
|
||
cal(&char_arr, k) - cal(&char_arr, k+1)
|
||
}
|
||
|
||
}
|
||
``` |