Spiral Matrix I

Problem

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

Note

解法很形象，先从左上角开始，从左向右添加第一行的元素，然后到了右上角，从最后一列从上到下，到了右下角，在最后一行从右到左，到了左下角，从第一列从下到上，如此循环。每一圈循环count加一，直到count到了最中间的一行或者最中间的一列，只需进行从左到右或从上到下的操作，然后break。

为什么要break？这样做的理由其实很简单，不论行数m还是列数n更大，最后一个循环发生在count*2 == m or n的时候，此时一定只剩下一行或一列要走。也就是说，四个for循环，只走一次。如果不在前两个for循环之后break的话，那么那多余的一行或一列就会被加入res数组两次，造成错误的结果。要注意，在第一次之后的for循环要避开之前遍历过的点。

Solution

public class Solution {    public List
    
      spiralOrder(int[][] matrix) {        List
     
       res = new ArrayList
      
        ();        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;        int m = matrix.length;        int n = matrix[0].length;        int count = 0;        while (2*count < m && 2*count < n) {            for (int i = count; i <= n-1-count; i++) {                res.add(matrix[count][i]);            }            for (int i = count+1; i <= m-1-count; i++) {                res.add(matrix[i][n-1-count]);            }            if (2*count+1 == m || 2*count+1 == n) break;            for (int i = n-2-count; i >= count; i--) {                res.add(matrix[m-1-count][i]);            }            for (int i = m-2-count; i >= count+1; i--) {                res.add(matrix[i][count]);            }            count++;        }        return res;    }}
      
     
    

Spiral Matrix II

Problem

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

Example

Given n = 3,

You should return the following matrix:

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

Note

解法和Spiral Matrix I一样，只是简化了，甚至可以用一样的方法去做，只要把m也换成n。

使用num++，以及最后讨论n是否为奇数以判断中间是否有一个未循环的点，是这道题的两个有趣的地方。

Solution

public class Solution {    public int[][] generateMatrix(int n) {        int num = 1;        int[][] res = new int[n][n];        for (int cur = 0; cur < n/2; cur++) {            for (int j = cur; j < n-1-cur; j++) {                res[cur][j] = num++;            }            for (int i = cur; i < n-1-cur; i++) {                res[i][n-1-cur] = num++;            }            for (int j = n-1-cur; j > cur; j--) {                res[n-1-cur][j] = num++;            }            for (int i = n-1-cur; i > cur; i--) {                res[i][cur] = num++;            }        }        if (n % 2 != 0) res[n/2][n/2] = num;        return res;    }}