本文共 4705 字,大约阅读时间需要 15 分钟。
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]
与498. Diagonal Traverse类似的做法,模仿运行过程,用+=move来控制移动,建立一个二维数组记录访问情况。因为这里涉及到-1,0,1三种移动方式,用矩阵比较麻烦,但是不用看着挺臃肿蠢笨的
class Solution { public ListspiralOrder(int[][] matrix) { List res = new ArrayList<>(); if (matrix == null || matrix.length == 0) return res; int m = matrix.length, n = matrix[0].length; boolean[][] visited = new boolean[m][n]; int row = 0, col = 0; int moveR = 0, moveC = 1; for(int i = 0; i < m*n; i++){ res.add(matrix[row][col]); visited[row][col] = true; row += moveR; col += moveC; if(col == n || (moveR == 0 && moveC == 1 && visited[row][col] == true)){ row++; col--; moveR = 1; moveC = 0; } else if(row == m || (moveR == 1 && moveC == 0 && visited[row][col] == true)){ row--; col--; moveR = 0; moveC = -1; } else if(col < 0 || (moveR == 0 && moveC == -1 && visited[row][col] == true)){ row--; col++; moveR = -1; moveC = 0; } else if(moveR == -1 && moveC == 0 && visited[row][col] == true){ row++; col++; moveR = 0; moveC = 1; } } return res; }}
leetcode solution 1: Simulation
跟我的做法差不多,不过这里用矩阵来控制移动:总共就4种情况,而且周期循环,用个变量++取模class Solution { public ListspiralOrder(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; }}
leetcode 2: Layer-by-Layer
不用额外的存储空间,但是理解复杂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; }}
solution 3:
针对我的方法在空间上的优化:只用4个变量来存储行列的头尾public class Solution { public ListspiralOrder(int[][] matrix) { List res = new ArrayList (); 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; }}
转载地址:http://sfqvb.baihongyu.com/