## Wednesday, February 8, 2017

### LeetCode 498. Diagonal Traverse

https://leetcode.com/problems/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:
```
1. The total number of elements of the given matrix will not exceed 10,000.

https://discuss.leetcode.com/topic/77865/concise-java-solution
Walk patterns:
• If out of `bottom border` (row >= m) then row = m - 1; col += 2; change walk direction.
• if out of `right border` (col >= n) then col = n - 1; row += 2; change walk direction.
• if out of `top border` (row < 0) then row = 0; change walk direction.
• if out of `left border` (col < 0) then col = 0; change walk direction.
• Otherwise, just go along with the current direction.
``````    public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return new int[0];
int m = matrix.length, n = matrix[0].length;

int[] result = new int[m * n];
int row = 0, col = 0, d = 0;
int[][] dirs = {{-1, 1}, {1, -1}};

for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row += dirs[d][0];
col += dirs[d][1];

if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
if (row < 0)  { row = 0; d = 1 - d;}
if (col < 0)  { col = 0; d = 1 - d;}
}

return result;
}``````
https://discuss.leetcode.com/topic/77937/java-15-lines-without-using-boolean
``````    public int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) return new int[0];
int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
for (int i = 0; i < arr.length; i++) {
arr[i] = matrix[r][c];
if ((r + c) % 2 == 0) { // moving up
if      (c == n - 1) { r++; }
else if (r == 0)     { c++; }
else            { r--; c++; }
} else {                // moving down
if      (r == m - 1) { c++; }
else if (c == 0)     { r++; }
else            { r++; c--; }
}
}
return arr;
}``````

`初始对角线方向为右上方（偏移量：行-1, 列+1），遇到边界时转向左下方（偏移量：行+1, 列-1）`

```向右上方移动遇到上边界时，若未达到右边界，则向右移动（偏移量：行+0，列+1），否则向下移动（偏移量：行+1，列+0）