Sunday, July 23, 2017

[Leetcode] Diagonal Traverse, Solution

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


[Thoughts]
以题中示例为例子,看一下坐标的变化,如下图

在上升通道的时候, row = row -1, col = col +1
在下降通道的时候,row = row +1, col = col -1

当坐标变化超出数组范围的时候,要遵循以下原则调整:
1. 如果row < 0, row = 0, 变换通道
2. 如果col < 0, col = 0, 变换通道
3. 如果 col > N, col = N-1, row = row +2;
4. 如果 row > M, row = M-1. col = col +2;



[Code]
1:    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {  
2:      if(matrix.size() == 0 || matrix[0].size() == 0) return {};  
3:        
4:      vector<int> result;  
5:        
6:      vector<pair<int, int>> move_delta{{-1, 1}, {1, -1}};  
7:        
8:      int rows = matrix.size(), cols = matrix[0].size();  
9:      int row = 0, col = 0, m = 0;  
10:      for(int i = 0; i< rows * cols; i++) {  
11:        result.push_back(matrix[row][col]);  
12:        row += move_delta[m].first;  
13:        col += move_delta[m].second;  
14:          
15:        if(row >= rows) {  
16:          row = rows-1;  
17:          col = col +2;  
18:          m = 1-m;  
19:        }  
20:          
21:        if(col >= cols) {  
22:          col = cols -1;  
23:          row = row + 2;  
24:          m = 1-m;  
25:        }  
26:          
27:        if(row < 0) {  
28:          row = 0;  
29:          m = 1-m;  
30:        }  
31:          
32:        if(col < 0) {  
33:          col = 0;  
34:          m = 1-m;  
35:        }  
36:      }  
37:      return result;  
38:    }  


No comments: