数组--part 5--螺旋矩阵（力扣59/54）（剑指offer 29）

基本算法思想

建议先去把题目看了，再来思考相关的代码。

错误的想法：实际上这种题型并不存在算法，只涉及到模拟，但是模拟难度并不是很基础，所以逐渐演变到面试官考察的常见题型之一。

建议按照左闭右开的原则（见下图，同种颜色代表着，是同层循环所作的事情），从一开始就定义好，进行循环。

这也就是循环不变量的思想。

理解了循环不变量的思想，接下来来进行介绍一下代码书写的基本思想，以及格式。

vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组int startx = 0, starty = 0; // 定义每循环一个圈的起始位置int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)int count = 1; // 用来给矩阵中每一个空格赋值int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位int i, j;while (loop--) {i = startx;j = starty;// 下面开始的四个for就是模拟转了一圈// 模拟填充上行从左到右(左闭右开)for (j = starty; j < n - offset; j++) {res[startx][j] = count++;}// 模拟填充右列从上到下(左闭右开)for (i = startx; i < n - offset; i++) {res[i][j] = count++;}// 模拟填充下行从右到左(左闭右开)for (; j > starty; j--) {res[i][j] = count++;}// 模拟填充左列从下到上(左闭右开)for (; i > startx; i--) {res[i][j] = count++;}// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)startx++;starty++;// offset 控制每一圈里每一条边遍历的长度offset += 1;}// 如果n为奇数的话，需要单独给矩阵最中间的位置赋值if (n % 2) {res[mid][mid] = count;}return res;}

leetcode 59 螺旋矩阵 II

链接

此题基础便来源于上面，自然可以AC。

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int > >result(n, vector<int >(n, 0));int loop = n / 2;//代表要循环的次数int startx = 0, starty = 0;//确认起始点的位置。int count = 1;//记录此时记录到的数字。int i, j;//记录此时二维数组的位置。int offset = 1;//记录需要停止的位置。//代表需要画多少圈，才能画完所有的数据。但是需要注意的是分奇数偶数//偶数直接画完了，奇数发现还有最中心的一块点没画。while (loop--){//先记录开始的位置 当然也可以放到for当中来初始化。这边只是展示一下。i = startx;j = starty;//开始遍历 先从左往右走，发现是j在遍历，并且确定[)，要确定好边界for ( ; j < n - offset; j++){result[i][j] = count++;}//开始从上往下遍历，发现是i在变化，此时j为n-offset，发现刚好不需要进行修改for ( ; i < n - offset; i++){result[i][j] = count++;}//开始从右往左遍历，发现是j在遍历，此时j刚好也是最后一位，end为starty。for ( ; j > starty; j--){result[i][j] = count++;}//开始从下往上遍历，发现是i在遍历，此时i是最后一位，end就是startxfor ( ; i > startx; i--){result[i][j] = count++;}//此时需要更新startx，和starty，以及offset来控制begin和endstartx++;starty++;offset++;}//剩下就是发现是奇数的时候需要给最中间的赋值if (n % 2) {result[n/2][n/2] = count;}return result;
}
};

leetcode 54 螺旋矩阵

链接

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {//首先先提取该矩阵为x行y列的矩阵int lenx = matrix.size(), leny = matrix[0].size();//再按照经典的模拟算法实现。//采用[)的思想进行书写int i, j;int startx = 0, starty = 0;int offset = 1;vector<int> result;//设置循环的次数int loop = min(lenx / 2, leny / 2);//开始循环遍历while (loop--){//先初始化i j;i = startx;j = starty;//开始四次循环绕圈for ( ; j < leny - offset; j++){result.push_back(matrix[i][j]);}for ( ; i < lenx - offset; i++){result.push_back(matrix[i][j]);}for ( ; j > starty; j--){result.push_back(matrix[i][j]);}for ( ; i > startx; i--){result.push_back(matrix[i][j]);}//更新startx starty offsetstartx++;starty++;offset++;}//判断循环次数是奇数还是偶数 if (lenx < leny && lenx % 2 == 1){for (i = startx, j = starty; j < leny - offset + 1; j++){result.push_back(matrix[i][j]);}}else if(lenx >= leny && leny % 2 == 1){for (i = startx, j = starty; i < lenx - offset + 1; i++){result.push_back(matrix[i][j]);}}return result;}
};

剑指Offer 29 顺时针打印矩阵

链接

实际上题目也就是上一题的翻版，但是在提交上一题的答案的时候，你会发现会失败，进去看他传回的代码的样式，发现错误的原因就在于，他传入的数据，不符合二维数组的样式，目测看来估计是java的题目。。

所以在函数的判定最开始前加上一个判断语句就对了

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) {return {};}//首先先提取该矩阵为x行y列的矩阵int lenx = matrix.size(), leny = matrix[0].size();//再按照经典的模拟算法实现。//采用[)的思想进行书写int i, j;int startx = 0, starty = 0;int offset = 1;vector<int> result;//设置循环的次数int loop = min(lenx / 2, leny / 2);//开始循环遍历while (loop--){//先初始化i j;i = startx;j = starty;//开始四次循环绕圈for ( ; j < leny - offset; j++){result.push_back(matrix[i][j]);}for ( ; i < lenx - offset; i++){result.push_back(matrix[i][j]);}for ( ; j > starty; j--){result.push_back(matrix[i][j]);}for ( ; i > startx; i--){result.push_back(matrix[i][j]);}//更新startx starty offsetstartx++;starty++;offset++;}//判断循环次数是奇数还是偶数 if (lenx < leny && lenx % 2 == 1){for (i = startx, j = starty; j < leny - offset + 1; j++){result.push_back(matrix[i][j]);}}else if(lenx >= leny && leny % 2 == 1){for (i = startx, j = starty; i < lenx - offset + 1; i++){result.push_back(matrix[i][j]);}}return result;}
};