当前位置： 首页 > article >正文

Golang每日一练(leetDay0014)

article 2024/11/15 1:14:06

目录

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

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

42. 接雨水 Trapping Rain Water  🌟🌟🌟

🌟 每日一练刷题专栏 🌟

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

代码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))
}

🌟 每日一练刷题专栏 🌟

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

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

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

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

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


http://www.kler.cn/a/2783.html

相关文章：

  • 今日 AI 简报 | 开源 RAG 文本分块库、AI代理自动化软件开发框架、多模态统一生成框架、在线图像背景移除等
  • 陪诊问诊APP开发实战：基于互联网医院系统源码的搭建详解
  • 如何使用ffmpeg命令行进行录屏
  • Linux如何更优质调节系统性能
  • 数据挖掘（九）
  • Vue 项目打包后环境变量丢失问题（清除缓存），区分.env和.env.*文件
  • MySQL主从复制
  • 【设计模式】23种设计模式之七大原则
  • Docker6种网络配置详解，网络模式应该这么选
  • 6.S081——Lab1——Xv6 and Unix utilities
  • 7个Python中的隐藏小技巧分享
  • 算法刷题总结 (二) 回溯与深广搜算法
  • 前端处理并发的最佳实践
  • 《网络安全入门到精通》 - 2.1 - Windows基础 - DOS命令Windows防火墙Windows共享文件
  • 【C++】引用详细解析
  • 进阶C语言：指针和数组训练题
  • 第四章 保护模式入门
  • XCIE-HUAWEI-超级完整的BGP-6-路由选路（三）+团体属性+BGP选路总结
  • Python流星雨代码
  • 算法设计与分析 实验五 贪心算法
  • Apache Kafka JNDI注入(CVE-2023-25194)漏洞复现浅析
  • JS数组reduce()方法详解及高级技巧
  • typedef uint8_t u8；（stm32数据类型）
  • springboot+mybatis plus+vue+elementui+axios 表格分页查询demo
  • # 机械设备故障的靶向迁移诊断与OpenAI分析
  • 把星巴克吓出冷汗，6580家门店扭亏为盈