LeetCode - topics: Array (Part II)

54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

1 2	Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

Example 2:

1 2	Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution:

func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return []int{}
	}
	result := make([]int, 0)
	endL, endC, startL, startC := len(matrix)-1, len(matrix[0])-1, 0, 0
	count, moveL, moveC := 1, 0, 1
	curL, curC := 0, 0

	for count <= len(matrix)*len(matrix[0]) {
		if moveC != 0 {
			if moveC > 0 {
				for ; curC <= endC; curC++ {
					result = append(result, matrix[curL][curC])
					count++
				}
				curC--
				curL++
				startL, moveL, moveC = curL, 1, 0
			} else {
				for ; curC >= startC; curC-- {
					result = append(result, matrix[curL][curC])
					count++
				}
				curC++
				curL--
				endL, moveL, moveC = curL, -1, 0
			}
		} else if moveL != 0 {
			if moveL > 0 {
				for ; curL <= endL; curL++ {
					result = append(result, matrix[curL][curC])
					count++
				}
				curL--
				curC--
				endC, moveL, moveC = curC, 0, -1

			} else {
				for ; curL >= startL; curL-- {
					result = append(result, matrix[curL][curC])
					count++
				}
				curC++
				curL++
				startC, moveL, moveC = curC, 0, 1
			}
		}s the integer 123.

Note:

用的笨方法，操作题，注意好上下左右的变化，把握好重复行列的处理

55. Jump Game

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

1
2
3

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Constraints:

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

Solution:

func canJump(nums []int) bool {
	if len(nums) == 1 {
		return true
	}
	curFar, curEnd := 0, 0
	for i, v := range nums {
		if curEnd >= len(nums)-1 {
			return true
		}
		curFar = max(curFar, i+v)
		if i == curEnd {
			curEnd = curFar
		}
	}
	return false
}
func max(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].

Solution:

func merge(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
}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

Note:

解决此类问题，首先将每个小分段的顺序按照起始点的大小来排序，随后判断相邻两个位置，后一个的起始点是否小于等于前一个的末尾点，一旦小于即有交叉，一有交叉就要先判断两个集合的end是什么(因为start已经按照顺序排好了，start必是前一个分段的起点)，通过max()函数进行比较收尾，这两个分段的merge就结束了，依次进行下去，即可完成所有merge

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

1 2	Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Example 2:

1
2
3

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].

Solution:

func insert(intervals [][]int, newInterval []int) [][]int {
	if len(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
}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

Note:

[56. Merge Intervals](#56. Merge Intervals)兄弟题，与上一题的区别在于，本次需要插入新的元素，而原本的元素集合是排序好的，所以新元素需要处理好位置，成功插入之后要做的事就如同上一题一样

59. Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

1 2	Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]

Solution:

func generateMatrix(n int) [][]int {
	if n == 1 {
		return [][]int{{1}}
	}
	result := make([][]int, n)
	for i := 0; i < n; i++ {
		result[i] = make([]int, n)
	}
	endL, endC, startL, startC := n-1, n-1, 0, 0
	count, moveL, moveC := 1, 0, 1
	curL, curC := 0, 0

	for count <= n*n {
		if moveC != 0 {
			if moveC > 0 {
				for ; curC <= endC; curC++ {
					result[curL][curC] = count
					count++
				}
				curC--
				curL++
				startL, moveL, moveC = curL, 1, 0
			} else {
				for ; curC >= startC; curC-- {
					result[curL][curC] = count
					count++
				}
				curC++
				curL--
				endL, moveL, moveC = curL, -1, 0
			}
		} else if moveL != 0 {
			if moveL > 0 {
				for ; curL <= endL; curL++ {
					result[curL][curC] = count
					count++
				}
				curL--
				curC--
				endC, moveL, moveC = curC, 0, -1

			} else {
				for ; curL >= startL; curL-- {
					result[curL][curC] = count
					count++
				}
				curC++
				curL++
				startC, moveL, moveC = curC, 0, 1
			}
		}
	}
	return result
}

Note:

[54. Spiral Matrix](#54. Spiral Matrix)兄弟题，上一题按照漩涡顺序输出值，这一题逆向而行，循环复现漩涡顺序的同时把当前走过的count赋值为当前位置的值即可

62. Unique Paths

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:

func uniquePaths(m int, n int) int {
	if n == 0 || m == 0 {
		return 0
	}
	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]
}

Note:

本题解法有三种，常规解法如上，一开始采用深搜，结果超时。后考虑题目特性，只能向右和向下，因此每一格至多只能由他的左方和上方到达，因此，可以首先将第一行和第一列的每格赋值为1，因为到达他们只可能有一种路径（即一直向下和一直向左），之后每一格的值都由左和上两个格子的和来决定。如第二行第二列，他的值由一行二列和二行一列相加得2，即如果由起点（一行一列）到达此处的路径有两条。那么相应的二行三列的值就是1+2=3。

另一思考方式则为数学方法，具体可见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:

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

Solution:

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if (len(obstacleGrid) != 0 && obstacleGrid[0][0] == 1) || obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1 {
		return 0
	}

	mark := 1
	for i := 0; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			obstacleGrid[i][0] = 0
			mark = 0
		}
		obstacleGrid[i][0] = mark
	}
	mark = 1

	for j := 1; j < len(obstacleGrid[0]); j++ {
		if obstacleGrid[0][j] == 1 {
			obstacleGrid[0][j] = 0
			mark = 0
		}
		obstacleGrid[0][j] = mark
	}

	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[i]); j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
				continue
			}
			obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
		}
	}
	return obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}

