当前位置:   article > 正文

代码随想录算法训练营:2/60_算法随想录网站

算法随想录网站

非科班学习算法day2 | LeetCode977: 有序数组的平方,Leetcode209: 长度最小的子数组,Leetcode88: 合并有序数组,Leetcode59:螺旋矩阵||

目录

介绍

一、基础概念补充:

1.c++中的vector的构造

2.++i和i++的区别

++i(前缀自增)

i++(后缀自增)

二、LeetCode题目

1.LeetCode977: 有序数组的平方

题目解析

优化思路

2.Leetcode209: 长度最小的子数组

题目解析

优化思路

3.Leetcode88:合并有序数组

题目解析

 4.Leetcode59:螺旋矩阵

题目解析

总结


介绍

包含LC的两道题目,还有相应概念的补充。

相关图解和更多版本:

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF


一、基础概念补充:

1.c++中的vector的构造

默认构造函数:创建一个空的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的副本。

2.++ii++的区别

       ++ii++都是C语言中的自增运算符,它们的作用是使变量i的值增加1。然而,它们在使用上有所不同,具体表现在它们的值何时被更新以及如何影响表达式的计算结果。

++i(前缀自增)
  • ++i首先将i的值增加1,然后再将更新后的值用于表达式的计算。
  • 如果++i是一个独立的语句或者是一个表达式的一部分,它的值会立即更新。
i++(后缀自增)
  • i++首先将i的当前值用于表达式的计算,然后再将i的值增加1。
  • 如果i++是一个独立的语句或者是一个表达式的一部分,它的值在表达式计算完毕后才会更新。

二、LeetCode题目

1.LeetCode977: 有序数组的平方

题目链接:. - 力扣(LeetCode)

题目解析

        首先,根据题目给出的示例一可以想到:对数组元素进行平方操作,得到新数组,对新数组进行冒泡排序即可得到目标数组。

 C++代码如下:

  1. class Solution {
  2. public:
  3. vector<int> sortedSquares(vector<int>& nums) {
  4. for(int i = 0; i < nums.size();i++)
  5. {
  6. nums[i] *= nums[i];
  7. }
  8. //排序
  9. for (int i = 0; i < nums.size(); i++)
  10. {
  11. for(int j = i + 1; j < nums.size(); j++)
  12. {
  13. if (nums[j] < nums[i])
  14. {
  15. int temp = nums[i];
  16. nums[i] = nums[j];
  17. nums[j] = temp;
  18. }
  19. }
  20. }
  21. //返回目标数组
  22. return nums;
  23. }
  24. };

时间复杂度分析:进行了双层的循环嵌套,按照最坏复杂度为O(n^2)

这段代码并不困难,可以在原有数组的基础上进行更新,但是时间复杂度爆炸,虽然在LC上能通过

优化思路

        继续观察题目要求:非递减顺序,平方。首先我们可以确定数组中的数字可能有负有正,但是取平方之后,最大的数不过就是出现在数组的两头。那么就可以借助两个指针(指向需求的位置:头部和尾部)进行比较,并且生成新的数组并且作为返回值。

注意点1:边界条件设置,为了能够遍历到每一个值,不排除最后两个指针重合的情况,所以这里采用left <= right 而不是left < right

注意点2:检查条件之后,进行左/右指针的移动。

注意点3:这里新建了一个vector,并且定义了临时指针指向该vector,left和right并不对prt有任何影响,最后返回的也是这个数组。

 调整之后C++代码如下:

  1. class Solution {
  2. public:
  3. vector<int> sortedSquares(vector<int>& nums) {
  4. //左右指针指向两端
  5. //检查状态
  6. //更新数组
  7. int left = 0;
  8. int right = nums.size() - 1;
  9. vector<int>result (nums.size());
  10. for(int prt = nums.size() - 1; prt >= 0 && left <= right ; prt--)
  11. {
  12. if(nums[left] * nums[left] < nums[right] * nums[right])
  13. {
  14. result[prt] = nums[right] * nums[right];
  15. right--;
  16. }
  17. else
  18. {
  19. result[prt] = nums[left] * nums[left];
  20. left++;
  21. }
  22. }
  23. return result;
  24. }
  25. };

 时间复杂度分析:按照最坏复杂度为O(n),很有效降低了时间复杂度。

2.Leetcode209: 长度最小的子数组

题目链接:209. 长度最小的子数组 - 力扣(LeetCode)

