54. Spiral Matrix

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]

You should return [1,2,3,6,9,8,7,4,5].

public class Solution { public List spiralOrder(int[][] matrix) { List result = new ArrayList(); if(matrix.length == 0) return result; int start_x = 0, start_y = 0, end_x = matrix[0].length, end_y = matrix.length; while(start_x < end_x){ //right for(int i = start_x; i < end_x; i++) result.add(matrix[start_y][i]); //down if(end_y - start_y == 1) break; for(int i = start_y + 1; i < end_y; i++) result.add(matrix[i][end_x - 1]); //left if(end_x - start_x == 1) break; for(int i = --end_x - 1; i >= start_x; i--) result.add(matrix[end_y - 1][i]); //up if(end_y - start_y == 2) break; for(int i = --end_y - 1; i > start_y; i--) result.add(matrix[i][start_x]); start_x++; start_y++; } return result; }}

class Solution { List res = new ArrayList<>(); int m, n; public List spiralOrder(int[][] matrix) { if (matrix == null || matrix.length == 0) return res; int counter = 0; m = matrix.length; n = matrix[0].length; while(true) { magic(matrix, counter); counter++; if(res.size() == m*n) return res; } } private void magic(int[][] matrix, int counter) { move(matrix, counter, counter, counter, n-counter-1); move(matrix, counter+1, n-counter-1, m-counter-1, n-counter-1); move(matrix, m-counter-1, n-counter-2, m-counter-1, counter); move(matrix, m-counter-2, counter, counter+1, counter); } private void move(int[][] matrix, int row1, int col1, int row2, int col2){ if (res.size() == m*n) return; if (row1 == row2) { if (col1 <= col2) { while(col1 <= col2) res.add(matrix[row1][col1++]); } else if (col1 > col2) { while(col1 >= col2) res.add(matrix[row1][col1--]); } } else if(col1 == col2) { if (row1 <= row2) { while(row1 <= row2) res.add(matrix[row1++][col1]); } else if (row1 > row2) { while(row1 >= row2) res.add(matrix[row1--][col1]); } } }}

class Solution { public List spiralOrder(int[][] matrix) { List result = new ArrayList<>(); if(matrix == null || matrix.length == 0) { return result; } int M = matrix.length, N = matrix[0].length; int[][] seen = new int[M][N]; int count = M * N; int i = 0, j = 0; int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int idx = 0; int[] dir = directions[idx]; int x = 0, y = 0; while(count != 0) { //System.out.println(matrix[i][j]); result.add(matrix[i][j]); seen[i][j] = 1; x = i + dir[0]; y = j + dir[1]; if(isInBounds(x, y, seen)) { i = x; j = y; } else { idx = (idx + 1) % directions.length; // System.out.printf("Direction: %d\n", idx); dir = directions[idx]; i += dir[0]; j += dir[1]; } count--; } return result; } public boolean isInBounds(int x, int y, int[][] seen) { if(x >= 0 && y >= 0 && x < seen.length && y < seen[0].length) { if(seen[x][y] != 1) return true; } return false; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。