目录
76. 最小覆盖子串 Minimum Window Substring 🌟🌟🌟
77. 组合 Combinations 🌟🌟
78. 子集 Subsets 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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）暂停更 |
