Rust每日一练(Leetday0026) 最小覆盖子串、组合、子集

　

目录

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^5
• s 和 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 <= 20
• 1 <= 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] <= 10
• nums 中的所有元素 互不相同

代码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）暂停更