498. Diagonal Traverse #
题目 #
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:
Note:
The total number of elements of the given matrix will not exceed 10,000.
题目大意 #
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
说明: 给定矩阵中的元素总数不会超过 100000 。
解题思路 #
- 给出一个二维数组，要求按照如图的方式遍历整个数组。
- 这一题用模拟的方式就可以解出来。需要注意的是边界条件：比如二维数组为空，二维数组退化为一行或者一列，退化为一个元素。具体例子见测试用例。
- 解题关键是在判断下一个位置，将矩阵想像成一个X,Y坐标轴。那么可分为以下几种情况， 1、斜角向右上遍历时， 当右上角在坐标轴内， 正常计算 即， x+1(X轴向右移动)， y-1(Y轴向上移动) 当右上角在坐标轴外，那么当前位置只能在 第一行X坐标轴 ，或者 最后一列Y坐标轴 ， 即判断该两种情况下�应该X坐标往右，或者 Y坐标往上 2、同理 斜角向下遍历时 当左下角在坐标轴内，正常计算 即， x-1(X轴向右移动)， y+1(Y轴向下移动) 当左下角在坐标轴外，那么当前位置只能在 第一列Y坐标轴，或者 最后一行X坐标轴， 即判断该两种情况下�应该X坐标往左，或者 Y坐标往下
代码 #
package leetcode
// 解法一
func findDiagonalOrder1(matrix [][]int) []int {
if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
return nil
}
row, col, dir, i, x, y, d := len(matrix), len(matrix[0]), [2][2]int{
{-1, 1},
{1, -1},
}, 0, 0, 0, 0
total := row * col
res := make([]int, total)
for i < total {
for x >= 0 && x < row && y >= 0 && y < col {
res[i] = matrix[x][y]
i++
x += dir[d][0]
y += dir[d][1]
}
d = (d + 1) % 2
if x == row {
x--
y += 2
}
if y == col {
y--
x += 2
}
if x < 0 {
x = 0
}
if y < 0 {
y = 0
}
}
return res
}
// 解法二
func findDiagonalOrder(matrix [][]int) []int {
if len(matrix) == 0 {
return []int{}
}
if len(matrix) == 1 {
return matrix[0]
}
// dir = 0 代表从右上到左下的方向， dir = 1 代表从左下到右上的方向 dir = -1 代表上一次转变了方向
m, n, i, j, dir, res := len(matrix), len(matrix[0]), 0, 0, 0, []int{}
for index := 0; index < m*n; index++ {
if dir == -1 {
if (i == 0 && j < n-1) || (j == n-1) { // 上边界和右边界
i++
if j > 0 {
j--
}
dir = 0
addTraverse(matrix, i, j, &res)
continue
}
if (j == 0 && i < m-1) || (i == m-1) { // 左边界和下边界
if i > 0 {
i--
}
j++
dir = 1
addTraverse(matrix, i, j, &res)
continue
}
}
if i == 0 && j == 0 {
res = append(res, matrix[i][j])
if j < n-1 {
j++
dir = -1
addTraverse(matrix, i, j, &res)
continue
} else {
if i < m-1 {
i++
dir = -1
addTraverse(matrix, i, j, &res)
continue
}
}
}
if i == 0 && j < n-1 { // 上边界
if j < n-1 {
j++
dir = -1
addTraverse(matrix, i, j, &res)
continue
}
}
if j == 0 && i < m-1 { // 左边界
if i < m-1 {
i++
dir = -1
addTraverse(matrix, i, j, &res)
continue
}
}
if j == n-1 { // 右边界
if i < m-1 {
i++
dir = -1
addTraverse(matrix, i, j, &res)
continue
}
}
if i == m-1 { // 下边界
j++
dir = -1
addTraverse(matrix, i, j, &res)
continue
}
if dir == 1 {
i--
j++
addTraverse(matrix, i, j, &res)
continue
}
if dir == 0 {
i++
j--
addTraverse(matrix, i, j, &res)
continue
}
}
return res
}
func addTraverse(matrix [][]int, i, j int, res *[]int) {
if i >= 0 && i <= len(matrix)-1 && j >= 0 && j <= len(matrix[0])-1 {
*res = append(*res, matrix[i][j])
}
}