【LeetCode-Java】54. Spiral Matrix+59. Spiral Matrix II

54. Spiral Matrix：

1.原题

链接：https://leetcode.com/problems/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].

给出一个矩阵，从外圈到内圈顺时针依次打印。

3.解题思路

这道题没有涉及复杂的数据结构或高级算法，但包含多个循环，需判断多个边界条件。

思路是每一次打印矩阵中的一个圈，用四个变量来控制：行起点，行终点，列起点，列终点。需注意的是，第三步遍历列数时需判断行数是否满足，第四步遍历行数时需判断列数是否满足。

时间复杂度为O(mn)，空间复杂度为O(mn)

4.代码实现

    public List<Integer> spiralOrder(int[][] matrix) {
  List<Integer> result=new ArrayList<Integer>();
        if(matrix.length<1)
        return result;
        int rowBegin=0,rowEnd=matrix.length-1;
        int colBegin=0,colEnd=matrix[0].length-1;
        while(rowBegin<=rowEnd && colBegin<=colEnd){
        for(int i=colBegin;i<=colEnd;i++)
        result.add(matrix[rowBegin][i]);
        rowBegin++;
        for(int i=rowBegin;i<=rowEnd;i++)
        result.add(matrix[i][colEnd]);
        colEnd--;
        if(rowBegin<=rowEnd){
        for(int i=colEnd;i>=colBegin;i--)
            result.add(matrix[rowEnd][i]);
            rowEnd--;
        }
        if(colBegin<=colEnd){
        for(int i=rowEnd;i>=rowBegin;i--)
            result.add(matrix[i][colBegin]);
            colBegin++;
        }
        }
        return result;
    }

59. Spiral Matrix II

1.原题

链接：https://leetcode.com/problems/spiral-matrix-ii/

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

For example,
Given n = 3,

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

给出整数n,生成一个n*n的矩阵。

3.解题思路

从外圈到内圈顺时针依次打印1,2,3...n^2，每次生成一个外圈。与上面这题不同的是，这个是一个方形矩阵，有些特殊情况不用判断。

时间复杂度为O(n^2)，空间复杂度为O(n^2)

4.代码实现

public int[][] generateMatrix(int n) {
    int[][] matrix=new int[n][n];
        int rowBegin=0,rowEnd=n-1;
        int colBegin=0,colEnd=n-1;
        int num=1;
        while(rowBegin<=rowEnd && colBegin<=colEnd){
        for(int i=colBegin;i<=colEnd;i++){
        matrix[rowBegin][i]=num;
        num++;
        }
        rowBegin++;
        for(int i=rowBegin;i<=rowEnd;i++){
        matrix[i][colEnd]=num;
        num++;
        }
        colEnd--;
        for(int i=colEnd;i>=colBegin;i--){
        matrix[rowEnd][i]=num;
        num++;
        }
        rowEnd--;
        for(int i=rowEnd;i>=rowBegin;i--){
        matrix[i][colBegin]=num;
        num++;
        }
        colBegin++;
        }
    return matrix;
    }