☆打卡算法☆LeetCode 59、螺旋矩阵 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个正整数，按顺时针顺序螺旋排列生成矩阵。”

题目链接：

来源：力扣（LeetCode）

链接：59. 螺旋矩阵 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：
输入： n = 3
输出： [[1,2,3],[8,9,4],[7,6,5]]

示例 2：
输入： n = 1
输出： [[1]]

二、解题

1、思路分析

这个题跟螺旋矩阵的区别在于，螺旋矩阵是已经排列好的，然后进行旋转。

而本题是根据输入的正整数，生成螺旋矩阵。

初始位置在矩阵的左上角，初始方向向右，若下一步的位置超过边界，或者是之间访问的文职，
则顺时针旋转，如此反复填充所有元素。

2、代码实现

代码参考：

public class Solution {
    public int[][] GenerateMatrix(int n) {
        int[][] res = new int[n][];
            for(int i=0; i<n;i++ )
            {
                res[i] = new int[n];
            }
            int lC = n;//剩余列长度
            int hC = n;//剩余行长度
            int l = 0;//当前的列位置
            int h = 0;//当前的行位置
            int num = 1;//该位置上的数字
            while(lC>0&&hC>0)
            {
                for(int i=0;i<lC ;i++,l++,num++ )//从第一行开始从左往右放数字
                {
                    res[h][l] = num;
                }
                l--;//调整下一个位置
                h++;
                hC--;
                if(hC==0)//判断结束，总行数和总列数一样，而列数先减少，所以剩余行数会比剩余列数快减少至0
                {
                    break;
                }
                for(int i=0;i<hC ;i++,h++,num++ )//从最后一列开始从上到下放数字
                {
                    res[h][l] = num;
                }
                h--;
                l--;
                lC--;
                for(int i=0; i<lC;i++,l--,num++)
                {
                    res[h][l] = num;
                }
                l++;
                h--;
                hC--;
                if(hC==0)
                {
                    break;
                }
                for(int i=0;i<hC ;i++,h--,num++ )
                {
                    res[h][l] = num;
                }
                h++;
                l++;
                lC--;
            }
            return res;
    }
}

3、时间复杂度

时间复杂度 ： O(n²)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

依旧是按层模拟的解题方法。