LeetCode54 螺旋矩阵
思路
就是说，给我们一个二维数组，然后我们需要按顺时针的顺序遍历二维数组，然后把每一个遍历到的数据放到一个一维数组中，最后返回这个一维数组。
思路很简单，关键是怎么控制让他顺时针去访问，什么时候向下走
什么时候向左走，什么时候向右走 等问题
如图分析：
但是此时还会存在问题
因为此题给的是 m*n 的矩阵不一定是正方形
因为不是正方形，边界的长和宽本来就不相同，在顺时针遍历的时候，可能某一次遍历完，已经遍历完所有元素了，但是由于参数的原因还会继续向后走。
解决方法：因此我们每走完一步都要判断是不是已经走完了 m*n个元素，如果是，那么直接提前break即可。
如下图所示：
-
此时是第二轮从left->right的遍历，此时top=1,left=1,right=2,bottom=1
-
这一次遍历之后，top++，变成2，下一次right不变，从top->bottom
因为top>bottom 所以不会进入
-
然后right--,变成1，下一次bottom不变，right->left 。
-
right=1,left=1,会进入 right->left的循环 而此时所有的元素都已经放入了目标的一维数组，所以此时进入循环 就会重复访问。
但是此时 如果是正方形，right一定是小于left的，因为正方形的边界都相同，每一轮之后，边界都等大的缩小1，但是由于是长方形，可能本来长就大于宽，因此出现了这种情况
代码
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
//总的元素个数
int total=matrixSize*matrixColSize[0];
//目前访问到的元素个数
int count=0;
//开辟排序后的数组
int* order=(int*)malloc(sizeof(int)*total);
int left=0;//左边界
int top=0;//上边界
int right=matrixColSize[0]-1;//右边界
int bottom=matrixSize-1;//下边界
//遍历的初始坐标为[top,left](0,0)
//top和bottom表示行坐标，left和right表示列坐标
//遍历原数组
while(count<total)
{
//top行固定 left->right
for(int i=left;i<=right;i++)
{
if(count==total)
break;
order[count++]=matrix[top][i];
}
top++;//缩小上边界
//right列固定，top->bottom
for(int i=top;i<=bottom;i++)
{
if(count==total)
break;
order[count++]=matrix[i][right];
}
right--;//缩小右边界
//bottom固定，right->left
for(int i=right;i>=left;i--)
{
if(count==total)
break;
order[count++]=matrix[bottom][i];
}
bottom--;//缩小下边界
//left固定，bottom->top
for(int i=bottom;i>=top;i--)
{
if(count==total)
break;
order[count++]=matrix[i][left];
}
left++;//缩小左边界
//来到此就要上去进行内层的一圈，由于上下左右边界都进行了调整
// 所以下一次还是从 [top,left]开始
}
*returnSize=total;
return order;
}
LeetCode59 螺旋矩阵Ⅱ
思路
- 定义一个n*n的二维数组
- 从外层到内层，按照顺时针顺序依次把 从1到n^2的数放入数组
- 循环判断条件是 count<=n*n
注意事项
-
*returnColumnSizes每一行多少列是一个数组 以二级指针的形式传递进来（一维数组的地址）。这个数组 需要自己malloc，然后赋值
第i行有多少列 -
*returnSize 是一个数组，返回的是二维数组的行数的大小
代码
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
//开辟一个数组 返回每行多少列
*returnColumnSizes=(int*)malloc(sizeof(int)*n);
//malloc一个二维数组
int** array=(int**)malloc(sizeof(int*) *n);
for(int i=0;i<n;i++)
{
array[i]=(int*)malloc(sizeof(int)*n);
(*returnColumnSizes)[i]=n;
}
//返回元素的大小：行
*returnSize=n;
int count=1;//最初的值
int total=n*n;
//定义上下左右边界
int left=0;
int top=0;
int right=n-1;
int bottom=n-1;
//开始向二维数组中填数字
while(count<=total)
{
//top不变，left->right
for(int i=left;i<=right;i++)
{
array[top][i]=count;
count++;
}
//上边界缩小
top++;
//right不变，top->bottom
for(int i=top;i<=bottom;i++)
{
array[i][right]=count;
count++;
}
//右边界缩小
right--;
//bottom不变，right->left
for(int i=right;i>=left;i--)
{
array[bottom][i]=count;
count++;
}
//下边界缩小
bottom--;
//left不变，bottom->top
for(int i=bottom;i>=top;i--)
{
array[i][left]=count;
count++;
}
//左边界缩小
left++;
//回到上面 进入内层
}
return array;
}