赞
踩
非科班学习算法day2 | LeetCode977: 有序数组的平方,Leetcode209: 长度最小的子数组,Leetcode88: 合并有序数组,Leetcode59:螺旋矩阵||
目录
包含LC的两道题目,还有相应概念的补充。
相关图解和更多版本:
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
默认构造函数:创建一个空的vector
。
std::vector<T> vec;
填充构造函数:创建一个包含n
个复制自val
的元素的vector
。
std::vector<T> vec(n, val);
范围构造函数:根据迭代器范围[first, last)
创建一个vector
。
std::vector<T> vec(first, last);
拷贝构造函数:创建一个新的vector
,作为现有vector
的副本。
++i
和i++
的区别 ++i
和i++
都是C语言中的自增运算符,它们的作用是使变量i
的值增加1。然而,它们在使用上有所不同,具体表现在它们的值何时被更新以及如何影响表达式的计算结果。
++i
(前缀自增)++i
首先将i
的值增加1,然后再将更新后的值用于表达式的计算。++i
是一个独立的语句或者是一个表达式的一部分,它的值会立即更新。i++
(后缀自增)i++
首先将i
的当前值用于表达式的计算,然后再将i
的值增加1。i++
是一个独立的语句或者是一个表达式的一部分,它的值在表达式计算完毕后才会更新。题目链接:. - 力扣(LeetCode)
题目解析
首先,根据题目给出的示例一可以想到:对数组元素进行平方操作,得到新数组,对新数组进行冒泡排序即可得到目标数组。
C++代码如下:
- class Solution {
- public:
- vector<int> sortedSquares(vector<int>& nums) {
- for(int i = 0; i < nums.size();i++)
- {
- nums[i] *= nums[i];
- }
-
- //排序
- for (int i = 0; i < nums.size(); i++)
- {
- for(int j = i + 1; j < nums.size(); j++)
- {
- if (nums[j] < nums[i])
- {
- int temp = nums[i];
- nums[i] = nums[j];
- nums[j] = temp;
- }
- }
- }
-
- //返回目标数组
- return nums;
- }
- };

时间复杂度分析:进行了双层的循环嵌套,按照最坏复杂度为O(n^2)
这段代码并不困难,可以在原有数组的基础上进行更新,但是时间复杂度爆炸,虽然在LC上能通过
优化思路
继续观察题目要求:非递减顺序,平方。首先我们可以确定数组中的数字可能有负有正,但是取平方之后,最大的数不过就是出现在数组的两头。那么就可以借助两个指针(指向需求的位置:头部和尾部)进行比较,并且生成新的数组并且作为返回值。
注意点1:边界条件设置,为了能够遍历到每一个值,不排除最后两个指针重合的情况,所以这里采用left <= right 而不是left < right
注意点2:检查条件之后,进行左/右指针的移动。
注意点3:这里新建了一个vector,并且定义了临时指针指向该vector,left和right并不对prt有任何影响,最后返回的也是这个数组。
调整之后C++代码如下:
- class Solution {
- public:
- vector<int> sortedSquares(vector<int>& nums) {
- //左右指针指向两端
- //检查状态
- //更新数组
-
- int left = 0;
- int right = nums.size() - 1;
-
- vector<int>result (nums.size());
-
- for(int prt = nums.size() - 1; prt >= 0 && left <= right ; prt--)
- {
- if(nums[left] * nums[left] < nums[right] * nums[right])
- {
- result[prt] = nums[right] * nums[right];
- right--;
- }
- else
- {
- result[prt] = nums[left] * nums[left];
- left++;
- }
- }
- return result;
-
- }
- };

时间复杂度分析:按照最坏复杂度为O(n),很有效降低了时间复杂度。
题目链接:209. 长度最小的子数组 - 力扣(LeetCode)
题目解析
遍历数组,生成目标数组的左边界;
嵌套循环,生成目标数组的右边界;
对区间内的元素加和判断是否满足条件;
返回有效数组长度
注意点1:外部循环条件设置:遍历每一个元素作为起始
注意点2:内部循环条件设置:遍历从外部循环锁定的元素[i]之后的所有元素,之后累计求和。
注意点3:这里设置minlen的原因是:除了像LC示例3这种不满足if判断的例子,还可能存在多个满足条件的子数组,这时候就需要满足最小的要求,所以在循环判断的过程中,设定一个当前最小长度的变量,有效防止仅出现一次满足大于target的数组出现就返回的现象。
注意点4:借助break,可以减少计算量。显而易见,在满足了当前搜索数组大于目标时,无需再将j向后检索。使用break跳出当前循环。
C++代码如下:
- class Solution {
- public:
- int minSubArrayLen(int target, vector<int>& nums) {
- int minlen = INT_MAX;
- int i = 0;
- while(i < nums.size())
- {
- int sum = 0;
- for(int j = i ;j < nums.size(); ++j)
- {
- sum += nums[j];
- if (sum >= target)
- {
- minlen = min(minlen,j - i + 1);
- break;
- }
- }
- ++i;
- }
- return (minlen == INT_MAX) ? 0 : minlen;
- }
- };

时间复杂度分析:按照最坏复杂度为O(n^2)
优化思路
采用滑动窗口来进行:
基本上还是基于左右两个边界,不过就像是一个区间版滑动变阻器,你的每次循环调试都像是测试电阻(当前值)是否满足目标电阻(条件)。
先移动右边窗口;
得到满足的窗口之后,移动左窗口;
检查是否符合条件。
调整之后C++代码如下:
- class Solution {
- public:
- int minSubArrayLen(int target, vector<int>& nums) {
- int left = 0;
- int right = 0;
- int sum = 0;
- int minlen = INT_MAX;
-
- //右窗口滑动
- for(; right < nums.size(); ++right)
- {
- sum += nums[right];
- while(sum >= target && left <= right)
- {
- minlen = min(minlen,right - left + 1);
- sum -= nums[left];
- ++left;
- }
- }
- return (minlen == INT_MAX) ? 0 : minlen;
-
- }
- };

