Code & Func

第12天。

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:

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

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

10
Explanation:

Note:

The total number of elements of the given matrix will not exceed 10,000.

这道题好像是之前没做出来的。

题意很好理解，这道题的关键就在于如何处理在边界时的移动。

首先，常规的移动就分为两种：

向右上移动
向左下移动

实现常规移动，这里就不赘述了。

然后就是在边界时如何移动了，经过观察移动的情况，我们可以总结出：

边界时，只有向右移动和向下移动两种情况
在向右上移动时遇到边界，优先向右移动
在向左下移动时遇到边界，优先向左移动

根据上面的结论，我们就可以写出代码了：

1
bool nextRightUp(int &i, int &j, int &m, int &n) {
2

3
    if (i - 1 >= 0 && j + 1 < n) { // move right up
4
        i--; j++; return true;
5
    } else if (j + 1 < n) { // move right
6
        j++; return false;
7
    } else if (i  + 1 < m){ // move down
8
        i++; return false;
9
    }
10
    return false; // mean in the last elem
11
}
12
bool nextLeftDown(int &i, int &j, int &m, int &n) {
13
    if (i + 1 < m && j -1 >= 0) { // move right up
14
        i++; j--; return true;
15
    } else if (i + 1 < m) { // move down
25 collapsed lines
16
        i++; return false;
17
    } else if (j + 1  < n) { // move right
18
        j++; return false;
19
    }
20
    return false;
21
}
22
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
23
    int m = matrix.size();
24
    vector<int> res;
25
    if (m == 0) return res;
26
    int n = matrix[0].size();
27
    int i = 0, j = 0;
28
    bool up = true;
29

30
    for(int k = 0;k < m*n;k++) {
31
        res.push_back(matrix[i][j]);
32
        if (up) {
33
            up = nextRightUp(i, j, m, n);
34
        } else {
35
            up = !nextLeftDown(i, j, m, n);
36
        }
37
    }
38

39
    return res;
40
}