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。

package main
import "fmt"
func canJump(nums []int) bool {
  n := len(nums)
  maxPos := 0
  for 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
}
func main() {
  nums := []int{2, 3, 1, 1, 4}
  fmt.Println(canJump(nums))
  nums2 := []int{3, 2, 1, 0, 4}
  fmt.Println(canJump(nums2))
}

代码2：

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

package main
import "fmt"
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
}
func main() {
  nums := []int{2, 3, 1, 1, 4}
  fmt.Println(canJump(nums))
  nums2 := []int{3, 2, 1, 0, 4}
  fmt.Println(canJump(nums2))
}

代码3：

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

package main
import "fmt"
func canJump(nums []int) bool {
  n := len(nums)
  dp := make([]bool, n)
  dp[0] = true
  for i := 1; i < n; i++ {
    for j := 0; j < i; j++ {
      if dp[j] && j+nums[j] >= i {
        dp[i] = true
        break
      }
    }
  }
  return dp[n-1]
}
func main() {
  nums := []int{2, 3, 1, 1, 4}
  fmt.Println(canJump(nums))
  nums2 := []int{3, 2, 1, 0, 4}
  fmt.Println(canJump(nums2))
}

代码4：

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

package main
import "fmt"
func canJump(nums []int) bool {
  n := len(nums)
  lastPos := n - 1
  for i := n - 2; i >= 0; i-- {
    if i+nums[i] >= lastPos {
      lastPos = i
    }
  }
  return lastPos == 0
}
func main() {
  nums := []int{2, 3, 1, 1, 4}
  fmt.Println(canJump(nums))
  nums2 := []int{3, 2, 1, 0, 4}
  fmt.Println(canJump(nums2))
}

输出：

true

false

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：

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

1.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 := 0
    right := n - 1
    for left <= right {
        mid := left + (right-left)/2
        if intervals[mid][1] < newInterval[0] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    insertIndex := left
    // 插入新区间
    i := 0
    for 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 := 0
    for 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 = 1
    for 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 := 0
    for 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
}