算法训练营第四天| 模拟算法

一、今日学习任务今日任务59. 螺旋矩阵 II 总结数组类题型解题框架题目建议本题关键还是在转圈的逻辑在二分搜索中提到的区间定义在这里又用上了。题目链接https://leetcode.cn/problems/spiral-matrix-ii/视频讲解https://www.bilibili.com/video/BV1SL4y1N7mV/二、自己看到题目的第一想法看到顺时针螺旋填充第一反应是一圈一圈往里填需要确定每圈的起止位置以及每条边怎么走跟二分法类似边界条件很重要每条边都要保持统一的区间规则比如左闭右开不然容易乱。三、实现过程中遇到哪些困难1、区间不一致第一条边填了最后一个拐角下条边又从同一个拐角开始导致重复填充。后来统一用左闭右开每条边只填到拐角前一个位置。2、奇数n的中心点n是奇数时最中间一个格子需要单独处理容易漏掉。3、循环次数一圈填完要转n/2圈n为奇数时最后补中心。四、代码是怎么实现的思路定义上下左右四个边界每圈按上→右→下→左的顺序填充每条边保持左闭右开只填到最后一个元素前填完一圈后收缩边界。class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorint res(n, vectorint(n, 0)); int num 1; int left 0, right n - 1; int top 0, bottom n - 1; while (left right top bottom) { // 上边从左到右 for (int i left; i right; i) { res[top][i] num; } top; // 右边从上到下 for (int i top; i bottom; i) { res[i][right] num; } right--; // 下边从右到左 if (top bottom) { for (int i right; i left; i--) { res[bottom][i] num; } bottom--; } // 左边从下到上 if (left right) { for (int i bottom; i top; i--) { res[i][left] num; } left; } } return res; } };五、今日收获心得1、螺旋矩阵的关键是保持区间定义一致每条边的处理规则要统一2、用边界收缩法left/right/top/bottom比较直观不容易出错3、这道题是模拟类题目的典型代表把一圈圈的逻辑拆清楚就好写了4、对边界条件有很好的锻炼做完之后对“循环不变量”的理解更深了和第一天的二分法其实是同一个道理。