题目解析

        遍历数组,生成目标数组的左边界;

        嵌套循环,生成目标数组的右边界;        

        对区间内的元素加和判断是否满足条件;

        返回有效数组长度

注意点1:外部循环条件设置:遍历每一个元素作为起始

注意点2:内部循环条件设置:遍历从外部循环锁定的元素[i]之后的所有元素,之后累计求和。

注意点3:这里设置minlen的原因是:除了像LC示例3这种不满足if判断的例子,还可能存在多个满足条件的子数组,这时候就需要满足最小的要求,所以在循环判断的过程中,设定一个当前最小长度的变量,有效防止仅出现一次满足大于target的数组出现就返回的现象。

注意点4:借助break,可以减少计算量。显而易见,在满足了当前搜索数组大于目标时,无需再将j向后检索。使用break跳出当前循环。

 C++代码如下: 

  1. class Solution {
  2. public:
  3. int minSubArrayLen(int target, vector<int>& nums) {
  4. int minlen = INT_MAX;
  5. int i = 0;
  6. while(i < nums.size())
  7. {
  8. int sum = 0;
  9. for(int j = i ;j < nums.size(); ++j)
  10. {
  11. sum += nums[j];
  12. if (sum >= target)
  13. {
  14. minlen = min(minlen,j - i + 1);
  15. break;
  16. }
  17. }
  18. ++i;
  19. }
  20. return (minlen == INT_MAX) ? 0 : minlen;
  21. }
  22. };

 时间复杂度分析:按照最坏复杂度为O(n^2) 

优化思路

       采用滑动窗口来进行:

       基本上还是基于左右两个边界,不过就像是一个区间版滑动变阻器,你的每次循环调试都像是测试电阻(当前值)是否满足目标电阻(条件)。

        先移动右边窗口;

        得到满足的窗口之后,移动左窗口;

        检查是否符合条件。

           

 调整之后C++代码如下:

  1. class Solution {
  2. public:
  3. int minSubArrayLen(int target, vector<int>& nums) {
  4. int left = 0;
  5. int right = 0;
  6. int sum = 0;
  7. int minlen = INT_MAX;
  8. //右窗口滑动
  9. for(; right < nums.size(); ++right)
  10. {
  11. sum += nums[right];
  12. while(sum >= target && left <= right)
  13. {
  14. minlen = min(minlen,right - left + 1);
  15. sum -= nums[left];
  16. ++left;
  17. }
  18. }
  19. return (minlen == INT_MAX) ? 0 : minlen;
  20. }
  21. };

 时间复杂度分析:按照最坏复杂度为O(n) 

3.Leetcode88:合并有序数组

题目链接:88. 合并两个有序数组 - 力扣(LeetCode)

题目解析

       以下思路借助于LC示例一给出:

        设置两个指针分别指向两个数组的起始位置;

        比对两个指针指向的大小;

        用小的数填充新建的m+n数组;

        遍历有效两个数组其中某一个的全部有效数字位置之后,检查另一个数组的剩余有效数字。

注意点1:在这里,我给出的快慢指针的说法并不准确,更好的应该是说1和2指针

注意点2:循环边界条件设置:不允许超出数组有效数字长度,这里有效数组长度指的分别是m和n

注意点3:在其中一个数组先全部填充到a(新建数组)后,要检查另一个数组的状态,将数组中剩余元素添加到新数组中。再次说明,新建数组之后,这三个指针相对独立,不会影响循环取值。

注意点4:根据题目要求,最后替换nums1.

C++代码如下:

  1. class Solution {
  2. public:
  3. void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  4. //借助双指针
  5. //定义快指针指向数组2
  6. //定义慢指针指向数组1
  7. int fast = 0;
  8. int slow = 0;
  9. int prt = 0;
  10. vector<int>a (m+n);
  11. while(slow < m && fast < n && prt < m + n)
  12. {
  13. if(nums2[fast] >= nums1[slow])
  14. {
  15. a[prt] = nums1[slow];
  16. slow++;
  17. }
  18. else
  19. {
  20. a[prt] = nums2[fast];
  21. fast++;
  22. }
  23. prt++;
  24. }
  25. while(slow < m)
  26. {
  27. a[prt] = nums1[slow];
  28. slow++;
  29. prt++;
  30. }
  31. while(fast < n)
  32. {
  33. a[prt] = nums2[fast];
  34. fast++;
  35. prt++;
  36. }
  37. for(int i = 0; i < m+n; i++)
  38. {
  39. nums1[i] = a[i];
  40. }
  41. }
  42. };

 补充:这道题只要说新建空间其实并不算很困难,一开始我沉浸在正向遍历,而且还想不新建空间,最后发现问题的复杂度大大增加。我们假设在数组1中插入数组2,那就要检查数组2中的元素在数组1中元素的相对位置,然后将其插入,数组1的元素向后移动,时间复杂度也爆炸,我还想用数组2来交换数组1的元素,原谅我太菜了,无果。

