题目:
例子:
分析题目:
本题给了一个值n要生成一个n*n的矩形,并且是螺旋的生成值。
这样我们可以把它分层来看如n =4时生成一个4*4的矩形由两层矩形构成,这样就能先遍历生成最外面的一层后再去生成里面的一层
那如何实现遍历呢?
先一行行来看(一层的上下左右行),因为起始位置是 0 0 所以我们能用对一层中的每一行用左闭右开的形式生成,这样就能顺利的完成对一层的遍历(具体就是从开始位置开始生成,每行的最后一个位置就不动,作为下一行的开始)
思想有了那就来实现:
附:
其中的returnSize、returnColumnSizes分别表示的是
returnSize:返回共有几行
returnColumnSizes:创建一个数组,数组中对应存放了每一行有几列
写法思路:
- 先要生成一个二维数组,来放螺旋矩形
- 通过遍历来生成(用一个变量来记录每一层的开始startx、starty , 如n == 4时 startx、y一开始为0 0 然后到里面那一层时开始为 1 1 )
- 然后是循环次数,那个实例来看 n == 4 时 循环两边即可,那就是n/2次
- 但注意的是,如n == 3 、 5 、 ... 这样的奇数时其中在循环遍历后会在最中间剩下一个位置而这个位置也是最后一个遍历的值,所以可以单独领出来判断一些即可
还有一些详细的过程已经进行了注释
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){int startx = 0,starty = 0,tag = 1,count = 1;//剪掉count让其形成左闭右开*returnSize = n;//返回有几行*returnColumnSizes = (int*)malloc(sizeof(int)*n);//返回每一行的列数//创建一个二维数组int **arr =(int**)malloc(sizeof(int*)*n);//先开辟一个存放一级指针的数组for(int i = 0; i < n ;i++){arr[i] = (int*)malloc(sizeof(int)*n);//给每一行开辟空间 ,这样就形成了二级指针(*returnColumnSizes)[i] = n;//每一行赋值有几列}int i = 0 , j = 0;int tmp = n/2;while(tmp--)//遍历n/2圈如:n == 4 时遍历2圈{//对每一行进行左闭右开的遍历
//tag是用来形成右开的即n - tag 是最后一个位置处的下标for(;j <n - tag;j++)arr[i][j] = count++;for(; i <n - tag ; i++)arr[i][j] = count++;for(;j > startx; j--)arr[i][j] = count++;for(;i > starty; i--)arr[i][j] = count++;//遍历完一层后需要改变一下开始startx、y 前置++一下赋值给i、j i= ++starty;j= ++startx;tag++;//tag++一下因为此时的边界又往里面进了一位}if(n % 2 == 1)//当n是奇数时arr[n/2][n/2] = count;//对最中间没有遍历到的最后一个值就行赋值return arr;
}
总结:
- 找规律,找到一个不变量,才能进行遍历