61、【数组】leetcode——[高频考题]59. 螺旋矩阵 II:N*N型(C++、Python版本)
1. 题目描述
运行效果
图示举例
2. 方法一:以起点、长度为研究对象,迭代更新
观察矩阵特点,填充顺序是从左至右、从上至下、从右至左、从下至上,然后再次在新的起点进行相同顺序填充。可发现每次新填充的起点沿着矩阵的主对角线。
在这一个过程中有三个重要的地方:填充起点、填充顺序和填充长度。
由此,构建仿真模拟这一过程。
- 填充起点设置对角线,每填充新的一层就往对角线下移动一个位置。
- 填充顺序按照右、下、左、上顺序进行。
- 填充长度设置一个偏移量,来控制每层填充的长度。以左闭右开([,))的填充方式进行填充。即一个方向上只填充n-1个数。
C++版本
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int startx = 0, starty = 0; // 设置每轮起点
int loop = n / 2, mid = n / 2; // 设置填充层数和记录终点位置
int count = 1, offset = 1; // 计数和设置偏移量
while(loop--) {
for(int i = starty; i < n - offset; i++) // 从起点位置开始,向右,starty + n - offset控制填充长度
res[startx][i] = count++;
for(int i = startx; i < n - offset; i++) // 向下
res[i][n - offset] = count++;
for(int i = n - offset; i > startx; i--) // 向左
res[n - offset][i] = count++;
for(int i = n - offset; i > starty; i--) // 向上(上述四个步骤都是左闭右开[,))
res[i][starty] = count++;
startx++; // 更新起点
starty++;
offset += 1; // 更新偏移量
}
if(n % 2 != 0) res[mid][mid] = count; // 若n为奇数,则需要单独填充终点位置
return res;
}
};
Python版本
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0]*n for _ in range(n)]
startx, starty, loop, mid = 0, 0, n // 2, n // 2
count = 1
for offset in range(1, loop + 1): # 每循环一层偏移量加1
for j in range(starty, n - offset): # 从左走至右
res[startx][j] = count
count += 1
for i in range(startx, n - offset): # 从上走至下
res[i][n - offset] = count
count += 1
for j in range(n - offset, starty, -1): # 从右走至左
res[n - offset][j] = count
count += 1
for i in range(n - offset, startx, -1): # 从下走左上
res[i][starty] = count
count += 1
startx += 1
starty += 1
if n % 2 != 0:
res[mid][mid] = count
return res
空间复杂度:
O
(
1
)
O(1)
O(1) 。除了返回的矩阵以外,空间复杂度是常数。
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2) 。 其中 nn 是给定的正整数。矩阵的大小是
n
×
n
n \times n
n×n,需要填入矩阵中的每个元素。
参考文章:
59.螺旋矩阵II
3. 方法二:边界收缩
记录矩阵的上、下、左、右边界标号,按照从左边界至右边界、从上边界至下边界、从右边界至左边界、从下边界至上边界的顺序。
每填充完一侧后,就将该测边界向内移一层,然后下一次填充就从该层边界的起始点开始填充。
C++版本
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int top = 0, buttom = n - 1, left = 0, right = n - 1; // 设置四个边界
int count = 1;
while(count <= n * n){
for(int i = left; i <= right; i++) res[top][i] = count++; // 左边界到右边界
top++;
for(int i = top; i <= buttom; i++) res[i][right] = count++; // 上边界到下边界
right--;
for(int i = right; i >= left; i--) res[buttom][i] = count++; // 右边界到左边界
buttom--;
for(int i = buttom; i >= top; i--) res[i][left] = count++; // 下边界到上边界
left++;
}
return res;
}
};
Python版本
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0] * n for _ in range(n)]
top, buttom, left, right = 0, n - 1, 0, n - 1
count = 1
while count <= n * n :
for i in range(left, right + 1) :
res[top][i] = count
count += 1
top += 1
for i in range(top, buttom + 1) :
res[i][right] = count
count += 1
right -= 1
for i in range(right, left - 1, -1) :
res[buttom][i] = count
count += 1
buttom -= 1
for i in range(buttom, top - 1, -1) :
res[i][left] = count
count += 1
left += 1
return res
空间复杂度:
O
(
1
)
O(1)
O(1) 。除了返回的矩阵以外,空间复杂度是常数。
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2) 。 其中 nn 是给定的正整数。矩阵的大小是
n
×
n
n \times n
n×n,需要填入矩阵中的每个元素。
相关文章
- Python图形用户界面Tkinter标准色彩颜色背景色大全
- python 排序算法总结及实例详解
- Atitit 文件上传 架构设计 实现机制 解决方案 实践java php c#.net js javascript c++ python
- Python之ffmpeg-python:ffmpeg-python库的简介、安装、使用方法之详细攻略
- Python编程语言学习:python中与数字相关的函数(取整等)、案例应用之详细攻略
- 成功解决Exception "unhandled RuntimeError" run loop already started File: F:Program FilesPythonPython
- 已解决2. Set PROTOCOL_BUPFERS_PYTHON_iMPLEMENTATION=python (but this will use pure-Python parsing and w
- 【python代码】:能在手机上敲 Python 代码几款App
- 为什么我觉得学python很难?
- 〖Python 数据库开发实战 - MySQL篇㉘〗- MySQL 日期函数
- 〖Python 数据库开发实战 - Python与MySQL交互篇⑩〗- 创建新闻管理系统的具体python文件
- Python采集疫情数据,并做可视化展示
- python基础知识之 Python代码规范
- 【LeetCode Python实现】 5472. 重新排列字符串(简单)
- 【华为OD机试 2023】 任务总执行时长(C++ Java JavaScript Python)
- 【华为OD机试 2023】 对称美学(C++ Java JavaScript Python)
- 【华为OD机试 2023】 不含101的数(C++ Java JavaScript Python)
- 【 华为OD机试 2023】荒地建设电站 /区域发电量统计(C++ Java JavaScript Python)
- 【华为OD机试 2023】最优资源分配/芯片资源占用(C++ Java JavaScript Python)
- 【 华为OD机试 2023】实力差距最小总和、最佳对手(C++ Java JavaScript Python)
- python之组一个tlv格式的报文
- C++调用C++项目中的Python脚本中的函数和类。,在,工程,python
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【Python实战】 ---- python 实现 CSDN 的定时自动签到