LeetCode 59. 螺旋矩阵 II
题目为:给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
螺旋矩阵类问题,没有特别好的算法去实现,可以按照上图中的来遍历,下面是思路和实现。
- 1 生成一个n*n的矩阵,用来返回结果
- 2 定义上右下左的边界,分别为0,n-1,n-1,0 (这些值对应数组中的初始位置,可见上图)
- 3 建一个变量cur记录当前值,cur > n*n的时候终止循环
- 4 循环里进行上右下左的判断
- 提示 写的过程中判断下一个要写哪个的时候可以预想一下本次结束后哪个边的值应该加还是减,这样有助于思考例如左边界到右边界后t就应该+1,然后就是上边界到下边界了,多想想上面的循环图
代码如下:学会了本题的思想,类似的54.螺旋矩阵;剑指Offer 29.顺时针打印矩阵,都能轻而易举的AC了。//top为0,上边界一开始为0,right一开始就是为n-1(数组从0开始n个),画图可以看出来,
let t = 0, r = n - 1, b = n-1, l=0
let cur = 1
//1 生成一个n*n的矩阵
const mat = new Array(n).fill(0).map(()=>new Array(n).fill(0))
while(cur <= tar){
for(let i = l; i <= r; i++)mat[t][i] = cur++ //左边界到右边界
t++ //上边第一行结束后到第二行,该上到下了,t++
for(let i = t; i <= b; i++)mat[i][r] = cur++ //上边界到下边界
r-- //r--,该右到左了
for(let i = r; i >= l; i--)mat[b][i] = cur++ //右边界到左边界
b-- //右到左后,b--,该下到上了
for(let i = b; i >= t; i--)mat[i][l] = cur++ //下边界到上边界
l++ //下到上后,l++该左到右了
}
return mat
PS:本文思路来自于这里