今日刷题重点----螺旋矩阵
59. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1 输出：[[1]]
思路1:
根据卡尔大佬的说法,求解本题依然是要坚持循环不变量原则。
模拟顺时针画矩阵的过程:
填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开又闭的原则，这样这一圈才能按照统一的规则画下来。
那么我按照左闭右开的原则，来画一圈，大家看一下
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
这也是坚持了每条边左闭右开的原则。
一些同学做这道题目之所以一直写不好，代码越写越乱。
就是因为在画每一条边的时候，一会左开又闭，一会左闭右闭，一会又来左闭右开，岂能不乱。
参考代码1
//1.一圈一圈的进行填数.圈数=n/2,如果n为奇数,则中间的那个数单独处理. //2.每次圈的边长相比上一次总是少二 ,以n=6为例:6 4 2 所以可以使用一个变量每次循环之后加2 //3.在进行循环时,要按照一定的规则,既要让所有的点都被遍历到也尽量不要多次进行遍历. 我们采用左闭右开的规则 vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n,vector<int>(n,0));//定义一个二维数组 int loop = n / 2; int cnt = 1;//填充变量 int offset = 1; int startX = 0,startY = 0;//定义每圈的起始坐标 while(loop--) { int i = startX; int j = startY; //从左到右 for(; j< startY+n-offset; j++) { res[i][j] = cnt++; } //从上到下 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++; } //offset变量加2 offset+=2; //startX,startY进行更新 startX++; startY++; } if(n%2) { //如果n是奇数. res[n/2][n/2] = cnt; } return res; }
思路2
生成一个 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即可
参考代码2
vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n,vector<int>(n,0)); int l = 0,r =n-1,u = 0,d = n-1; int sum = n*n,num=1; //cout<<"123"<<endl; while(num<=sum) { //从左到右 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++; cout<<num<<endl; } 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还执行.
参考代码
//思路:参考螺旋矩阵二 注意每层for循环中间的sum条件也要限制. 具体原因可以举个例子比如说只有一行的话, //从左到右循环完毕按说已经结束了,但是 从右向左的for依旧会被执行.. vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> res; if(matrix.size()==0){ return res; } int n = matrix.size(); int m = matrix[0].size(); int l = 0,r = m-1,u = 0,d = n-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; }
剑指 Offer 29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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]
思路分析:
和上面的题类似
参考代码
vector<int> spiralOrder(vector<vector<int>>& matrix) { if(matrix.size()==0){ return {}; } int n = matrix.size(); int m = matrix[0].size(); int l = 0,r = m-1,u = 0,d = n-1; int sum = n*m,num=1; vector<int> ans; while(num<=sum){ //从左到右 for(int i =l;i<=r;i++){ V.push_back(matrix[u][i]); num++; } u++; //从上到下 for(int i = u;i<=d;i++){ V.push_back(matrix[i][r]); num++; } r--; //从右到左 for(int i=r;i>=l;i--){ V.push_back(matrix[d][i]); num++; } d--; //从下到上 for(int i = d;i>=u;i--){ V.push_back(matrix[i][l]); num++; } l++; } return V; }
