Spiral Matrix(LintCode)

Spiral Matrix

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

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].

难得的一次AC！虽然感觉题很水，但是像这样思路清晰的写下来，没有出任何的“小问题”，然后提交，AC的情况对我来说还是很少的。虽然代码依旧有些乱。

想法就是定义一个方向的二维数组，从(0，0)开始沿一个方向遍历，若碰壁（下个遍历目标越界或已被遍历）就一个不会碰壁的方向继续遍历；每一个方向都碰壁时结束。

 public class Solution {

     /**

      * @param matrix a matrix of m x n elements

      * @return an integer list

      */

      int[][] f = new int[1000][1000];

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

         List<Integer> list = new ArrayList<Integer>();

         int m = matrix.length;

         if(m == 0) return list;

         int n = matrix[0].length;

         int[][] d = new int[4][2];

         d[0][0] = 0; d[0][1] = 1;

         d[1][0] = 1; d[1][1] = 0;

         d[2][0] = 0; d[2][1] = -1;

         d[3][0] = -1; d[3][1] = 0;

         int cd = 0;

         int i = 0;

         int j = 0;

         list.add(matrix[0][0]);

         f[0][0] = 1;

         boolean flag = true;

         while(flag) {

             if(!isV(i,j,d[cd],m,n)){

                 int x = 0;

                 while(!isV(i,j,d[cd],m,n) && x < 4) {

                     cd = (cd + 1) % 4;

                     x++;

                 }

                 if(x >= 4) flag = false;

             }else {

                 i += d[cd][0];

                 j += d[cd][1];

                 list.add(matrix[i][j]);

                 f[i][j] = 1;

             }

         }

         return list;

     }

     boolean isV(int i ,int j ,int d[] ,int m ,int n) {

         if(i + d[0] < 0 || i + d[0] >= m) return false;

         if(j + d[1] < 0 || j + d[1] >= n) return false;

         if(f[i + d[0]][j + d[1]] != 0)return false;

         return true;

     }

 }

巴特西

Spiral Matrix(LintCode)

Spiral Matrix

最新文章

热门文章