文章目录
- 螺旋矩阵
- 解题思路
- 先找行进路线
- 找每条路线的结束位置
- 再找每条路线的结束位置
- 模拟行走
- 螺旋矩阵 II
- 总结
螺旋矩阵
解题思路
本题可以采用模拟的方式,设4种行走方向,如下图:
先找行进路线
4个方向的行走路线分别是:从左到右,从上到下,从右到左,从下到上。
并且
从左到右是从第一行开始,
从上到下是从最后一列开始,
从右到左是从最后一行开始,
从下到上是从第一列开始。
代码定义如下:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
return ans;
}
当第一圈走完以后,4个方向一定都会向内收缩一圈。
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
leftToRight++;
upToDown--;
rightToLeft--;
downToUp++;
return ans;
}
找每条路线的结束位置
现在我们只需要搞清楚如何定义每个方向算走完这个逻辑即可,从图上可以看出,每个方向的结束位置,就是下一个方向的开始位置,比如从左向右走时,行保持不变,列应该一直走到下一个方向的开始位置,即upToDown定义的范围。
从上到下走时,列保持不变,行应该一直走到下一个方向的开始位置,即rightToLeft定义的范围。
由此可得,如下代码:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
for(int i = ?; i <= upToDown; i++){
}
leftToRight++;
for(int i = ?; i <= rightToLeft; i++){
}
upToDown--;
for(int i = ?; i >= downToUp; i--){
}
rightToLeft--;
for(int i = ?; i >= leftToRight; i--){
}
downToUp++;
return ans;
}
再找每条路线的结束位置
弄清楚4个方向的结束位置之后,剩下来的只要在定义好开始位置就好了,很明显,上一个方向的结束位置,即是当前方向的开始位置。
所以,我们填入4个方向的开始值后,代码如下:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
for (int i = downToUp; i <= upToDown; i++) {
}
leftToRight++;
for (int i = leftToRight; i <= rightToLeft; i++) {
}
upToDown--;
for (int i = upToDown; i >= downToUp; i--) {
}
rightToLeft--;
for (int i = rightToLeft; i >= leftToRight; i--) {
}
downToUp++;
return ans;
}
模拟行走
接下来,让每个方向走起来,并挨个添加到集合中,代码如下:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
for (int i = downToUp; i <= upToDown; i++) {
ans.add(matrix[leftToRight][i]);
}
leftToRight++;
for (int i = leftToRight; i <= rightToLeft; i++) {
ans.add(matrix[i][upToDown]);
}
upToDown--;
for (int i = upToDown; i >= downToUp; i--) {
ans.add(matrix[rightToLeft][i]);
}
rightToLeft--;
for (int i = rightToLeft; i >= leftToRight; i--) {
ans.add(matrix[i][downToUp]);
}
downToUp++;
return ans;
}
矩阵大小即是一共要走的步数,那么每走一步记录一下,直到走满矩阵大小即表示走完。
最后代码实现如下:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int step = 0;
int totalStep = matrix.length * matrix[0].length;
int leftToRight = 0;
int upToDown = matrix[0].length - 1;
int rightToLeft = matrix.length - 1;
int downToUp = 0;
while (step < totalStep) {
for (int i = downToUp; i <= upToDown && step < totalStep; i++) {
ans.add(matrix[leftToRight][i]);
step++;
}
leftToRight++;
for (int i = leftToRight; i <= rightToLeft && step < totalStep; i++) {
ans.add(matrix[i][upToDown]);
step++;
}
upToDown--;
for (int i = upToDown; i >= downToUp && step < totalStep; i--) {
ans.add(matrix[rightToLeft][i]);
step++;
}
rightToLeft--;
for (int i = rightToLeft; i >= leftToRight && step < totalStep; i--) {
ans.add(matrix[i][downToUp]);
step++;
}
downToUp++;
}
return ans;
}
螺旋矩阵 II
使用同样的套路即可快速完成
public int[][] generateMatrix(int n) {
int[][] ans = new int[n][n];
int step = 0;
int leftToRight = 0;
int upToDown = n - 1;
int rightToLeft = n - 1;
int downToUp = 0;
while (step < n * n) {
for (int i = downToUp; i <= upToDown && step < n * n; i++) {
ans[leftToRight][i] = ++step;
}
leftToRight++;
for (int i = leftToRight; i <= rightToLeft && step < n * n; i++) {
ans[i][upToDown] = ++step;
}
upToDown--;
for (int i = upToDown; i >= downToUp && step < n * n; i--) {
ans[rightToLeft][i] = ++step;
}
rightToLeft--;
for (int i = rightToLeft; i >= leftToRight && step < n * n; i--) {
ans[i][downToUp] = ++step;
}
downToUp++;
}
return ans;
}
总结
记住三个关键点即可:
- 总共上下左右4个方向。
- 每个方向的开始都由上一个方向的结束来决定。
- 每个方向的结束都由下一个方向的开始来决定。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)