Rust每日一练(Leetday0014) 组合总和II、缺失正数、接雨水

目录

40. 组合总和 II  Combination Sum II  🌟🌟

41. 缺失的第一个正数 First Missing Positive  🌟🌟🌟

42. 接雨水 Trapping Rain Water  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

40. 组合总和 II Combination Sum II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

代码： 回溯法

fn combination_sum_ii(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {let mut res = Vec::new();if candidates.len() > 0 {let mut candidates = candidates;candidates.sort();backtrack(&candidates, 0, target, &mut Vec::new(), &mut res);}res
}fn backtrack(candidates: &Vec<i32>, start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {if target == 0 {res.push(path.clone());return;}for i in start..candidates.len() {if i > start && candidates[i] == candidates[i - 1] {continue;}let cur = candidates[i];if cur <= target {path.push(cur);backtrack(candidates, i + 1, target - cur, path, res);path.pop();} else {break;}}
}fn main() {let candidates = vec![10, 1, 2, 7, 6, 1, 5];println!("{:?}", combination_sum_ii(candidates, 8));let candidates = vec![2, 5, 2, 1, 2];println!("{:?}", combination_sum_ii(candidates, 5));
}

输出：

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]

---

41. 缺失的第一个正数 First Missing Positive

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

代码1：

fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();let mut nums = nums;// 将数组中的每个数放到对应的位置上for i in 0..n {while nums[i] > 0 && nums[i] <= n as i32 && nums[nums[i] as usize - 1] != nums[i] {let j = nums[i] as usize - 1;nums.swap(i, j);}}// 遍历一遍数组，找到第一个位置上的数不是对应的数for i in 0..n {if nums[i] != i as i32 + 1 {return i as i32 + 1;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}

 代码2：

use std::collections::HashSet;fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();let mut set = HashSet::new();for v in nums {set.insert(v);}for i in 1..=n {if !set.contains(&(i as i32)) {return i as i32;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}

 代码3：

fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();// 将数组中所有小于等于0的数和大于n的数都替换成n+1let mut nums = nums.into_iter().map(|x| if x <= 0 || x > n as i32 { n as i32 + 1 } else { x }).collect::<Vec<i32>>();// 使用哈希表记录数组中出现的正整数for i in 0..n {let num = nums[i].abs();if num <= n as i32 {nums[(num - 1) as usize] = -nums[(num - 1) as usize].abs();}}// 从1开始遍历正整数，找到第一个没出现的即可for i in 1..=n {if nums[(i - 1) as usize] > 0 {return i as i32;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}

输出：

3
2
1

---

42. 接雨水 Trapping Rain Water

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

代码1： 双指针

fn trap(height: Vec<i32>) -> i32 {let n = height.len();if n == 0 {return 0;}let (mut left, mut right) = (0, n - 1); // 双指针let (mut max_left, mut max_right) = (0, 0); // 最高的柱子高度let mut res = 0;while left < right { // 当 left 和 right 相遇时结束循环if height[left] < height[right] {max_left = max(max_left, height[left]);res += max_left - height[left];left += 1;} else {max_right = max(max_right, height[right]);res += max_right - height[right];right -= 1;}}return res;
}fn max(a: i32, b: i32) -> i32 {if a > b {return a;}return b;
}fn main() {let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];println!("{}", trap(height));let height = vec![4, 2, 0, 3, 2, 5];println!("{}", trap(height));
}

输出：

6
9

方法2： 循环暴力

fn trap(height: Vec<i32>) -> i32 {let n = height.len();if n == 0 {return 0;}let mut left: Vec<i32> = vec![0; n]; // 记录左边最高的柱子高度let mut right: Vec<i32> = vec![0; n]; // 记录右边最高的柱子高度left[0] = height[0];for i in 1..n {left[i] = max(left[i-1], height[i]);}right[n-1] = height[n-1];for i in (0..n-1).rev() {right[i] = max(right[i+1], height[i]);}let mut res = 0;for i in 1..n-1 {res += min(left[i], right[i]) - height[i];}return res;
}fn max(a: i32, b: i32) -> i32 {if a > b {return a;}return b;
}fn min(a: i32, b: i32) -> i32 {if a < b {return a;}return b;
}fn main() {let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];println!("{}", trap(height));let height = vec![4, 2, 0, 3, 2, 5];println!("{}", trap(height));
}

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：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）暂停更