LC76. Minimum Window Substring Hard
给定原串 S 和模式 T，取S的一个最小区间，使得 T 中每个字母都在这个子串中出现过。
暴力肯定是枚举起终点，考虑转化下，枚举起点和长度，这里长度可以二分答案了。
考虑单次验证的复杂度，枚举起点 O(n-ans)，遍历O(ans)，N^2级别的肯定不行。
滑动窗口的话，枚举字符串均摊 O(N)，但是对比答案呢，O(alphabet)，应该可以
最后 60*NlogN，应该是正解了。
最后做完看题解正解应该是双指针，O(n+m)
impl Solution {
fn count_alphabet(s: &String) -> Vec<i32>{
s.chars()
.map(|ch| ch as usize - 'A' as usize)
.fold(vec![0; 60], |mut count, i| {
count[i] += 1;
count
})
}
fn check(len: usize, s: &String, count_t: &Vec<i32>) -> (bool, usize, usize) {
let (mut res, mut res_l, mut res_r) = (false, 0, 0);
let is_greater_or_equal = |s: &Vec<i32>, t: &Vec<i32>| -> bool {
s.iter().zip(t.iter()).all(|(a, b)| a >= b)
};
let s: Vec<char> = s.chars().collect();
let mut count_s = Self::count_alphabet(&s[..len].iter().collect());
if is_greater_or_equal(&count_s, count_t) {
return (true, 0, len-1);
}
for i in len..s.len() { // enum the terminal one
count_s[s[i] as usize - 'A' as usize] += 1;
count_s[s[i-len] as usize - 'A' as usize] -= 1;
if is_greater_or_equal(&count_s, count_t) {
res = true;
res_l = i-len+1;
res_r = i;
}
}
(res, res_l, res_r)
}
pub fn min_window(s: String, t: String) -> String {
let count_t = Self::count_alphabet(&t);
let (mut l, mut r, mut ans_l, mut ans_r) = (1, s.len(), s.len(), 0);
while l <= r {
let mid = (l + r) >> 1;
let (res, res_l, res_r) = Self::check(mid, &s, &count_t);
println!("check {} : {} {} {}", mid, res, res_l, res_r);
if res {
(ans_l, ans_r) = (res_l, res_r);
r = mid - 1;
} else {
l = mid + 1;
}
}
// println!("result : {} {}", ans_l, ans_r);
if ans_l == s.len() {
return "".to_string();
}
s[ans_l..=ans_r].to_string()
// s
}
}LC1463. Cherry Pickup II Hard
最大三角路径的改版，有俩起点，且一个权值只能被获得一次，考虑 DP
范围 70*70，状压估计压不下来。本题核心应该就是处理权值不能重复获得。
有一个性质我觉得可以利用，就是如果走到同一格，俩人一定是一起到的。
考虑状态 dpx1x2,表示 1 号走到 x1y1，2 号走到 x2y2 的最大价值
转移按行，dpx1x2 可以从上一行的 {y1-1, y1, y1+1} 和 {y2-1, y2, y2+1}的笛卡尔积获得。
初始状态dp00 = val0 + val0
按行转移的话，发现 x1 永远是等于 x2 的，可以压一维, dpx[y2]，第一维也可以滚动，但是懒得滚动了
实际写的时候要注意下，有些格子不可达，枚举的时候扔掉（take用在这了）
这个五层循环不太优雅，不过这种 case 感觉也没啥改动空间
impl Solution {
pub fn cherry_pickup(grid: Vec<Vec<i32>>) -> i32 {
let (n, m) = (grid.len(), grid[0].len());
let mut dp = vec![vec![vec![0; m]; m]; n];
dp[0][0][m-1] = grid[0][0] + grid[0][m-1];
for i in 0..n-1 {
for y1 in (0..m).take(i+1) {
for y2 in (0..m).rev().take(i+1) {
for ty1 in y1.saturating_sub(1)..= y1 + 1 {
for ty2 in y2.saturating_sub(1)..= y2 + 1 {
if ty1 >= m || ty2 >= m {
continue;
}
dp[i+1][ty1][ty2] = std::cmp::max(
dp[i+1][ty1][ty2],
dp[i][y1][y2] +
if ty1 == ty2 {grid[i+1][ty1]}
else {grid[i+1][ty1] + grid[i+1][ty2]}
);
}
}
}
}
}
dp[n-1].iter()
.flat_map(|row| row.into_iter().copied())
.max()
.unwrap()
}
}LC1291. Sequential Digits Med
本来没范围限制，数字分割就好了。但是范围10 ^ 9，考虑其他的枚举方法
对于第一个数位是 k，只需拼个 kk+1k+2k+3 (k+l < 10) 即可
最后排个序
impl Solution {
pub fn sequential_digits(low: i32, high: i32) -> Vec<i32> {
let mut res = Vec::new();
for i in 1..=9 {
for l in i+1..=9 {
let mut now = 0;
for cur in i..=l {
now = now * 10 + cur;
}
if now >= low && now <= high {
res.push(now);
}
}
}
res.sort();
res
}
}一个更函数式的写法
impl Solution {
pub fn sequential_digits(low: i32, high: i32) -> Vec<i32> {
let mut res: Vec<_> = (1..=9)
.flat_map(|i| (i+1..=9).map(move |l| (i, l)))
.filter_map(|(i, l)| {
let now = (i..=l).fold(0, |now, cur| now * 10 + cur);
if now >= low && now <= high { Some(now) } else { None }
})
.collect();
res.sort();
res
}
}LC2966. Divide Array Into Arrays With Max Difference Med
额，感觉排个序贪心就行了，看看能不能锻炼下函数式编程技巧
impl Solution {
pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
nums.sort();
let res: Vec<Vec<i32>> = nums.chunks(3).map(|chunk| chunk.to_vec()).collect();
if res.iter().any(|sub_vec| sub_vec.len() == 3 && sub_vec[2] - sub_vec[0] > k) { vec![] } else {res}
}
}LC647. Palindromic Substrings Med
找到所有的回文子串，感觉比较常规的题
数据范围是 1000 。
考虑枚举子串+哈希，预处理正反串哈希，枚举之后看相同区间的正反串哈希是否一样即可。
应该是肯定能做，但是题目标签是 DP，想想能不能用 DP 做。
如果是 DP，肯定是从短到长，第一维枚举长度，第二维枚举起点，这样已经 n^2了，转移得考虑 O1 的
考虑 dpi 为 起点为 i，终点为 j 的串是否为回文，转移似乎应该是dpi+1 == 1 && s[i] == s[j]
考虑偶数的情况，初始值dpi = 1 if s[i] == s[i+1]
应该没啥不对的，两种方法都写下。
状态：dpi 表示从 i 到 j 的子串是否为回文串
边界条件：dpi = 1， dpi = 1 if s[i] == s[i+1]
答案：s[i..j] s.t. dpi == 1
转移：dpi = dpi+1 == 1 && s[i] == s[j]
impl Solution {
pub fn count_substrings(s: String) -> i32 {
let n = s.len();
let s = s.into_bytes();
let mut dp = vec![vec![false;n];n];
for i in 0..n {
dp[i][i] = true;
if i < n-1 && s[i] == s[i+1] {
dp[i][i+1] = true;
}
}
for len in (3..=n) {
for l in (0..n-len+1) {
dp[l][l+len-1] |= dp[l+1][l+len-2] && s[l] == s[l+len-1];
}
}
dp.iter()
.flat_map(|row| row.iter())
.filter(|&&value| value)
.count() as i32
// let mut res = 0;
// for (i, arr1) in dp.iter().enumerate() {
// for (j, cur) in arr1.iter().enumerate() {
// if *cur {
// res += 1;
// }
// }
// }
// res
}
}
评论 (0)