leetcode 54. Spiral Matrix 谷歌面试题

Seawolf

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]
Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

思路：两个pointer，一个横着走，一个竖着走，每次计算matrix 的最外围一周，然后进行递归。考虑特殊情况，一个是empty set，另一个是size one array。

class Solution {
        public static List<Integer> spiralOrder(int[][] matrix) {

        ArrayList<Integer> recept = new ArrayList<>();
            
        ArrayList<Integer> empty = new ArrayList<Integer>(){};
            
        if(matrix == null || matrix.length == 0){
            
            return empty;
        }
            
        if(matrix.length == 1){
            
            for(int i = 0; i<matrix[0].length; i++ ){
                
                recept.add(matrix[0][i]);
            }
            
            return recept;
        }

        generateList(matrix, recept, matrix[0].length, matrix.length, 0);

        return recept;
    }

    public static void generateList(int[][] matrix, ArrayList<Integer> array, int rowlen, int colen, int n) {
        
        if(matrix == null){

            return;
        }

        int len_of_column = colen - 2*n;

        int len_of_row = rowlen - 2*n;

        if(len_of_column <= 0 || len_of_row <= 0) {

            return;
        }

        int first = 0 + n, second = 0 + n;

        if(first == n) {

            while(first != n+ len_of_row && first>=n && first <= n+ len_of_row) {

                array.add(matrix[0+n][(first++)]);

//                System.out.println(array);
//                System.out.println("-----");
            }
        }

        second++;

        if(first == len_of_row+n && second == n+1) {

            while(second != len_of_column + n && second >=n && second <= len_of_column + n) {

                array.add(matrix[second++][first-1]);

//                System.out.println(array);
//                System.out.println("-----");
            }
        }

        first= first -2 ;

        if(first == len_of_row-2+n && second == len_of_column+n) {

            while(first != 0+n && first >=n && first <= len_of_row+n) {

                array.add(matrix[second-1][(first--)]);

//                System.out.println(array);
//                System.out.println("-----");
            }
        }

        second--;



        if(first == 0+n && second == len_of_column-1+n) {

            while(second != n && second >=n && second <=len_of_column+n) {

                array.add(matrix[(second--)][first]);
            }

        }

        n++;

        generateList(matrix, array, rowlen, colen, n);

    }
}

结果在running time 和 memory usage beat 100% online submissions！！！