目录
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
let t: Vec
if s.len() < t.len() {
return String::new();
}
let mut need: HashMap
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
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::
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
let mut res: Vec
let mut path: Vec
fn backtrack(start: i32, n: i32, k: i32, path: &mut Vec
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
let mut res: Vec
for i in 0..1< let mut path: 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 let mut res: Vec fn back_track (index: usize, path: &mut Vec let tmp: 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 println!("{:?}", subsets(nums)); let nums: Vec println!("{:?}", subsets(nums)); } 输出： [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] [[], [0]] 代码2： 循环枚举 fn subsets(nums: Vec let mut res: 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 println!("{:?}", subsets(nums)); let nums: Vec println!("{:?}", subsets(nums)); } 输出： [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] [[], [0]] 代码3： 位运算 fn subsets(nums: Vec let mut res: Vec let n = nums.len(); for i in 0..(1 << n) { // 枚举所有二进制数 let mut path: 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 println!("{:?}", subsets(nums)); let nums: Vec 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）暂停更 精彩内容
您阅读本篇文章共花了：
发表评论