Golang每日一练(leetDay0019)

目录

55. 跳跃游戏 Jump Game  🌟🌟

56. 合并区间 Mmerge Intervals  🌟🌟

57. 插入区间 Insert Interval  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

55. 跳跃游戏 Jump Game

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i] <= 10^5

代码1：

贪心算法，记录每个位置能跳到的最远距离，如果当前位置已经超过了当前能跳到的最远距离，说明无法到达终点，返回 false。 

func canJump(nums []int) bool {n := len(nums)maxPos := 0for i := 0; i < n; i++ {if i > maxPos {return false}maxPos = max(maxPos, i+nums[i])}return true
}
func max(a, b int) int {if a > b {return a}return b
}

 代码2：

回溯算法，从第一个位置开始，依次尝试跳到后面的每一个位置，如果遇到无法跳到的位置，则回溯到上一个位置，直到跳到终点或无法回溯为止。

func canJump(nums []int) bool {return backtrack(nums, 0)
}
func backtrack(nums []int, pos int) bool {if pos == len(nums)-1 {return true}furthestJump := min(pos+nums[pos], len(nums)-1)for nextPos := furthestJump; nextPos > pos; nextPos-- {if backtrack(nums, nextPos) {return true}}return false
}
func min(a, b int) int {if a < b {return a}return b
}

 代码3：

动态规划，定义状态 dp[i] 表示能否从起点跳到第 i 个位置。转移方程为 dp[i] = dp[j] && j + nums[j] >= i，其中 j 为能够跳到的位置。

func canJump(nums []int) bool {n := len(nums)maxPos := 0for i := 0; i < n; i++ {if i > maxPos {return false}maxPos = max(maxPos, i+nums[i])}return true
}
func max(a, b int) int {if a > b {return a}return b
}

 代码4：

反向贪心算法，从终点开始向前遍历，记录能够跳到终点的最小位置，如果当前位置能够跳到这个最小位置，则更新最小位置，最后判断起点是否能够跳到这个最小位置即可。 

func canJump(nums []int) bool {n := len(nums)lastPos := n - 1for i := n - 2; i >= 0; i-- {if i+nums[i] >= lastPos {lastPos = i}}return lastPos == 0
}

---

56. 合并区间 Mmerge Intervals

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

代码1：

排序 + 双指针 首先将区间按照起始位置从小到大排序，然后使用双指针对区间进行合并。具体来说，定义左右指针 left 和 right，初始时 left 指向第一个区间的起始位置，right 指向第一个区间的结束位置。然后依次遍历每个区间，如果当前区间的起始位置小于等于 right，则将 right 更新为当前区间的结束位置，否则将当前区间的起始位置和结束位置作为一个新区间加入结果集，并将左右指针更新为当前区间的起始位置和结束位置。最后将最后一个区间加入结果集即可。

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := [][]int{}left, right := intervals[0][0], intervals[0][1]for i := 1; i < len(intervals); i++ {if intervals[i][0] <= right {if intervals[i][1] > right {right = intervals[i][1]}} else {res = append(res, []int{left, right})left, right = intervals[i][0], intervals[i][1]}}res = append(res, []int{left, right})return res
}

代码2：

排序 + 栈 首先将区间按照起始位置从小到大排序，然后使用栈对区间进行合并。具体来说，依次遍历每个区间，如果当前区间的起始位置小于等于栈顶区间的结束位置，则将栈顶区间的结束位置更新为当前区间的结束位置，否则将当前区间加入栈中。最后将栈中所有区间加入结果集即可。 

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})stack := [][]int{}for _, interval := range intervals {if len(stack) == 0 || interval[0] > stack[len(stack)-1][1] {stack = append(stack, interval)} else {stack[len(stack)-1][1] = max(stack[len(stack)-1][1], interval[1])}}return stack
}
func max(a, b int) int {if a > b {return a}return b
}

 代码3：

排序 + 遍历 首先将区间按照起始位置从小到大排序，然后依次遍历每个区间，如果当前区间的起始位置小于等于结果集中最后一个区间的结束位置，则将结果集中最后一个区间的结束位置更新为当前区间的结束位置，否则将当前区间加入结果集。最后输出结果集即可。 

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := [][]int{}for _, interval := range intervals {if len(res) == 0 || interval[0] > res[len(res)-1][1] {res = append(res, interval)} else {res[len(res)-1][1] = max(res[len(res)-1][1], interval[1])}}return res
}
func max(a, b int) int {if a > b {return a}return b
}

---

57. 插入区间 Insert Interval

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
• intervals 根据 intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10^5

代码1：

二分查找  先通过二分查找找到新区间需要插入的位置，然后按照方法一的方式插入新区间并合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置left := 0right := n - 1for left <= right {mid := left + (right-left)/2if intervals[mid][1] < newInterval[0] {left = mid + 1} else {right = mid - 1}}insertIndex := left// 插入新区间i := 0for i < insertIndex {res = append(res, intervals[i])i++}if i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并重叠的区间for i < n {if intervals[i][0] <= res[len(res)-1][1] {res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])} else {res = append(res, intervals[i])}i++}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}

 代码2：

双指针 由于区间列表是按照起始端点排序的，因此可以使用双指针的方法，分别找到新区间需要插入的位置和合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置i := 0for i < n && intervals[i][1] < newInterval[0] {res = append(res, intervals[i])i++}// 合并重叠的区间for i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并剩余的区间for i < n {res = append(res, intervals[i])i++}// 再次合并重叠的区间n = len(res)i = 1for i < n {if res[i][0] <= res[i-1][1] {res[i-1][1] = max(res[i][1], res[i-1][1])res = append(res[:i], res[i+1:]...)n--} else {i++}}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}

 代码3：

暴力插入 遍历区间列表，找到新区间需要插入的位置，然后插入新区间。再遍历一遍区间列表，合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置i := 0for i < n && intervals[i][1] < newInterval[0] {res = append(res, intervals[i])i++}// 插入新区间if i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并重叠的区间for i < n {if intervals[i][0] <= res[len(res)-1][1] {res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])} else {res = append(res, intervals[i])}i++}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}

---

🌟 每日一练刷题专栏 🌟

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

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

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

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

☸ 主页：https://hannyang.blog.csdn.net/ 

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