合作做网站的总结和心得,网站程序包括数据库和网页程序,深圳网站制作十年乐云seo品牌,网站关键词更换了 day2 2023.11.30 代码随想录
1. 977有序数组的平方 第二天做题就遇到点问题了#xff0c;首先对于该题#xff0c;简单的暴力平方排序肯定没问题#xff0c;但一定不是我们要的最优解#xff0c;我们争取在O(n)的时间复杂度内解决问题#xff0c;发现对于一个初始数组… day2 2023.11.30 代码随想录
1. 977有序数组的平方 第二天做题就遇到点问题了首先对于该题简单的暴力平方排序肯定没问题但一定不是我们要的最优解我们争取在O(n)的时间复杂度内解决问题发现对于一个初始数组平方后的最大值一定是在两边的。因此可以同时从两边开始索引处理也就是昨天做的双指针思想。 但是在开始动手后出了问题开始想在原始数组上进行更新但是逻辑理不清。我的想法是对比两个指针的平方较大得更新末尾指针较小的存储在一个temp中用于下一次循环判断感觉思路是可以的但实现起来就有问题首先每次循环需要跟上一次temp判断在两者进行对比。两层if嵌套。。。屎山代码得感觉了。其次在后续更新中也有点问题每次只能更新一个快指针值但会有剩余值无法更新因此该思路哪怕可行但过于繁琐。看了一眼代码随想录正解发现重新定义了个result数组。。。直接傻眼了茅塞顿开。。 因此最终声明两个快慢索引在for循环更新到result中即可代码如下
class Solution {
public:vectorint sortedSquares(vectorint nums) {vectorint result(nums.size());int lowindex 0;int fastindexnums.size()-1;for(int inums.size()-1; i0;i--){if(nums[fastindex]*nums[fastindex]nums[lowindex]*nums[lowindex]){result[i] nums[fastindex]*nums[fastindex];fastindex--;}else{result[i] nums[lowindex]*nums[lowindex];lowindex;}}return result;}
};2. 209长度最小的子数组 这个题有些难度首先最直观的做法就是暴力循环两层佛如第一层for是子数组内层for是找到符合要求的最小数组尝试写了写该暴力方法测试通过但提交后当数值过大时出现时间超出限制得问题因此显然不是最优解
//暴力遍历法
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int RlengthINT32_MAX;int sum;int SLength;for(int i0;inums.size();i){sum0;SLength0;for(int ji;jnums.size();j){sumnums[j];SLength;if(sumtarget){Rlength SLength Rlength ? SLength:Rlength;break;}}}return RlengthINT32_MAX? 0:Rlength;}
};本题真正做法则是滑动窗口法该方法确实不太了解因此直接看代码随想录文字讲解自己在尝试写代码暴力法中两层for代表了数组起始位置和终止位置因此滑动窗口则是一个for解决两个问题那么是该控制起始位置还是终止位置呢显然如果控制起始位置那怎么找终止位置因为找终止位置得过程一定是需要遍历得因此滑动窗口得for循环中心是控制终止位置当然需要通知控制起始位置因此也需要两个指针也是双指针得思想。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int RLengthINT32_MAX;int sum0;int SLength0;for(int j0, i0;jnums.size();j){sum nums[j];// SLength;while(sumtarget){// SLength--;SLength (j-i1);RLength RLengthSLength ? RLength:SLength;sum -nums[i];}}return RLengthINT32_MAX ? 0:RLength;}
};开始我在写代码时使用的是注释掉的方法记录子数组的长度并且在暴力方法时也是这样但这里出现了问题想着如果总和超了起始位置前进时数组长度减一就好了但有一种情况如果现在超了但减一后又不够你如果提前减一在记录长度就有问题长度应该是减一之前的长度记录到这里突然灵光一闪本来放弃了原本记录长度的方法但是突然发现问题所在了尝试将两行代码位置互换先记录长度在减少。就通过啦
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int RLengthINT32_MAX;int sum0;int SLength0;for(int j0, i0;jnums.size();j){sum nums[j];SLength;while(sumtarget){RLength RLengthSLength ? RLength:SLength; //这里SLength--; //这里sum -nums[i];}}return RLengthINT32_MAX ? 0:RLength;}
};因此该方法我个人认为有个混淆点就是在前进起始位置时前进与更新长度的顺序问题应该是先更新位置再前进起始位置。while中带等号。 总体表达意思在终止位置固定时哎呦现在子数组之和满足要求了唉那我先记录下来目前的长度再尝试将起始位置前进一下咦依然满足啊那就再前进一下。。。哦不满足啦那最小的就是我上一个记录的啦再比较与不同终止位置时的最小长度更新最终最小长度ok结束
3. 59螺旋矩阵 螺旋矩阵很久之前写过但又忘了借此机会复习一下自己写的时候以为两层for循环更新行列值想了很久该怎么组织逻辑关系理不清最后看代码随想录文字讲解是按照每一圈为一个循环每次循环分为四部–上右下左的顺序赋值达到目的不过变量有点多开始没有写遍历长度这个变量测试通过但当n4时就报错了最后理一遍所有变量 首先每层循环的起始点不一样因此需要两个变量为每次循环提供起始点并在循环结束后加1. 其次二维数组的索引肯定需要两个变量 之后对于n的奇偶不同结果不同如果是偶数则循环为整数不会落单。但如果为奇数比如3想一想一圈处理后只剩中间一个因此需要特殊处理所以需要一个变量代表中间索引 然后肯定需要一个变量控制循环次数也就是要处理几圈。 最后也是我最开始忽略的每一次循环的每一步处理到哪里结束开始以为就是n-1但这是最外圈的如果n大一些比如4在第二圈循环中每一步少两个位置因此减2.所以需要一个控制遍历处理长度的遍历。 最终结果如下
class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorint result(n, vectorint(n));int startx0,starty0; //位置int loop n/2; //循环几次int count1; //赋值int mid n/2; //单独处理中间int i,j;int length 1;while(loop--){i startx;j starty;for(jstarty;jn-length;j){ //上行左闭右开result[i][j] count;}for(istartx;in-length;i){ //右列 上闭下开result[i][j] count;}for(;jstarty;j--){ //下行右闭左开result[i][j] count;}for(;istartx;i--){ //左列下闭上开result[i][j] count;}startx;starty;length;}if(n%2){result[mid][mid] n*n; //奇数时单独处理}return result;}
};
