早起刷题（Day 2）

LeetCode63. 不同路径 II

#动态规划

题目描述

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

解题思路

(1). 采用二维递归的思路，本题是LeetCode62. 不同路径的变种，实际上是一道题；
(2). 在处理初始条件（第一行和第一列）遇到障碍物时，障碍物所在的格子即之后的格子都属于不可到达的坐标，退出循环；
(3). 在递归过程中，如果遇到障碍物，直接判断为不可到达 dp[i][j]=0，否则当前格子的路径数等于上面、左面的路径数之和。

时间复杂度

O($N^2$).

解题代码

func uniquePathsWithObstacles(obstacleGrid [][]int) int {

	if obstacleGrid[0][0] == 1 {
		return 0
	}

	m, n := len(obstacleGrid), len(obstacleGrid[0])
	dp := make([][]int, m)
	for i:=0; i<m; i++ {
		dp[i] = make([]int, n)
	}

	for i:=0; i<m; i++ {
		if obstacleGrid[i][0] != 1 {
			dp[i][0] = 1
		} else {
			break
		}
	}

	for i:=1; i<n; i++ {
		if obstacleGrid[0][i] != 1 {
			dp[0][i] = 1
		} else {
			break
		}
	}

	for i:=1; i<m; i++ {
		for j:=1; j<n; j++ {
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0
			} else {
				dp[i][j] = dp[i-1][j]+dp[i][j-1]
			}
		}
	}

	return dp[m-1][n-1]
}

LeetCode498. 对角线遍历

#模拟题

题目描述

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1:

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2:
输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

解题思路

(1). 本题要处理的细节比较多。首先解决边界问题，当 mat 只有一行或一列的时候，直接输出这一行或一列；
(2). 要关注三个和转向有关的情况：direction 用于描述当前前进的方向，向右上是为 true，向左下时为 false；rowHalf 用于描述在右上方向前进到顶格时，接下来是要向右还是向下移动一格；columnHalf 用于描述在左下方向前进到顶格时接下来是要向下还是向右前进一格。实际上就是判断有没有分别在行和列上走过 mat 的一半位置。
(3). 可以观察到，当前位置的坐标和 i+j 在大于等于行号或列号的时候，走到顶格后转向的方向需要发生改变。

时间复杂度

O($M*N$)

解题代码

func findDiagonalOrder(mat [][]int) []int {

	ret := []int{}
	m, n := len(mat), len(mat[0])
	if m == 1 {
		return mat[0]
	} else if n == 1 {
		for i:=0; i<m; i++ {
			ret = append(ret, mat[i][0])
		}
		return ret
	}

	i, j := 0, 0
	direction := true
	rowHalf := true
	columnHalf := true

	for i<m && j<n {
		ret = append(ret, mat[i][j])
		if (i == 0 && direction && rowHalf) || (j == n-1 && direction && !rowHalf) {
			if rowHalf {
				if j < n-1 {
					j++
				} else {
					i++
				}
			} else {
				i++
			}
			direction = false
		} else if (j == 0 && !direction) || (i == m-1 && !direction && !columnHalf) {
			if columnHalf {
				if i < m-1 {
					i++
				} else {
					j++
				}
			} else {
				j++
			}
			direction = true
		} else if direction {
			i--
			j++
		} else {
			i++
			j--
		}
		
		if i+j >= m-1 {
			columnHalf = false
		}
		if i+j >= n-1 {
			rowHalf = false
		}
	}
	
	return ret
}

LeetCode83. 删除排序链表中的重复元素

#链表

题目描述

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

示例 1:
输入：head = [1,1,2]
输出：[1,2]

示例 2:
输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：
链表中节点数目在范围 [0, 300] 内
100 <= Node.val <= 100
题目数据保证链表已经按升序排列

解题思路

(1). 要删除重复的节点，那么就要实时维护三个位置的节点 pre、cur、next，假设要删除 cur，那么删除之后还要将 cur 重新指向 next；
(2). 如果 pre 和 cur 的值不相等，那么同时向后移动一位。

时间复杂度

O(N).

解题代码

/**

* Definition for singly-linked list.

* type ListNode struct {

* 	Val int

* 	Next *ListNode

* }

*/

func deleteDuplicates(head *ListNode) *ListNode {

	if head == nil || head.Next == nil {
		return head
	}

	pre, cur := head, head.Next
	for cur != nil {
		next := cur.Next
		if cur.Val == pre.Val {
			pre.Next = next
			cur = next
		} else {
			pre = cur
			cur = next
		}
	}
	
	return head
}