4、枚举模拟法
59.螺旋矩阵 II
题目描述
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1 输出：[[1]]
思路分析:
方法一:模拟(循环不变量原则)
根据卡尔大佬的说法,求解本题依然是要坚持循环不变量原则。
模拟顺时针画矩阵的过程:
填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
这也是坚持了每条边左闭右开的原则。
一些同学做这道题目之所以一直写不好，代码越写越乱。
就是因为在画每一条边的时候，一会左开又闭，一会左闭右闭，一会又来左闭右开，岂能不乱。
方法二
生成一个 n×n 空矩阵 res，随后模拟整个向内环绕的填入过程：
定义当前左右上下边界 l,r,u,d，初始值 num = 1，迭代终止值 sum= n * n；
当 num <= sum 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：num++,得到下一个需要填入的数字；
更新边界：例如从左到右填完后，上边界 u++，相当于上边界向内缩 1。
使用num <= sum而不是l < r || u < d作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
最终返回 res即可
参考代码
方法一
#include<bits/stdc++.h> using namespace std; vector<vector<int>> generateMatrix(int n) { int startX = 0,startY = 0;//循环起始下标 vector<vector<int>> res(n,vector<int>(n,0));//定义矩阵 int loop = n / 2;//循环层数 int offSet = 1;//每次循环遍历需要减少的元素个数 int cnt = 0;//进行矩阵赋值 int i,j; while(loop--) { i = startX; j = startY; //从左到右 for(; j<startY+n-offSet; j++) { res[i][j] = ++cnt; } //结束的j刚好就是下一次循环需要用的纵坐标 //从上到下 for(; i<startX+n-offSet; i++) { res[i][j] = ++cnt; } //从右到左 for(; j>startY; j--) { res[i][j] = ++cnt; } //从下到上 for(; i>startX; i--) { res[i][j] = ++cnt; } // startX++;//更新下一次起始下标 startY++; offSet+=2; } if(n%2==1) {//如果n是奇数,更新中心点. res[n/2][n/2] = ++cnt; } return res; }
方法二
#include<bits/stdc++.h> using namespace std; vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n,vector<int>(n,0)); int u = 0,d = n - 1,l = 0,r = n-1; int num = 1; while(num<=n*n){ //从左到右 for(int i = l; i <= r;i++) { res[u][i] = num++; } u++; //从上到下 for(int i = u;i<=d;i++){ res[i][r] = num++; } r--; //从右到左 for(int i = r;i>=l;i--){ res[d][i] = num++; } d--; //从下到上 for(int i = d;i>=u;i--) { res[i][l] = num++; } l++; } return res; }
54. 螺旋矩阵
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路分析
和上面的题思路二很相似,但本题不同的是会出现矩形;,所以中间的for循环也要对sum进行限制,防止减成0后,后面的for还执行.
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> spiralOrder(vector<vector<int>>& matrix) { if(matrix.size()==0) { return {}; } vector<int> res; int n = matrix.size(),m = matrix[0].size(); int u = 0,l = 0,d = n - 1,r = m - 1; int sum = n * m; while(sum) { //从左到右 for(int i = l; i <= r&∑ i++) { res.push_back(matrix[u][i]); sum--; } u++; //从上到下 for(int i = u; i<=d&∑ i++) { res.push_back(matrix[i][r]); sum--; } r--; //从右到左 for(int i = r; i>=l&∑ i--) { res.push_back(matrix[d][i]); sum--; } d--; //从下到上 for(int i = d; i>=u&∑ i--) { res.push_back(matrix[i][l] ); sum--; } l++; } return res; }
如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客
