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
代码1： 回溯法
package main import ( "fmt" "sort" ) func combinationSum2(candidates []int, target int) [][]int { res := [][]int{} if len(candidates) > 0 { sort.Ints(candidates) backtrack(candidates, 0, target, []int{}, &res) } return res } func backtrack(candidates []int, start, target int, path []int, res *[][]int) { if target == 0 { temp := make([]int, len(path)) copy(temp, path) *res = append(*res, temp) return } for i := start; i < len(candidates) && candidates[i] <= target; i++ { if i > start && candidates[i] == candidates[i-1] { continue } path = append(path, candidates[i]) backtrack(candidates, i+1, target-candidates[i], path, res) path = path[:len(path)-1] } } func main() { candidates := []int{10, 1, 2, 7, 6, 1, 5} fmt.Println(combinationSum2(candidates, 8)) candidates2 := []int{2, 5, 2, 1, 2} fmt.Println(combinationSum2(candidates2, 5)) }
输出：
[[1 1 6] [1 2 5] [1 7] [2 6]]
[[1 2 2] [5]]
代码2：动态规划
package main import ( "fmt" "sort" ) func combinationSum2(candidates []int, target int) [][]int { if len(candidates) == 0 { return [][]int{} } sort.Ints(candidates) dp := make([][][]int, target+1) dp[0] = [][]int{{}} for i := 0; i < len(candidates); i++ { for j := target; j >= candidates[i]; j-- { if dp[j-candidates[i]] != nil { temp := make([][]int, len(dp[j-candidates[i]])) for k := 0; k < len(dp[j-candidates[i]]); k++ { temp[k] = make([]int, len(dp[j-candidates[i]][k])) copy(temp[k], dp[j-candidates[i]][k]) } for k := 0; k < len(temp); k++ { if len(temp[k]) > 0 && temp[k][len(temp[k])-1] > candidates[i] { continue } path := append(temp[k], candidates[i]) dp[j] = append(dp[j], path) } } } } return RemoveDuplicates(dp[target]) } func RemoveDuplicates(arr [][]int) [][]int { m := make(map[string]int) for _, a := range arr { s := fmt.Sprintf("%v", a) m[s]++ } res := make([][]int, 0, len(m)) for _, a := range arr { s := fmt.Sprintf("%v", a) if m[s] == 1 { res = append(res, a) } m[s]-- } return res } func main() { candidates := []int{10, 1, 2, 7, 6, 1, 5} fmt.Println(combinationSum2(candidates, 8)) candidates2 := []int{2, 5, 2, 1, 2} fmt.Println(combinationSum2(candidates2, 5)) }
动态规划的结果有重复组合， 需要另外去重RemoveDuplicates。
输出：
[[1 2 5] [1 1 6] [2 6] [1 7]]
[[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：
package main import "fmt" func firstMissingPositive(nums []int) int { n := len(nums) // 将数组中的每个数放到对应的位置上 for i := 0; i < n; i++ { for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] { nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] } } // 遍历一遍数组，找到第一个位置上的数不是对应的数 for i := 0; i < n; i++ { if nums[i] != i+1 { return i + 1 } } return n + 1 } func main() { nums := []int{1, 2, 0} fmt.Println(firstMissingPositive(nums)) nums1 := []int{3, 4, -1, 1} fmt.Println(firstMissingPositive(nums1)) nums2 := []int{7, 8, 9, 11, 12} fmt.Println(firstMissingPositive(nums2)) }
代码2：
package main import "fmt" func firstMissingPositive(nums []int) int { n := len(nums) Map := make(map[int]int, n) for _, v := range nums { Map[v] = v } for i := 0; i < n; i++ { if _, ok := Map[i+1]; !ok { return i + 1 } } return n + 1 } func main() { nums := []int{1, 2, 0} fmt.Println(firstMissingPositive(nums)) nums1 := []int{3, 4, -1, 1} fmt.Println(firstMissingPositive(nums1)) nums2 := []int{7, 8, 9, 11, 12} fmt.Println(firstMissingPositive(nums2)) }
代码3：
package main import "fmt" func firstMissingPositive(nums []int) int { n := len(nums) // 将数组中所有小于等于0的数和大于n的数都替换成n+1 for i := 0; i < n; i++ { if nums[i] <= 0 || nums[i] > n { nums[i] = n + 1 } } // 使用哈希表记录数组中出现的正整数 for i := 0; i < n; i++ { num := abs(nums[i]) if num <= n { nums[num-1] = -abs(nums[num-1]) } } // 从1开始遍历正整数，找到第一个没出现的即可 for i := 1; i <= n; i++ { if nums[i-1] > 0 { return i } } return n + 1 } func abs(x int) int { if x < 0 { return -x } return x } func main() { nums := []int{1, 2, 0} fmt.Println(firstMissingPositive(nums)) nums1 := []int{3, 4, -1, 1} fmt.Println(firstMissingPositive(nums1)) nums2 := []int{7, 8, 9, 11, 12} fmt.Println(firstMissingPositive(nums2)) }
输出：
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： 双指针
package main import ( "fmt" ) func trap(height []int) int { n := len(height) if n == 0 { return 0 } left, right := 0, n-1 // 双指针 maxLeft, maxRight := 0, 0 // 最高的柱子高度 res := 0 for left < right { // 当 left 和 right 相遇时结束循环 if height[left] < height[right] { maxLeft = max(maxLeft, height[left]) res += maxLeft - height[left] left++ } else { maxRight = max(maxRight, height[right]) res += maxRight - height[right] right-- } } return res } func max(a, b int) int { if a > b { return a } return b } func main() { height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1} fmt.Println(trap(height)) height2 := []int{4, 2, 0, 3, 2, 5} fmt.Println(trap(height2)) }
输出：
6
9
方法2： 循环暴力
package main import ( "fmt" ) func trap(height []int) int { n := len(height) if n == 0 { return 0 } left := make([]int, n) // 记录左边最高的柱子高度 right := make([]int, n) // 记录右边最高的柱子高度 left[0] = height[0] for i := 1; i < n; i++ { left[i] = max(left[i-1], height[i]) } right[n-1] = height[n-1] for i := n - 2; i >= 0; i-- { right[i] = max(right[i+1], height[i]) } res := 0 for i := 1; i < n-1; i++ { res -= max(-left[i], -right[i]) + height[i] // -max(-a,-b) == min(a,b) } return res } func max(a, b int) int { if a > b { return a } return b } func main() { height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1} fmt.Println(trap(height)) height2 := []int{4, 2, 0, 3, 2, 5} fmt.Println(trap(height2)) }