下面给出一种后向遍历的方法,不用新开辟空间

c++代码如下:

  1. class Solution {
  2. public:
  3. void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  4. int p1 = m - 1;
  5. int p2 = n - 1;
  6. int p = m + n - 1;
  7. while(p1 >= 0 && p2 >= 0 && p >= 0)
  8. {
  9. if (nums1[p1] > nums2[p2])
  10. {
  11. nums1[p] = nums1[p1];
  12. p1--;
  13. }
  14. else
  15. {
  16. nums1[p] = nums2[p2];
  17. p2--;
  18. }
  19. p--;
  20. }
  21. //处理剩余nums2,因为此时没有开辟新空间,极端情况是要么num2全部比num1小
  22. //此时相当于移动了整个num1;要么是nums2全部插入
  23. while(p2 >= 0)
  24. {
  25. nums1[p] = nums2[p2];
  26. p--;
  27. p2--;
  28. }
  29. }
  30. };

以上代码运行之后发现示例3跑不过,即nums1 = [0],m = 0的情况, 头部添加检查:

  1. if(m == 0)
  2. {
  3. nums1 = nums2;
  4. }

 4.Leetcode59:螺旋矩阵

题目链接:59. 螺旋矩阵 II - 力扣(LeetCode)

题目解析

       以下思路借助于LC示例给出:

        首先给定循环的边界条件,四个边界;

        预先定义需要作为容器的矩阵matrix;

        按照左开右闭的原则遍历四条边;

        检查元素遗漏。

注意点1:vector里面是可以再放vector的,这也是C++常见的矩阵创建方式,详细见前面说的vector构造。

注意点2:最重要的无疑是边界条件的设置。设置了四个初始边界之后,我们要清楚,自己写的遍历,每一次不变的是什么,变的是什么。

比如在遍历第一行时候,明显变化的是纵坐标,也就是martix[~][i]里的i在变化,它的变化区间是什么?是左闭右开。这样子就可以一步一步确定遍历的条件。当然,外部循环的条件就是,边界不允许交叉。

注意点3:最后设置了一个检查,根据实例,不难发现,如果数字为奇数,比如3,那么最后(9)肯定会有一个单独的中心点,所以我们检查是否为奇数,如果是,那么就单独填补一下这个数字。

 C++代码如下:

  1. class Solution {
  2. public:
  3. vector<vector<int>> generateMatrix(int n) {
  4. //模拟螺旋顺序
  5. //坚持左闭右开原则
  6. //预分配
  7. vector<vector<int>> matrix(n, vector<int>(n, 0));
  8. //定义循环变量
  9. int left = 0;
  10. int right = n - 1;
  11. int top = 0;
  12. int bottom = n - 1;
  13. int mid = n / 2;
  14. int r = 0;
  15. while(left <= right && top <= bottom)
  16. {
  17. //遍历第一条边
  18. for(int i = left; i< right; i++)
  19. {
  20. matrix[top][i] = ++r;
  21. }
  22. top++; //向下一行
  23. //遍历第二条边
  24. for(int j = top - 1; j < bottom; j++)
  25. {
  26. matrix[j][right] = ++r;
  27. }
  28. right--;
  29. //遍历第三条边
  30. for(int i = right + 1; i > left; i--)
  31. {
  32. matrix[bottom][i] = ++r;
  33. }
  34. bottom--;
  35. //遍历第四条边
  36. for(int j = bottom + 1; j > top - 1; j--)
  37. {
  38. matrix[j][left] = ++r;
  39. }
  40. left++;
  41. }
  42. if(n % 2)
  43. {
  44. matrix[mid][mid] = ++r;
  45. }
  46. return matrix;
  47. }
  48. };

总结


打卡第二天,坚持!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/973826
推荐阅读
相关标签
  

闽ICP备14008679号