“给定一个正整数,按顺时针顺序螺旋排列生成矩阵。”
题目链接:
来源:力扣(LeetCode)
链接:59. 螺旋矩阵 II - 力扣(LeetCode) (leetcode-cn.com)
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:
输入: n = 3
输出: [[1,2,3],[8,9,4],[7,6,5]]
示例 2:
输入: n = 1
输出: [[1]]
这个题跟螺旋矩阵的区别在于,螺旋矩阵是已经排列好的,然后进行旋转。
而本题是根据输入的正整数,生成螺旋矩阵。
初始位置在矩阵的左上角,初始方向向右,若下一步的位置超过边界,或者是之间访问的文职, 则顺时针旋转,如此反复填充所有元素。
代码参考:
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;
}
}
时间复杂度 : O(n2)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
依旧是按层模拟的解题方法。