59.螺旋矩阵II54.螺旋矩阵
59.螺旋矩阵II 54.螺旋矩阵
59.螺旋矩阵II
自己写的：
//力扣题号59.螺旋矩阵
// 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
// 空间复杂度 O(1)
#include<iostream>
using namespace std;
#include<vector>int main() {int n;cout << "请输入:";cin >> n;vector<vector<int>> nums(n,vector<int>(n,0));int count = 1;if (n % 2 != 0) {int centx = n/2, centy = n/2;nums[centx][centy] = n * n;}for(int col=0;col<n-1;col++){for (int i = col;i <n-1-col;i++) {nums[col][i] = count;count++;}for (int j = col;j <n-1-col;j++) {nums[j][n - 1-col] = count;count++;}for (int k = n - 1-col;k > col;k--) {nums[n - 1-col][k] = count;count++;}for (int f = n - 1-col;f > col;f--) {nums[f][col] = count;count++;}}for (int i = 0;i < n;i++) {for (int j = 0;j < n;j++) {cout << nums[i][j]<<" ";}cout << endl;}return 0;
}
网上解法：
#include<iostream>
#include<vector>
using namespace std;class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0));//使用vector定义一个二维数组int startx = 0, starty = 0;//定义每循环一个圈的起始位置int loop = n / 2;//每个圈循环几次，例如n位奇数3，那么loop=1只是循环一圈，矩阵中间的值需要单独处理int mid = n / 2;//矩阵中间的位置，例如：n为3，中间的位置就是（1，1),n为5，中间位置为（2,2）int count = 1;//用来给矩阵中每一个空格赋值int offset = 1;//需要控制每条边遍历的长度，每次循环右边界收缩一位int i, j;while (loop--) {i = startx;j = starty;//下面开始的四个for循环就是模拟顺时针转了一圈//模拟填充上行从左到右(左闭右开：第一行第一个元素被填充，最后一个元素不被填充）for (j;j < n - offset;j++) {//此时j初始为0，末端为n-2，也就是遍历第一行除了最后一个元素以外的所有元素res[i][j] = count++;}//模拟填充右列从上到下（上闭下开）for (i;i < n - offset;i++) {//此时i为0，末端为n-2，j为n-1，也就是遍历最后一列的除了最后一个元素以外的所有元素res[i][j] = count++;}//模拟填充下行从右到左（右闭左开）for (;j > starty;j--) {//此时j为n-1，i为n-1，末端为1，也就是遍历最后一行除了第一个元素以外的所有元素res[i][j] = count++;}//模拟填充左列从下到上（下闭上开）for (;i > startx;i--) {//此时i为n-1，j为0，末端为1，也就是遍历第一列除了最后一个元素以外的所有元素res[i][j] = count++;}//第二圈开始的时候，起始位置要各自+1，例如：第一圈的起始位置是(0,0)，第二圈的起始位置是(1,1)startx++;starty++;//offset 控制每一圈里每一条边遍历的长度offset++;}//如果n为奇数的话，需要单独给矩阵最中间的位置赋值if (n % 2) {res[mid][mid] = count;}return res;}
};int main() {Solution sol;//这种创建对象的方式为 栈中分配，由操作系统进行内存的分配和管理//当程序离开对象的使用范围（如方法结束，一个程度块的最后{}），范围内的栈中的对象会自动删除，内存自动回收。Solution* sol2 = new Solution();//这种创建对象的方式为堆中分配，由管理者进行内存的分配和管理，用完必须delete()，否则可能造成内存泄漏//堆中的对象不会自动删除，内存不会自动回收，所以new一个对象使用完毕，必须调用delete，释放内存空间。也就是说，new和delete必须成对出现int num;cin >> num;vector<vector<int>> result(num, vector<int>(num, 0));vector<vector<int>> result2(num, vector<int>(num, 0));result=sol.generateMatrix(num);result2=sol2->generateMatrix(num);delete(sol2);for (int i = 0;i < num;i++) {for (int j = 0;j < num;j++) {cout << result[i][j] << " ";}cout << endl;}for (int i = 0;i < num;i++) {for (int j = 0;j < num;j++) {cout << result2[i][j] << " ";}cout << endl;}
}
54.螺旋矩阵
自己写的：
//力扣题号54.螺旋矩阵
// 时间复杂度：O(mn)
// 空间复杂度:O(mn)//自己解法：
#include<iostream>
#include<vector>
using namespace std;class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int count = 1;vector<int> res;//赋值一个矩阵for (int i = 0;i < matrix.size();i++) {for (int j = 0;j < matrix[i].size();j++) {matrix[i][j] = count++;}}//查看赋值的矩阵for (int i = 0;i < matrix.size();i++) {for (int j = 0;j < matrix[i].size();j++) {cout << matrix[i][j]<<" ";}cout << endl;}int offset = 1;//赋值偏移量int startx = 0;//赋值起始的元素的列int starty = 0;//赋值起始元素的行int i, j;while (true) {i = startx;//重新赋值起始元素j = starty;if (matrix.size() == 1) {//如果该数组只有一行，直接将该行赋值给结果res = matrix[0];break;}if (matrix[0].size() == 1) {//如果该数组只有一列，循环传入结果for (int j = 0;j < matrix.size();j++) {res.push_back(matrix[j][0]);}break;}//为什么要将上面两种情况单独判断，原因是我们扫描矩阵的元素是左闭右开的，如果某一行或一列只有一个元素的话，该元素既是第一个元素又是最后一个元素//最后在左闭右开的情况下是取不到的，因此要将这种特殊情况单独取出来。//总体说明：我这里把所有元素分为两类，一类是在环上的元素，一类是中间元素，矩阵由环和中间元素构成，// 每一个环一定有一个起始位置，且坐标为上一个环起始位置的行坐标+1，列坐标+1//判断此时的起始元素列坐标是否超过对应矩阵末端坐标，如果超出了则说明环已经扫描完毕，要么剩一个单独的元素，要么没有元素if (startx > matrix[0].size() - offset || starty > matrix.size() - offset) {break;}//从左到右赋值，这里是左闭右开，没有取最后一个元素for (j = startx;j < matrix[0].size() - offset;j++) {res.push_back(matrix[i][j]);}//从上往下赋值，这里是上闭下开，没有取最后一个元素for (i = starty;i < matrix.size() - offset;i++) {res.push_back(matrix[i][j]);}for (;j > startx;j--) {res.push_back(matrix[i][j]);}for (;i > starty;i--) {res.push_back(matrix[i][j]);}startx++;//起始位置列坐标+1starty++;//起始位置行坐标+1offset++;//偏移量+1}//如果if (matrix.size() == matrix[0].size()) {res.push_back(matrix[matrix.size() / 2][matrix.size() / 2]);}return res;}
};int main() {Solution sol;int m, n;cin >> m >> n;vector<vector<int>> res(m, vector<int>(n, 0));vector<int> result;result=sol.spiralOrder(res);for (int i = 0;i < result.size();i++) {cout << result[i] << " ";}
}
网上解法：
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int count = 1;//赋值一个二维数组for (int i = 0;i < matrix.size();i++) {for (int j = 0;j < matrix[i].size();j++) {matrix[i][j] = count++;}}vector <int> ans;if (matrix.empty()) return ans; //若数组为空，直接返回答案int up = 0; //赋值上下左右边界int down = matrix.size() - 1;int left = 0;int right = matrix[0].size() - 1;while (true){for (int i = left; i <= right; ++i) ans.push_back(matrix[up][i]); //这里初始up为0，表示从第一行开始从左往右一次扫描到最末端if (++up > down) break; //现在最上端也就是上边界已经扫描完毕，因此删去（实际上这里是将上边界++），然后判断上边界是否大于下边界，比如说如果只有一行，++之后上边界为1就大于下边界为0了，因此退出循环for (int i = up; i <= down; ++i) ans.push_back(matrix[i][right]); //然后螺旋扫描，这里初始right为matrix[0].size() - 1，也就是最后一列，这里的up++之后为1，也就是从第二行开始扫描到最后一行if (--right < left) break; //扫描完毕之后对右边届进行--，也就是删去（实际上只是将右边届往左退回一步），然后判断右边界是否小于了左边界，比如说如果只有一列，--之后右边界为-1,就小于左边界0了，因此退出循环for (int i = right; i >= left; --i) ans.push_back(matrix[down][i]); //这里的下边界初始为matrix.size() - 1，然后从右往左扫描if (--down < up) break; //扫描完毕之后对下边界进行--，也就是删去（实际上只是将下边界往上退了一步），然后判断下边界是否小于了上边界，比如说如果原数组只有两行，上面第一个for循环扫描上边界的时候已经删去了一行，现在轮到下边界删去的时候还剩一行，删去下边界之后就结束了，因此这里要判断一下for (int i = down; i >= up; --i) ans.push_back(matrix[i][left]); //这里左边界初始为0，从下往上扫描if (++left > right) break; //扫描完毕之后，删去左边界（这里实际上是将左边界往右进了一步），然后判断左边界是否大于右边界，比如说如果原数组只有两列，上面第二个for循环扫描左边界的时候已经删去了一列，现在轮到左边界删去的时候还剩一列，删去左边界之后就结束了，因此这里要判断一下//一圈结束以后扫描第二圈，相当于外面一个环已经被全部删去了，对应的上、下、左、右边界也都进行了刷新，现在对一个新的矩阵再进行扫描，知道扫描完成...//如果非要讨论for循环的边界，那么边界是左闭右闭的。}return ans;}
};
int main() {Solution sol;int m, n;cin >> m >> n;vector<vector<int>> res(m, vector<int>(n, 0));vector<int> result;result=sol.spiralOrder(res);for (int i = 0;i < result.size();i++) {cout << result[i] << " ";}
}