Note:

[62. Unique Paths](#62. Unique Paths)兄弟题，本题有阻碍物，所以在初始化的时候需要考虑。第一行和第一列赋初值的时候要判断是否有阻碍物，如果有，则该行或者该列后续的格子值全部为0(因为无法向左走和向上走)。随后开始与上题一样的加和流程，注意障碍物也会出现在此时，所以也要加一个判断，即如果是障碍物，那么这个格子的值是0，并且跳过本次循环。

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

1
2
3

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Solution:

func minPathSum(grid [][]int) int {

	for i := 1; i < len(grid); i++ {
		grid[i][0] += grid[i-1][0]
	}

	for j := 1; j < len(grid[0]); j++ {
		grid[0][j] += grid[0][j-1]
	}

	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]
}
func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

Note:

依旧是上两题同类型题目，本题每格都有初始值，在达到终点时判断路径上经过所有格子的值之和最小的路径。首先依旧是对第一行第一列的处理，进行累加，随后进行例行步骤，不过此时需要进行筛选，即遍历到某个新格子的时候，它需要判断上方和左方当前的累加值哪个小，得到min值，随后将自己的值赋值为原本值+min值。

66. Plus One

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Solution:

func plusOne(digits []int) []int {
	i := len(digits) - 1
	for ; i >= 0; i-- {
		digits[i] = (digits[i] + 1) % 10
		if digits[i] != 0 {
			break
		}
	}
	if i < 0 {
		digits = append([]int{1}, digits...)
	}
	return digits
}

Note:

简单题，注意进位和补1

73. Set Matrix Zeroes

Given an *m* x *n* matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

A straight forward solution using O(m**n) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Example 1:

1 2	Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Solution:

func setZeroes(matrix [][]int) {
	visR := make(map[int]int)
	visC := make(map[int]int)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if (matrix[i][j]) == 0 {
				visR[i] = 1
				visC[j] = 1
			}
		}
	}

	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if visR[i] == 1 || visC[j] == 1 {
				matrix[i][j] = 0
			}
		}
	}
}

Note:

笨方法，先用vis数组监视0元素出现的行列，然后在进行for循环进行0覆盖

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

1 2	Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Solution:

func searchMatrix(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 {
					return true
				} else if matrix[i][mid] > target {
					r = mid - 1
				} else {
					l = mid + 1
				}
			}
			break
		}
	}
	return false
}

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?

Example 1:

1 2	Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Solution:

func sortColors(nums []int) {
	countR, countW, countB := 0, 0, 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			countR++
		} else if nums[i] == 1 {
			countW++
		} else {
			countB++
		}
	}
	fill(&nums, 0, countR, 0)
	fill(&nums, countR, countR+countW, 1)
	fill(&nums, countR+countW, countR+countW+countB, 2)
}
func fill(nums *[]int, start, end int, color int) {
	for i := start; i < end; i++ {
		(*nums)[i] = color
	}
}

Note:

一共就三个元素，只要统计一下他们一共有多少个，再按照顺序重新赋值即可

78. Subsets

Given an integer array nums, return all possible subsets (the power set).

The solution set must not contain duplicate subsets.

Example 1:

1 2	Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution:

func subsets(nums []int) [][]int {
	var result [][]int
	var current []int
	result = append(result, []int{})
	backTrace(&result, 0, nums, current)
	return result

}
func backTrace(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]
	}
}

# bit manipulation
class Solution:
    def subsets(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

Note:

直观想到backtrace直接搞定，看提示后发现还有位操作的方法leet_nik_Discuss

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 }

Page View

Prev Home Next

LeetCode-Array-II

LeetCode - topics: Array (Part II)

54. Spiral Matrix

Solution:

Note:

55. Jump Game

Solution:

Note:

56. Merge Intervals

Solution:

Note:

57. Insert Interval

Solution:

Note:

59. Spiral Matrix II

Solution:

Note:

62. Unique Paths

Solution:

Note:

63. Unique Paths II

Solution:

Note:

64. Minimum Path Sum

Solution:

Note:

66. Plus One

Solution:

Note:

73. Set Matrix Zeroes

Solution:

Note:

74. Search a 2D Matrix

Solution:

Note:

75. Sort Colors

Solution:

Note:

78. Subsets

Solution:

Note: