本文主要是介绍螺旋矩阵算法(leetcode第885题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。最终，我们到过网格的所有 rows x cols 个空间。按照访问顺序返回表示网格位置的坐标列表。示例 1：输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：[[0,0],[0,1],[0,2],[0,3]]
示例 2：输入：rows = 5, cols = 6, rStart = 1, cStart = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]提示：1 <= rows, cols <= 100
0 <= rStart < rows
0 <= cStart < cols
算法一：
思路：
分析上图，可以剖析出一个规律：
每次循环，向右向下移动相同步数，向左向上移动相同步数，并且向右向下一体，向左向上一体，这两个步数依次递增
所以我们可以改变步数与增量来实现循环
对于超范围的坐标进行判断即可
代码实现：
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
# include<stdlib.h>
void pushMatrix(int **matrix,int rows,int cols,int rStart,int cStart,int *index){//存入matrixif(rStart>=rows||rStart<0)//行超范围return;else if(cStart>=cols||cStart<0)//列超范围return;else{//存入matrix[*index][0]=rStart;matrix[*index][1]=cStart; (*index)++;}
}
int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {*returnSize=rows*cols;//总空间*returnColumnSizes=(int*)malloc(sizeof(int)*(*returnSize));int **matrix=(int**)malloc(sizeof(int*)*(*returnSize));//开辟m*n行，每行一个二维坐标(等同于两列)，第一列为x，第二列为yfor(int i=0;i<rows*cols;i++){matrix[i]=(int*)malloc(sizeof(int)*2);(*returnColumnSizes)[i]=2;//列空间为2}int index=0,dx=1;//index-->matrix下标//dx-->循环次数int changeDx=1;//changeDx-->增量while(index<rows*cols){if(index==0){//对第一次进行特殊处理pushMatrix(matrix,rows,cols,rStart,cStart,&index);if(index==*returnSize) return matrix;}for(int i=0;i<dx;i++){cStart+=changeDx;//左右移动pushMatrix(matrix,rows,cols,rStart,cStart,&index);}for(int i=0;i<dx;i++){rStart+=changeDx;//上下移动pushMatrix(matrix,rows,cols,rStart,cStart,&index);}changeDx=-changeDx;//步长相反dx++;//循环次数加一}return matrix;
}算法一直白代码
思路：
将while里的两个for循环分为四个for循环，对于上下左右，直观易懂，但是优化不明显
代码实现：
void judge(int rStart,int cStart,int rows,int cols,int**arr,int* rest,int*p){if(rStart>=rows||rStart<0)return;else if(cStart>=cols||cStart<0)return;else{arr[*p][0]=rStart;arr[(*p)++][1]=cStart;(*rest)--;}
}
int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {int rest=cols*rows;int**arr=malloc(sizeof(int*)*rest);*returnSize=rest;*returnColumnSizes=malloc(sizeof(int)*rest);for(int i=0;i<rest;i++){arr[i]=malloc(sizeof(int)*2);(*returnColumnSizes)[i]=2;}for(int r=1,p=0;rest;r+=2){//因为每走两次走的距离增加一格，走四次增加两格，所以r+=2if(!p){ //对第一次走进行特殊处理judge(rStart,cStart,rows,cols,arr,&rest,&p);if(!rest) return arr;}for(int j=0;j<r;j++)//右走(j<r)judge(rStart,++cStart,rows,cols,arr,&rest,&p);for(int j=0;j<r;j++)//下走(j<r)judge(++rStart,cStart,rows,cols,arr,&rest,&p);//注意j<r变为j<=r，相当于走的距离增加一格for(int j=0;j<=r;j++)//左走(j<=r)judge(rStart,--cStart,rows,cols,arr,&rest,&p);for(int j=0;j<=r;j++)//上走(j<=r)judge(--rStart,cStart,rows,cols,arr,&rest,&p);}return arr;
}这篇关于螺旋矩阵算法(leetcode第885题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
