funccanJump(nums []int)bool { iflen(nums) == 1 { returntrue } curFar, curEnd := 0, 0 for i, v := range nums { if curEnd >= len(nums)-1 { returntrue } curFar = max(curFar, i+v) if i == curEnd { curEnd = curFar } } returnfalse } funcmax(a int, b int)int { if a > b { return a } return b }
Note:
[45.Jump Game II](#45. Jump Game II)兄弟题,上一题求跳跃步数,这一条只要判断最远可以跳出(>=)即可判断能够跳到终点
56. Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
1 2 3
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
funcmerge(intervals [][]int) [][]int { sort.Slice(intervals, func(i, j int)bool { return intervals[i][0] < intervals[j][0] }) var res [][]int for i := 0; i < len(intervals); i++ { start, end := intervals[i][0], intervals[i][1] j := i + 1 for ; j < len(intervals) && intervals[j][0] <= end; j++ { end = max(end, intervals[j][1]) } res = append(res, []int{start, end}) i = j - 1 } return res } funcmax(a int, b int)int { if a > b { return a } return b }
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
funcinsert(intervals [][]int, newInterval []int) [][]int { iflen(intervals) == 0 { return [][]int{newInterval} } var res [][]int inserOK := false for i, v := range intervals { if v[0] > newInterval[0] { intervals = append(intervals[:i], append([][]int{newInterval}, intervals[i:]...)...) inserOK = true break } } if !inserOK { intervals = append(intervals, newInterval) } for i := 0; i < len(intervals); i++ { start := intervals[i][0] end := intervals[i][1] j := i + 1 for ; j < len(intervals) && intervals[j][0] <= end; j++ { end = max(end, intervals[j][1]) } res = append(res, []int{start, end}) i = j - 1 } return res } funcmax(a int, b int)int { if a > b { return a } return b }
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Example 1:
1 2
Input: m = 3, n = 7 Output: 28
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
funcuniquePaths(m int, n int)int { if n == 0 || m == 0 { return0 } mat := make([]int, n) for i := 0; i < n; i++ { mat[i] = 1 } for i := 1; i < m; i++ { for j := 1; j < n; j++ { mat[j] += mat[j-1] } } return mat[n-1] }
另一思考方式则为数学方法,具体可见Art of Problem Solving: Counting Paths on a Grid。大体思想是,由于方向确定,范围确定,所以总步长确定,即每条到达终点的路径一共要走多少步,相应的,每条路径中向下的步数和向右的步数也是确定值,所以就变成了组合问题,即在M步里,一共以何种顺序出现确定的i步的向左右或j步的向右走,即C(M,i)或C(M,j)
63. Unique Paths II
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space is marked as 1 and 0 respectively in the grid.
Example 1:
1 2 3 4 5 6
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right
for i := 1; i < len(grid); i++ { for j := 1; j < len(grid[i]); j++ { grid[i][j] += min(grid[i-1][j], grid[i][j-1]) } } return grid[len(grid)-1][len(grid[0])-1] } funcmin(a int, b int)int { if a > b { return b } return a }
funcsearchMatrix(matrix [][]int, target int)bool { for i := 0; i < len(matrix); i++ { if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target { l, r := 0, len(matrix[i])-1 for l <= r { mid := (l + r) >> 1 if matrix[i][mid] == target { returntrue } elseif matrix[i][mid] > target { r = mid - 1 } else { l = mid + 1 } } break } } returnfalse }
Note:
简单题,直接方法判断target的范围,找到对应范围后对该范围二分查找
75. Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Follow up:
Could you solve this problem without using the library’s sort function?
Could you come up with a one-pass algorithm using only O(1) constant space?
funcsubsets(nums []int) [][]int { var result [][]int var current []int result = append(result, []int{}) backTrace(&result, 0, nums, current) return result
} funcbackTrace(result *[][]int, start int, nums []int, current []int) { if start <= len(nums) && current != nil { temp := make([]int, len(current)) copy(temp, current) *result = append(*result, temp) } for i := start; i < len(nums); i++ { current = append(current, nums[i]) backTrace(result, i+1, nums, current) current = current[:len(current)-1] } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# bit manipulation classSolution: defsubsets(self, nums): result = list() n = len(nums) for i in range(pow(2, n)): lst = list() for j in range(n): bit = i & 1 if bit: lst.append(nums[j]) i >>= 1 result.append(lst) return result
n=3 [1,2,3] 2**3 0) 0 0 0 -> Dont take 3 , Dont take 2 , Dont take 1 = { } 1) 0 0 1 -> Dont take 3 , Dont take 2 , take 1 = {1 } 2) 0 1 0 -> Dont take 3 , take 2 , Dont take 1 = { 2 } 3) 0 1 1 -> Dont take 3 , take 2 , take 1 = { 1 , 2 } 4) 1 0 0 -> take 3 , Dont take 2 , Dont take 1 = { 3 } 5) 1 0 1 -> take 3 , Dont take 2 , take 1 = { 1 , 3 } 6) 1 1 0 -> take 3 , take 2 , Dont take 1 = { 2 , 3 } 7) 1 1 1 -> take 3 , take 2 , take 1 = { 1 , 2 , 3 }