SpiralMatrix [source code]
public class SpiralMatrix {
static
/******************************************************************************/
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<> ();
if (matrix.length == 0 || matrix[0].length == 0)
return res;
int R = matrix.length, C = matrix[0].length;
boolean[][] visited = new boolean[R][C];
int[] delta_row = {0, 1, 0, -1}, delta_col = {1, 0, -1, 0};
int x = 0, y = 0, pos_row = 0, pos_col = 0, delta_x = delta_row[pos_row], delta_y = delta_col[pos_col];
while (true) {
res.add (matrix[x][y]);
visited[x][y] = true;
/* Two points:
1. separate increment updates from coordinate updates, as a conditional
2. pre-leaf determination */
if (!isValid (visited, x + delta_x, y + delta_y)) {
pos_row = (pos_row + 1) % 4;
pos_col = (pos_col + 1) % 4;
delta_x = delta_row[pos_row];
delta_y = delta_col[pos_col];
}
x += delta_x;
y += delta_y;
if (!isValid (visited, x, y))
break;
}
return res;
}
boolean isValid (boolean[][] visited, int x, int y) {
return x >= 0 && y >= 0 && x < visited.length && y < visited[0].length && !visited[x][y];
}
}
/******************************************************************************/
public static void main(String[] args) {
SpiralMatrix.Solution tester = new SpiralMatrix.Solution();
int[][][] inputs = {
{
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
}, {{1,2,3,6,9,8,7,4,5}},
{{}}, {{}},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] matrix = inputs[2 * i];
int[] ans = inputs[2 * i + 1][0];
System.out.println (Printer.separator ());
String input_str = Matrix.printMatrix (matrix);
List<Integer> output = tester.spiralOrder (matrix);
List<Integer> ans_ls = new ArrayList<> ();
for (int num : ans)
ans_ls.add (num);
System.out.printf ("%s -> %s, expected: %s\n",
input_str, Printer.wrapColor (output.toString (), output.equals (ans_ls) ? "green" : "red"), ans_ls
);
}
}
}
好像有点思路, 直接开始写;
最后按时写出来了, 速度是3ms (8%). 注意上面代码给的comment; 反正最后就是考一个熟练度; 这种担心出界的问题的traversal, pre leaf判断非常的好用; 另外, 上面的逻辑也很清楚: 反正我是要+delta的, 那我在+delta之前先用一个conditional来判断这个delta首先有没有问题(加了之后会不会出界), 如果没有问题, 那么就不执行这个update delta的操作, 否则就update一下, 保证不会出错; 这个就跟你给一个Map<String, List<String>>这样的东西里面的list的更新是一回事的原理;
另外, 关于这个visited的, 实际上我感觉好像可以直接用四个int来保存四个方向不断收缩的边界, 但是想想计算有点麻烦, 不如直接用visited来搞, 反正也方便;
另外, 草稿:
虽然好像没什么卵用; 这题反正就是多动手就能看出来了;
editorial
Approach #1: Simulation [Accepted]
Intuition
Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.
Algorithm
Let the array have
R rows and
C columns.
seen[r][c] denotes that the cell on the
r-th row and
c-th column was previously visited. Our current position is
(r, c), facing direction
di, and we want to visit
R x
C total cells.
As we move through the matrix, our candidate next position is
(cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length, C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
int r = 0, c = 0, di = 0;
for (int i = 0; i < R * C; i++) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int cr = r + dr[di];
int cc = c + dc[di];
if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
r = cr;
c = cc;
} else {
di = (di + 1) % 4;
r += dr[di];
c += dc[di];
}
}
return ans;
}
}
这个跟我的代码几乎就是一样的了, 不过没有我的代码clean;
Approach #2: Layer-by-Layer [Accepted]
Intuition
The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.
这个思路好像有点意思, 也是一个把矩形进行等分的问题, 这个操作见过好几次了;
class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}
}
思路本身并不是很难理解, 笔算两下就知道了; 比较难处理是最后terminate的时候的corner case; 这个我感觉只能通过例子来笔算了; 我感觉这个思路的实现难度是高于上面那个自动走的方法的, 但是又没有带来什么实际的加速效果;
@qwl5004 said in Super Simple and Easy to Understand Solution:
This is a very simple and easy to understand solution. I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.
The only tricky part is that when I traverse left or up I have to check whether the row or col still exists to prevent duplicates. If anyone can do the same thing without that check, please let me know!
Any comments greatly appreciated.
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if (matrix.length == 0) {
return res;
}
int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
// Traver Up
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin ++;
}
return res;
}
}
跟editorial2实际上是类似的思路, 不过他认为自己的想法不同; 注意, 每一个外层while的iteration里面, 是走完一整个圈, 而不是一个点; 这个问题以前也讨论过了, eager nesting很多时候可以降低问题的整个难度;
@jakwings said in Super Simple and Easy to Understand Solution:
You should use an array of direction offsets if you want to be a game developer. And you don't need to check the border because rows and cols always decrease. Here is my C++ code:
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>> &matrix) {
vector<int> result;
if (matrix.empty()) return result;
result = matrix[0]; // no need to check the first row
int dirs[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; // direction offsets
int d = 0; // direction index
int m = matrix.size();
int n = matrix[0].size();
int pos[2] = {0, n - 1}; // start from the top right corner
int i = (m - 1) * n; // number of the rest numbers
while (i > 0) {
for (int j = 1; j < m; j++) {
i--;
pos[0] += dirs[d][0]; pos[1] += dirs[d][1];
result.push_back(matrix[pos[0]][pos[1]]);
}
m--; // decrease the size of row or column
swap(m, n); // switch between horizontal and vertical mode
d = (d + 1) % 4; // loop between direction offsets
}
return result;
}
};
这个算法是稍微有点绕人的, 看下面:
总体的思路还是一个模拟traversal的思路, 不过这些swap什么的东西, 让readability确实降低了; 另外, 这个好像是LeetCode第一次有人用方向向量做法;
@Lancelod_Liu said in Super Simple and Easy to Understand Solution:
My cpp solution using same idea. state means direction and everything is just in code.
class Solution {
public:
vector<int> spiralOrder(vector<vector<int> > &matrix) {
int rows = matrix.size();
if (rows == 0) return vector<int> ();
int cols = matrix[0].size();
int row = 0, col = 0, layer = 0;
vector<int> res;
res.push_back(matrix[0][0]);
int state = 1;
for (int step = 1; step < rows * cols; step++) {
switch(state) { // based on state, check and change state, then move on
case 1: // supposed to go right
if (col == cols-layer-1) { // reach right bound
row++;
state = 2;
}
else col++;
break;
case 2: // supposed to go down
if (row == rows-layer-1) { // reach downside bound
col--;
state = 3;
}
else row++;
break;
case 3: // supposed to go left
if (col == layer) { // reach left bound
row--;
state = 4;
}
else col--;
break;
case 4: // supposed to go up
if (row == layer+1) { // reach upside bound
col++;
state = 1;
layer++;
}
else row--;
break;
}
res.push_back(matrix[row][col]);
}
return res;
}
};
还行的解法, 思路也是挺明确的, 我之前想过维护四边, 他这里直接用layer来维护一个相当于四条边的offset, 因为四条边的步进是一样的;
原来的OP一个担心的问题就是在走下边和左边的时候, 需要加一个check(任何对边不能相等或者反转), 他在发帖的时候认为的一个难题就是怎样去掉这个check, 然后下面就有人想出来了:
@rakesh_joshi said in Super Simple and Easy to Understand Solution:
almost same code but you can use the matrix size for the breaking condition for simplicity
as in my code i calculated the matrix sizen=ROW*COL, now i can check my resultant vector size become equal tonor not
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>res; int R,C,l,r,t,b,n; // R --row, C --col, l --left, r --right , t --top, b --bottom
if((R=matrix.size())==0) return res;
C=matrix[0].size(), n=R*C,t=0,l=0, r=C-1,b=R-1;
while(res.size()!=n){
for(int i=l;i<=r;i++) res.push_back(matrix[t][i]);
t++;
for(int i=t;i<=b;i++) res.push_back(matrix[i][r]);
r--;
if(res.size()==n) break;
for(int i=r; i>=l;i--) res.push_back(matrix[b][i]);
b--;
for(int i=b;i>=t;i--) res.push_back(matrix[i][l]);
l++;
}
return res;
}
@stellari said in A concise C++ implementation based on Directions:
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 5
6 7 8 9 10
11 12 13 14 15Imagine a cursor starts off at (0, -1), 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
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}.
Thus, 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;
}
这个跟前面那个game的人的写法是差不多的, 只不过那个人用swap, 这里stellari把两个维度的长度保存在一个长度为2的数组, 然后用binary index来切换;
一个评价很高的:
@ChuntaoLu said in Simple Python solution by mutating the matrix:
The con is mutating the matrix, if this is not allowed, we can make a deep copy of the matrix first. And of course it comes with the additional memory usage.
def spiralOrder(self, matrix):
ret = []
while matrix:
ret += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
ret.append(row.pop())
if matrix:
ret += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
ret.append(row.pop(0))
return ret
但是看不懂啊, 后面对Python的语法稍微熟悉一点之后再来看好了;
submission就那几个解法, 波动; 现在看来还是那个game的人和stellari的那种交换维度的方法比较有意思;
Problem Description
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Difficulty:Medium
Total Accepted:130.6K
Total Submissions:483.9K
Contributor:LeetCode
Companies
googlemicrosoftuber
Related Topics
array
Similar Questions