Created
February 10, 2018 01:38
-
-
Save jianminchen/8e1db32dc8168195c60b3848ab077f3b to your computer and use it in GitHub Desktop.
Leetcode 54: Spiral matrix - clock wise - direction arrays, clockwise, and then range discussion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Julia study the Leetcode discussion: | |
https://discuss.leetcode.com/topic/15558/a-concise-c-implementation-based-on-directions/2?page=1 | |
What I like to do is to go over the notes and make it more readable first. Most of important is to train | |
myself to go over the thinking process closely. Spend more time on thinking process instead of the code. | |
When traversing the matrix in the spiral order, at any time we follow one out of the following four | |
directions: RIGHT DOWN LEFT UP. Suppose we are working on a 5 x 3 matrix as such: | |
0 1 2 3 4 | |
6 7 8 9 10 | |
11 12 13 14 15 | |
Imagine a cursor starts off at (0, 0), i.e. the position at '0', then we can achieve | |
the spiral order by doing the following: | |
Go right 5 times | |
Go down 2 times | |
Go left 4 times | |
Go up 1 times. | |
Go right 3 times | |
Go down 0 times -> quit | |
**Range decrement by one for horizontal series** | |
**Rnage decerement by one for vertical series** | |
Notice that the directions we choose always follow the order 'right->down->left->up', | |
and for horizontal movements, the number of shifts follows: {5, 4, 3}, and vertical | |
movements follows {2, 1, 0}. | |
From the above example, we can define the horizontal range initial value is rows, | |
but the vertical initial value is cols - 1; next horizontal range will decrement value | |
by one, same as next vertical range. (Julia added this paragraph to help illustration.) | |
**One for loop instead of four** | |
We can make use of a direction matrix that records the offset for all directions, then | |
an array of two elements that stores the number of shifts for horizontal and vertical | |
movements, respectively. This way, we really just need one for loop instead of four. | |
Another good thing about this implementation is that: If later we decided to do spiral | |
traversal on a different direction (e.g. Counterclockwise), then we only need to change | |
the Direction matrix; the main loop does not need to be touched. | |
*/ | |
vector<int> spiralOrder(vector<vector<int>>& matrix) { | |
vector<vector<int> > dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; | |
vector<int> res; | |
int nr = matrix.size(); | |
if (nr == 0) return res; | |
int nc = matrix[0].size(); | |
if (nc == 0) return res; | |
vector<int> nSteps{nc, nr - 1}; | |
int iDir = 0; // index of direction. | |
int ir = 0, ic = -1; // initial position | |
while (nSteps[iDir % 2]) | |
{ | |
for (int i = 0; i < nSteps[iDir%2]; ++i) | |
{ | |
ir += dirs[iDir][0]; | |
ic += dirs[iDir][1]; | |
res.push_back(matrix[ir][ic]); | |
} | |
nSteps[iDir % 2]--; | |
iDir = (iDir + 1) % 4; | |
} | |
return res; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment