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]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105

解题思路

解法一
1.思路：

把下标和相同的放到同一个链表，然后反转和为偶数的链表。

2.优缺点：
不需要判断方向，不需要模拟，不需要判断边界，不需要推导公式。此方法可以很容易在面试的时候写出来。
缺点是使用了额外空间。

3.举例：
3.1 第一步：对于每个和，添加对应数字到链表

[0] -> [1]
[1] -> [2,4]
[2] -> [3,5,7]
[3] -> [6,8]
[4] -> [9]

3.2 第二步，反转

[0] -> [1]
[1] -> [2,4]
[2] -> [7,5,3]
[3] -> [6,8]
[4] -> [9]

3.3 输出

解法二

定义四个方向，每一步都判段是否越界，越界的话就掉头。需要定义如下关键变量

int m = mat.length;

int n = mat[0].length;

int result[] = new int[m * n];

int i = 0, j = 0;

int dirct[][] = new int[][] { { 0, 1 }, { 1, -1 }, { 1, 0 }, { -1, 1 } };

boolean forword = true;

boolean change = false;

result[0] = mat[0][0];

代码实现

解法一

/**
Ideas:
We just consider the sum of index (i,j).
Add each element of sum to map, and then we need to reverse list.

Time: O(M*N)
Space O(M*N)
 */
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if(mat == null || mat.length == 0) {
            return new int[0];
        }
        int rows = mat.length;
        int cols = mat[0].length;
        int[] res = new int[rows*cols];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();

        // add element to map
        for(int i = 0;i < rows;i++) {
            for(int j = 0;j < cols;j++) {
                int sum = i+j;
                if(!map.containsKey(sum)) {
                    map.put(sum, new ArrayList<>());
                }
                map.get(sum).add(mat[i][j]);
            }
        }

        // add to res
        int idx = 0;
        for(Map.Entry<Integer, ArrayList<Integer>> entry: map.entrySet()) {
            int sum = entry.getKey();
            ArrayList<Integer> list = entry.getValue();
            if(sum % 2 == 0) {
                // need to reverse
                Collections.reverse(list);
            }
            // add to res
            for(int i = 0;i < list.size();i++,idx++) {
                res[idx] = list.get(i);
            }
        }
        return res;
    }
}

解法二 

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

		int m = mat.length;
		int n = mat[0].length;
		int result[] = new int[m * n];
		int i = 0, j = 0;

		int dirct[][] = new int[][] { { 0, 1 }, { 1, -1 }, { 1, 0 }, { -1, 1 } };

		boolean forword = true;
		boolean change = false;
		result[0] = mat[0][0];
		for (int k = 1; k < m * n; k++) {

			//从左下到右上对接线的遍历
			if (forword) {
				int newi = i + dirct[3][0];
				int newj = j + dirct[3][1];
				change = false;
				//越界了要改变方向，同时"转弯",优先考虑往(0,1)方向移动
				if (outRange(newi, newj, m, n)) {
					newi = i + dirct[0][0];
					newj = j + dirct[0][1];
					change = true;
					//存在另一种"转弯"可能
					if (outRange(newi, newj, m, n)) {
						newi = i + dirct[2][0];
						newj = j + dirct[2][1];
					}

				}
				i = newi;
				j = newj;
			}
			//从左下到左对接线的遍历
			if (!forword) {
				int newi = i + dirct[1][0];
				int newj = j + dirct[1][1];
				change = false;
				//越界了要改变方向，同时"转弯",优先考虑往(1,0)方向移动
				if (outRange(newi, newj, m, n)) {
					newi = i + dirct[2][0];
					newj = j + dirct[2][1];
					change = true;
					if (outRange(newi, newj, m, n)) {
						newi = i + dirct[0][0];
						newj = j + dirct[0][1];
					}

				}
				i = newi;
				j = newj;
			}
			if (change) {
				forword = !forword;
			}

			result[k] = mat[i][j];

		}
		return result;
	}

	private boolean outRange(int i, int j, int m, int n) {
		if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
			return true;
		}
		return false;
	}

解题总结

寻找规律，建议自己不看题解从头到尾实现一遍，不同的人写的会有差异。