做微信商城网站建设放心网站推广优化咨询

54. 螺旋矩阵

使用vis数组记录该位置是否已经被访问
定义一个int型dir来记录方向，0123分别代表右下左上
当越界或碰壁已访问的位置后，修改dir并计算下一个位置
否则根据原dir计算下一个位置

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();int n = matrix.length;int m = matrix[0].length;int dir = 0; // 0右  1下  2左  3上boolean vis[][] = new boolean[n][m];int x = 0;int y = 0;for(int i = 0; i < n*m; i ++){list.add(matrix[x][y]);vis[x][y] = true;if(dir == 0){if(y + 1 >= m || vis[x][y+1] == true){dir = (dir + 1) % 4;x = x + 1;}else{y = y + 1;}}else if(dir == 1){if(x + 1 >= n || vis[x+1][y] == true){dir = (dir + 1) % 4;y = y - 1;}else{x = x + 1;}}else if(dir == 2){if(y - 1 < 0 || vis[x][y-1] == true){dir = (dir + 1) % 4;x = x - 1;}else{y = y - 1;}}else{if(x - 1 < 0 || vis[x-1][y] == true){dir = (dir + 1) % 4;y = y + 1;}else{x = x - 1;}}}return list;}
}

简化

常用思路，使用二维数组dirs[4][2]进行坐标的上下左右四个方位移动，简化代码
（也常用dirs[8][2]获取坐标的周围8个位置）
使用dirs和dir计算下一个将要使用的新坐标，若越界或碰壁，则将dir修改，获得正确的新坐标

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();int n = matrix.length;int m = matrix[0].length;int dir = 0; // 0右  1下  2左  3上int dirs[][] = {{0,1},{1,0},{0,-1},{-1,0}}; // 对应dir四种移动坐标变化boolean vis[][] = new boolean[n][m];int x = 0;int y = 0;for(int i = 0; i < n*m; i ++){list.add(matrix[x][y]);vis[x][y] = true;// 判断int newX = x + dirs[dir][0];int newY = y + dirs[dir][1];if(newX < 0 || newX >= n || newY < 0 || newY >= m || vis[newX][newY] == true){dir = (dir + 1) % 4;}// 移动x += dirs[dir][0];y += dirs[dir][1];}return list;}
}