时间复杂度分析:按照最坏复杂度为O(n)
题目链接:88. 合并两个有序数组 - 力扣(LeetCode)
题目解析
以下思路借助于LC示例一给出:
设置两个指针分别指向两个数组的起始位置;
比对两个指针指向的大小;
用小的数填充新建的m+n数组;
遍历有效两个数组其中某一个的全部有效数字位置之后,检查另一个数组的剩余有效数字。
注意点1:在这里,我给出的快慢指针的说法并不准确,更好的应该是说1和2指针
注意点2:循环边界条件设置:不允许超出数组有效数字长度,这里有效数组长度指的分别是m和n
注意点3:在其中一个数组先全部填充到a(新建数组)后,要检查另一个数组的状态,将数组中剩余元素添加到新数组中。再次说明,新建数组之后,这三个指针相对独立,不会影响循环取值。
注意点4:根据题目要求,最后替换nums1.
C++代码如下:
- class Solution {
- public:
- void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
-
- //借助双指针
- //定义快指针指向数组2
- //定义慢指针指向数组1
- int fast = 0;
- int slow = 0;
- int prt = 0;
-
- vector<int>a (m+n);
-
- while(slow < m && fast < n && prt < m + n)
- {
- if(nums2[fast] >= nums1[slow])
- {
- a[prt] = nums1[slow];
- slow++;
- }
- else
- {
- a[prt] = nums2[fast];
- fast++;
- }
- prt++;
- }
- while(slow < m)
- {
- a[prt] = nums1[slow];
- slow++;
- prt++;
- }
- while(fast < n)
- {
- a[prt] = nums2[fast];
- fast++;
- prt++;
- }
-
- for(int i = 0; i < m+n; i++)
- {
- nums1[i] = a[i];
- }
- }
- };

补充:这道题只要说新建空间其实并不算很困难,一开始我沉浸在正向遍历,而且还想不新建空间,最后发现问题的复杂度大大增加。我们假设在数组1中插入数组2,那就要检查数组2中的元素在数组1中元素的相对位置,然后将其插入,数组1的元素向后移动,时间复杂度也爆炸,我还想用数组2来交换数组1的元素,原谅我太菜了,无果。
下面给出一种后向遍历的方法,不用新开辟空间
c++代码如下:
- class Solution {
- public:
- void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
- int p1 = m - 1;
- int p2 = n - 1;
- int p = m + n - 1;
-
- while(p1 >= 0 && p2 >= 0 && p >= 0)
- {
- if (nums1[p1] > nums2[p2])
- {
- nums1[p] = nums1[p1];
- p1--;
- }
- else
- {
- nums1[p] = nums2[p2];
- p2--;
- }
- p--;
- }
-
- //处理剩余nums2,因为此时没有开辟新空间,极端情况是要么num2全部比num1小
- //此时相当于移动了整个num1;要么是nums2全部插入
-
- while(p2 >= 0)
- {
- nums1[p] = nums2[p2];
- p--;
- p2--;
- }
-
- }
- };

以上代码运行之后发现示例3跑不过,即nums1 = [0],m = 0的情况, 头部添加检查:
- if(m == 0)
- {
- nums1 = nums2;
- }
题目链接:59. 螺旋矩阵 II - 力扣(LeetCode)
题目解析
以下思路借助于LC示例给出:
首先给定循环的边界条件,四个边界;
预先定义需要作为容器的矩阵matrix;
按照左开右闭的原则遍历四条边;
检查元素遗漏。
注意点1:vector里面是可以再放vector的,这也是C++常见的矩阵创建方式,详细见前面说的vector构造。
注意点2:最重要的无疑是边界条件的设置。设置了四个初始边界之后,我们要清楚,自己写的遍历,每一次不变的是什么,变的是什么。
比如在遍历第一行时候,明显变化的是纵坐标,也就是martix[~][i]里的i在变化,它的变化区间是什么?是左闭右开。这样子就可以一步一步确定遍历的条件。当然,外部循环的条件就是,边界不允许交叉。
注意点3:最后设置了一个检查,根据实例,不难发现,如果数字为奇数,比如3,那么最后(9)肯定会有一个单独的中心点,所以我们检查是否为奇数,如果是,那么就单独填补一下这个数字。
C++代码如下:
- class Solution {
- public:
- vector<vector<int>> generateMatrix(int n) {
- //模拟螺旋顺序
- //坚持左闭右开原则
-
- //预分配
- vector<vector<int>> matrix(n, vector<int>(n, 0));
- //定义循环变量
- int left = 0;
- int right = n - 1;
- int top = 0;
- int bottom = n - 1;
-
- int mid = n / 2;
- int r = 0;
- while(left <= right && top <= bottom)
- {
- //遍历第一条边
- for(int i = left; i< right; i++)
- {
- matrix[top][i] = ++r;
- }
- top++; //向下一行
-
- //遍历第二条边
- for(int j = top - 1; j < bottom; j++)
- {
- matrix[j][right] = ++r;
- }
- right--;
-
- //遍历第三条边
- for(int i = right + 1; i > left; i--)
- {
- matrix[bottom][i] = ++r;
- }
- bottom--;
-
- //遍历第四条边
- for(int j = bottom + 1; j > top - 1; j--)
- {
- matrix[j][left] = ++r;
- }
- left++;
- }
- if(n % 2)
- {
- matrix[mid][mid] = ++r;
- }
- return matrix;
- }
-
- };

打卡第二天,坚持!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。