76. 最小覆盖子串 Minimum Window Substring
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 10^5s和t由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
代码1： 滑动窗口
use std::collections::HashMap; fn min_window(s: String, t: String) -> String { let s: Vec<u8> = s.into_bytes(); let t: Vec<u8> = t.into_bytes(); if s.len() < t.len() { return String::new(); } let mut need: HashMap<u8, i32> = HashMap::new(); // 存储t中每个字符的出现次数 for i in 0..t.len() { *need.entry(t[i]).or_insert(0) += 1; } let (mut left, mut right) = (0, 0); // 滑动窗口的左右指针 let mut count = t.len(); // 记录滑动窗口中还需要的字符数 let mut min_len = s.len() + 1; // 记录最小覆盖子串的长度 let mut start = 0; // 记录最小覆盖子串的起始位置 while right < s.len() { // 当右指针指向的字符是需要的字符，count减一 if let Some(v) = need.get_mut(&s[right]) { if *v > 0 { count -= 1; } *v -= 1; } right += 1; // 当count为0时，说明滑动窗口中已经包含t中的所有字符 while count == 0 { // 如果当前的覆盖子串更小，则更新最小覆盖子串的长度和起始位置 if right - left < min_len { min_len = right - left; start = left; } // 当左指针指向的字符是需要的字符，count加一 if let Some(v) = need.get_mut(&s[left]) { *v += 1; if *v > 0 { count += 1; } } left += 1; } } if min_len == s.len() + 1 { "".to_string() } else { String::from_utf8_lossy(&s[start..start + min_len]).to_string() } } fn main() { println!("{}", min_window("ADOBECODEBANC".to_string(), "ABC".to_string())); println!("{}", min_window("a".to_string(), "a".to_string())); println!("{}", min_window("a".to_string(), "aa".to_string())); }
代码2：双指针
use std::collections::HashMap; fn min_window(s: String, t: String) -> String { let mut need: HashMap<char, i32> = HashMap::new(); let mut count = t.len() as i32; let (mut left, mut right, mut start, mut min_len) = (0, 0, 0, s.len() + 1); for c in t.chars() { *need.entry(c).or_insert(0) += 1; } let s = s.chars().collect::<Vec<_>>(); while right < s.len() { if let Some(v) = need.get_mut(&s[right]) { if *v > 0 { count -= 1; } *v -= 1; } right += 1; while count == 0 { if right - left < min_len { min_len = right - left; start = left; } if let Some(v) = need.get_mut(&s[left]) { *v += 1; if *v > 0 { count += 1; } } left += 1; } } if min_len == s.len() + 1 { "".to_owned() // 返回空字符串 } else { s[start..start + min_len].iter().collect() } } fn main() { println!("{}", min_window("ADOBECODEBANC".to_string(), "ABC".to_string())); println!("{}", min_window("a".to_string(), "a".to_string())); println!("{}", min_window("a".to_string(), "aa".to_string())); }
输出：
BANC
a
//空行
77. 组合 Combinations
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
代码1： 回溯法
fn combine(n: i32, k: i32) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![]; // 存储所有组合 let mut path: Vec<i32> = vec![]; // 存储当前组合 fn backtrack(start: i32, n: i32, k: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) { if path.len() == k as usize { // 当前组合长度为k，加入结果中 res.push(path.clone()); return; } for i in start..=n { // 枚举可选数字 path.push(i); // 加入当前数字 backtrack(i + 1, n, k, path, res); // 从i+1开始枚举下一个数字 path.pop(); // 撤销当前数字 } } backtrack(1, n, k, &mut path, &mut res); // 从1开始枚举第一个数字 res } fn main() { println!("{:?}", combine(4, 2)); println!("{:?}", combine(1, 1)); }
输出：
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
[[1]]
代码2： 枚举法
fn combine(n: i32, k: i32) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![]; // 存储所有组合 for i in 0..1<<n { // 枚举所有二进制数 let mut path: Vec<i32> = vec![]; // 存储当前组合 for j in 1..=n { // 枚举n个数字 if i & 1 << j-1 != 0 { // 当前数字被选中 path.push(j); } } if path.len() == k as usize { // 当前组合长度为k，加入结果中 res.push(path); } } res } fn main() { println!("{:?}", combine(4, 2)); println!("{:?}", combine(1, 1)); }
78. 子集 Subsets
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
代码1：回溯法
fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![]; // 存储所有子集 fn back_track (index: usize, path: &mut Vec<i32>, nums: &[i32], res: &mut Vec<Vec<i32>>) { // 递归枚举所有子集 let tmp: Vec<i32> = path.to_vec(); // 将当前组合复制到临时数组中 let n = nums.len(); res.push(tmp); // 加入当前子集 for i in index..n { // 枚举每个数字 path.push(nums[i]); // 加入数字构成新的组合 back_track (i+1, path, nums, res); // 递归枚举下一位数字 path.pop(); // 移除数字 } } back_track (0, &mut vec![], &nums, &mut res); // 从空集开始递归枚举所有子集 res } fn main() { let nums: Vec<i32> = vec![1, 2, 3]; println!("{:?}", subsets(nums)); let nums: Vec<i32> = vec![0]; println!("{:?}", subsets(nums)); }
输出：
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [0]]
代码2： 循环枚举
fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![vec![]]; // 初始为空集 for i in 0..nums.len() { // 枚举每个数字 for sub in res.clone() { // 枚举已有的子集 let mut temp = sub.clone(); temp.push(nums[i]); // 加入当前数字 res.push(temp); // 加入新的子集 } } res } fn main() { let nums: Vec<i32> = vec![1, 2, 3]; println!("{:?}", subsets(nums)); let nums: Vec<i32> = vec![0]; println!("{:?}", subsets(nums)); }
输出：
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [0]]
代码3： 位运算
fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut res: Vec<Vec<i32>> = vec![]; // 存储所有子集 let n = nums.len(); for i in 0..(1 << n) { // 枚举所有二进制数 let mut path: Vec<i32> = vec![]; // 存储当前子集 for j in 0..n { // 枚举n个数字 if i & (1 << j) != 0 { // 当前数字被选中 path.push(nums[j]); } } res.push(path); // 加入当前子集 } res } fn main() { let nums: Vec<i32> = vec![1, 2, 3]; println!("{:?}", subsets(nums)); let nums: Vec<i32> = vec![0]; println!("{:?}", subsets(nums)); }
输出：
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [0]]
🌟每日一练刷题专栏🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
