个人主页：https://github.com/zbhgis
前言
本系列主要记录自己学习算法的过程中的感悟。
力扣59. 螺旋矩阵 II
链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
注意点
定义一个方向变量，决定每次移动的步数与长度
每次走到边缘或者下一个元素有值的时候，就转向。
其他情况就一直走就行。
代码
class Solution { private static final int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int[][] generateMatrix(int n) { int[][] ans = new int[n][n]; int i = 0; int j = 0; int d = 0; for (int val = 1; val <= n * n; val ++) { ans[i][j] = val; int nx = i + DIR[d][0]; int ny = j + DIR[d][1]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || ans[nx][ny] != 0) { d = (d + 1) % 4; } i += DIR[d][0]; j += DIR[d][1]; } return ans; } }时空复杂度分析
时间复杂度为O(n²)
空间复杂度为O(1)
Acwing756. 蛇形矩阵
链接：https://www.acwing.com/problem/content/description/758/
注意点
同上
代码
import java.util.Scanner; public class Main { private static final int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] ans = new int[m][n]; int i = 0; int j = 0; int d = 0; for (int val = 1; val <= m * n; val ++) { ans[i][j] = val; int nx = i + DIR[d][0]; int ny = j + DIR[d][1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n || ans[nx][ny] != 0) { d = (d + 1) % 4; } i += DIR[d][0]; j += DIR[d][1]; } for (i = 0; i < m; i ++) { for (j = 0; j < n; j ++) { System.out.print(ans[i][j] + " "); } System.out.println(); } } }时空复杂度分析
同上
力扣54. 螺旋矩阵
链接：https://leetcode.cn/problems/spiral-matrix/description/
注意点
与前两题不同的是，这次需要通过matrix[i][j] = Integer.MAX_VALUE来判断是不是已经访问过了。其他步骤都一样。
代码
class Solution { private static final int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public List<Integer> spiralOrder(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; List<Integer> ans = new ArrayList<>(m * n); int i = 0; int j = 0; int d = 0; for (int k = 1; k <= m * n; k ++) { ans.add(matrix[i][j]); int nx = i + DIR[d][0]; int ny = j + DIR[d][1]; matrix[i][j] = Integer.MAX_VALUE; if (nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] == Integer.MAX_VALUE) { d = (d + 1) % 4; } i += DIR[d][0]; j += DIR[d][1]; } return ans; } }时空复杂度分析
时间复杂度为O(n²)
空间复杂度为O(1)
力扣LCR 146.螺旋遍历二维数组
链接：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/
注意点
这一题还需要额外注意当输入的为空数组的情况，这个时候直接返回空数组就行，不要处理。
代码
class Solution { private static final int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int[] spiralArray(int[][] array) { int m = array.length; if (m == 0) { return new int[0]; } int n = array[0].length; int[] ans = new int[m * n]; int i = 0; int j = 0; int d = 0; for (int k = 0; k < m * n; k ++) { ans[k] = array[i][j]; array[i][j] = Integer.MAX_VALUE; int x = i + DIR[d][0]; int y = j + DIR[d][1]; if (x < 0 || x >= m || y < 0 || y >= n || array[x][y] == Integer.MAX_VALUE) { d = (d + 1) % 4; } i += DIR[d][0]; j += DIR[d][1]; } return ans; } }时空复杂度分析
时间复杂度为O(n²)
空间复杂度为O(1)
参考
https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
