LeetCode59. 螺旋矩阵Ⅱ

题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例

提交的代码

class Solution {
    int matrixLen=0;
    public int[][] generateMatrix(int n) {
	//初始化空数组
        int[][] matrix=new int[n][n];
	//每个位置的值，递增1
        int initNum=1;
	//每一圈左上角的初始index
        int initIndex=0;
	//矩阵边长，留待给对称位置赋值时用
        matrixLen=n;
	//递归给矩阵赋值
        outerMatrix(matrix,initIndex,initNum,n);
        return matrix;
    }

    public void outerMatrix(int[][] matrix,int initIndex,int initNum,int initLen){
	//当矩阵长为1和2的时候特殊处理
        if(initLen==1){
            matrix[initIndex][initIndex]=initNum;
        }else if(initLen==2){
            matrix[initIndex][initIndex]=initNum++;
            matrix[initIndex][initIndex+1]=initNum++;
            matrix[initIndex+1][initIndex+1]=initNum++;
            matrix[initIndex+1][initIndex]=initNum++;
        }else{

            int j=initIndex;
            int k=initIndex;
            int gap=(initLen-1)*2;
	    //7字形拐角的第一段赋值
            for(int i=0;i<initLen;i++,k++){
                matrix[j][k]=initNum;
		//给对称位置赋值
                matrix[matrixLen-j-1][matrixLen-k-1]=initNum+gap;
                initNum++;
            }
            j++;
            k--;
	    //7字形拐角的第二段赋值
            for(int i=0;i<initLen-2;i++){
                matrix[j][k]=initNum;
                matrix[matrixLen-j-1][matrixLen-k-1]=initNum+gap;
                if (i==initLen-3){
                    initNum=initNum+gap;
                }else{
                    initNum++;
                }
                j++;
            }
            outerMatrix(matrix,++initIndex,++initNum,initLen-2);
        }
    }
}

思路

最外面一圈只处理如图所示的一半，另一半用对称的方法来赋值，可以观察到第一圈对称位置的值相差6，通过(4-1)*2得到，内圈对称的位置相差2，(2-1)*2。
然后用递归的方法来处理内圈。startIndex=0,1,2....。
当圈的半径为1和2时特别处理，如上面代码所示。

学习到的方法

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix=new int[n][n];

        //计算所给的n，需要转几圈，如2就一圈，3就一圈加一个单独的值，4就两圈完成，5就两圈加一个单独的值
        int loop=n/2;
        //计算如果是奇数的话，那么最后的且是最中心的点，它的index是什么
        int centralIndex=n/2;
        //每一圈的起始index(0,0)(1,1)
        int startX=0;
        int startY=0;
        //每一圈不需要处理的个数
        int offset=1;
        //每一个空位需要填充的值(每次+1)
        int currentValue=1;

        int i;
        int j;
        while(loop>0){
            i=startX;
            j=startY;

            for(;j<n-offset;j++){
                matrix[i][j]=currentValue++;
            }
            for(;i<n-offset;i++){
                matrix[i][j]=currentValue++;
            }
            for(;j>startY;j--){
                matrix[i][j]=currentValue++;
            }
            for(;i>startX;i--){
                matrix[i][j]=currentValue++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startX++;
            startY++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;

            loop--;
        }
         // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if ((n % 2)==1) {
            matrix[centralIndex][centralIndex] = currentValue;
        }
        return matrix;
    }
}

思路

如图所示，遵从左闭右开的方法，第一行的最后一个不处理，留给最后一列用刚才的方法，最右一列的最后一个不处理，最后一行从右向左的最后一个不处理，留待左列从下向上处理length减一个。
这样转圈处理起来代码好写，只需要考虑好每次循环的startIndex，给出的n需要转几圈(n/2)，，offset(左闭右开，最后一个不处理需要用到)的长度处理。当n为偶数的时候是不可能存在最后的centralIndex的，当n为奇数的时候，最中间的那一个位置的index怎么求(n/2)。