【面试算法笔记】0105-数组-螺旋矩阵

个人主页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 ListInteger spiralOrder(int[][] matrix) { int m matrix.length; int n matrix[0].length; ListInteger 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