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+1 let 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)); }
