DAY2 数组part02

今日任务

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

977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

解法一：暴力解法（函数sort）

*C++ sort()排序详解-CSDN博客

*sort使用快排，复杂度为nlogn

 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         sort(nums.begin(),nums.end());
 9         return nums;
10     }
11 };

解法二：双指针

 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         int left=0;
 9         int right=nums.size()-1;
10         int k=nums.size()-1;
11         vector<int> result(nums.size(),0);//注意初始化语法
12         while(left<=right)
13         {
14             if(nums[left]<nums[right]) result[k--]=nums[right--];
15             else result[k--]=nums[left++];
16         }
17         return result;
18     }
19 };

 *根据平方之后数组的大小，使用双指针

209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

*滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

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

59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

 1 class Solution {
 2 public:
 3     vector<vector<int>> generateMatrix(int n) {
 4     int i,j,num,k;
 5     vector<vector<int>> a(n,vector<int>(n,0));
 6     //注意二维vector初始化
 7     k=0;
 8     num=1;
 9     while(num<=n*n)
10     {
11         i=j=k;
12         for(j=k;j<n-k-1;j++){
13             a[i][j]=num++;
14         }//j=n-1-k;
15         for(i=k;i<n-k-1;i++)
16         {
17             a[i][j]=num++;
18         }//i=n-k-1=j;
19         for(j=n-k-1;j>k;j--){
20             a[i][j]=num++;
21         }//j=k;i=n-k-1;
22         for(i=n-k-1;i>k;i--){
23             a[i][j]=num++;
24         }
25         k++;
26     }
27     return a;
28     }
29 };

 数组总结

代码随想录 (programmercarl.com)