_2LeetCode代码随想录算法训练营第二天C++

LeetCode 题目列表：

• 977.有序数组的平方
• 209.长度最小的子数组
• 59.螺旋矩阵II

977.有序数组的平方

题目所述数组含有负数。

双指针的思路

双指针的思路：

最大元素一定是在两边，考虑用两个指针逐步向中间合拢，得到一个由大到小的数组，在更新数组时也由大索引到小索引更新。

代码

/** @lc app=leetcode.cn id=977 lang=cpp** [977] 有序数组的平方*/// @lc code=start
class Solution {
public:vector sortedSquares(vector& nums) {vector result(nums.size(), 0);//初始化结果数组int index = nums.size() - 1;//初始化更新数组的indexfor(int i = 0,j = nums.size() - 1; i <= j; )//双指针往中间夹击{int muti_i = nums[i]*nums[i];//此处是为了少算一次*法int muti_j = nums[j]*nums[j];//此处是为了少算有一次*法if(muti_i > muti_j)//如果i指向的元素的平方更大{result[index--] = muti_i;//更新结果数组和更新indexi++;//更新i}else//如果i和j指向的元素的平方相等或j指向的元素的平方更大{result[index--] = muti_j;//更新结果数组和更新indexj--;//更新j}}return result;}
};
// @lc code=end

犯的错误

将这一句
for(int i = 0,j = nums.size() - 1; i <= j; )//双指针往中间夹击
写成了
for(int i = 0, int j = nums.size() - 1; i <= j; )//双指针往中间夹击
属于是低级错误

209.长度最小的子数组

暴力解法

使用两层嵌套for循环，第一层表示起始位置，第二层表示终止位置，遍历所有的情况，求得长度最小的子数组。

双指针的思路

滑动窗口的思想

只用一个for循环解决问题，那么for循环里面的索引是滑动窗口的起始位置还是终止位置呢？如果是起始位置，那么和暴力解法一样把所有的终止位置都遍历了一遍，所以是终止位置。

重点所在

那么如何决定起始位置呢？需要使用一个动态移动的策略确定。即当集合里面的所有元素和大于等于target时，就可以移动起始位置了。

代码

/** @lc app=leetcode.cn id=209 lang=cpp** [209] 长度最小的子数组*/// @lc code=start
class Solution {
public:int minSubArrayLen(int target, vector& nums) {int result = INT32_MAX;//首先将结果赋值为超大的值int subLength = 0;//表示滑动窗口的大小int i = 0;//表示滑动窗口的起始位置int sum = 0;//记录滑动窗口元素和for(int j = 0;j < nums.size();j++){sum += nums[j];//滑动窗口后移一位，就将新的滑动窗口的终止位置的元素加到sum中while(sum >= target)//当sum大于等于target时，就要更新起始位置了{subLength = j - i + 1;//求得当前滑动窗口的大小result = subLength < result ? subLength : result;//与result比较，如果比result更小则更新result为subLength；否则不更新result。sum -= nums[i++];//sum减掉滑动窗口起始位置的元素，更新i}}return result < INT32_MAX ? result : 0;}
};
// @lc code=end

时间复杂度

每个元素在滑动窗口进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

问题

在for循环中，为什么不使用if而使用while呢？

如果target = 100

可能存在这样的滑动窗口：[1, 1, 1, 1, 1, 100]

需要求得最小的result。

59.螺旋矩阵II

错误思路

处理每条边的时候，规则不统一；导致需要处理很多边界条件，这样就很容易出错。

循环不变量

循环就是一圈一圈地处理，不变量就是每条边地处理规则一样。

采用左闭右开的规则：如上图所示，处理第一行时只处理1、2；处理第三列时只处理3、4；处理第三行时只处理5、6；处理第一列时只处理7、8；对于每一个循环皆如此，直到循环结束。

代码

/** @lc app=leetcode.cn id=59 lang=cpp** [59] 螺旋矩阵 II*/// @lc code=start
class Solution {
public:vector> generateMatrix(int n) {vector> res(n, vector(n, 0));//使用vector定义一个二维数组int startx = 0,starty = 0;//定义初始位置为(0,0)int loop = n / 2;//表示执行几个圈，n为偶数时可行，但是n为基数时会忘掉中心位置的元素，这个就可以在最后做一个判断int offset = 1;//执行一圈就将其加1，目的是计算边界int data = 1;//记录数值1->2->3...->nint i,j;//相当于是索引while(loop--){i = startx, j = starty;//处理一个圈的上(左闭右开)for(; j < n - offset; j++)res[startx][j] = data++;//处理一个圈的右(左闭右开) 此时j == n - offsetfor(; i < n - offset; i++)res[i][j] = data++;//处理一个圈的下(左闭右开) 此时i == n - offset, j == n - offsetfor(; j > starty; j--)res[i][j] = data++;//处理一个圈的左(左闭右开)，此时i == n - offset, j == startyfor(; i > startx; i--)res[i][j] = data++;//处理完一圈之后，要移动初始位置和offsetstartx++;starty++;offset++;}if(n % 2 == 1)//如果n是基数，则要添加以下中心位置的元素{int mid = n / 2;res[mid][mid] = data;}return res;}
};
// @lc code=end