北京企迪网站建设公司,佛山企业网站排名,长春如何建立一个平台网站,什么网站做家电测评文章目录 基本算法思想leetcode 59 螺旋矩阵 IIleetcode 54 螺旋矩阵剑指Offer 29 顺时针打印矩阵 基本算法思想
建议先去把题目看了#xff0c;再来思考相关的代码。
错误的想法#xff1a;实际上这种题型并不存在算法#xff0c;只涉及到模拟#xff0c;但是模拟难度并… 文章目录 基本算法思想leetcode 59 螺旋矩阵 IIleetcode 54 螺旋矩阵剑指Offer 29 顺时针打印矩阵 基本算法思想
建议先去把题目看了再来思考相关的代码。
错误的想法实际上这种题型并不存在算法只涉及到模拟但是模拟难度并不是很基础所以逐渐演变到面试官考察的常见题型之一。
建议按照左闭右开的原则见下图同种颜色代表着是同层循环所作的事情从一开始就定义好进行循环。 这也就是循环不变量的思想。
理解了循环不变量的思想接下来来进行介绍一下代码书写的基本思想以及格式。
vectorvectorint generateMatrix(int n) {vectorvectorint res(n, vectorint(n, 0)); // 使用vector定义一个二维数组int startx 0, starty 0; // 定义每循环一个圈的起始位置int loop n / 2; // 每个圈循环几次例如n为奇数3那么loop 1 只是循环一圈矩阵中间的值需要单独处理int mid n / 2; // 矩阵中间的位置例如n为3 中间的位置就是(11)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:vectorvectorint generateMatrix(int n) {vectorvectorint result(n, vectorint (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:vectorint spiralOrder(vectorvectorint matrix) {//首先先提取该矩阵为x行y列的矩阵int lenx matrix.size(), leny matrix[0].size();//再按照经典的模拟算法实现。//采用[)的思想进行书写int i, j;int startx 0, starty 0;int offset 1;vectorint 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:vectorint spiralOrder(vectorvectorint 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;vectorint 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;}
};
