代码随想录训练营day02

第一章数组part02

1.Leetcode 有序数组的平方

1.1.题目链接 977.有序数组的平方

文章讲解：代码随想录
视频讲解：卡哥B站视频

1.2 思路：看到本题目的第一反应是采用两步走形式，首先将数组元素进行平方化，然后将所得新数组进行排序进而得到满足要求的数组。没有考虑到本体也可以采用双指针形式，由于题目中数组元素是按照大小顺序排列的可以采用做右指针形式，通过对比每次的左右指针所指带元素的绝对值或者平方，然后将大的值放入到新数组的最后，以此进行从两边向中间遍历的方式得到所有元素的平方。

1.3 附加代码如下所示：

（1）暴力列举法，时间复杂度为 O（n×n）

class Solution{
    public:
    vector<int>sortedSquares(vector<int>& nums){
           
            for(int i=0;i<nums.size();i++)
            {
                nums[i]*=nums[i];
            }
            sort(nums.begin(),nums.end());
            return nums;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）双指针法时间复杂度为 O（n）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        
        int right=nums.size()-1;
        int flag=nums.size()-1;
        int length=nums.size();
        vector<int>result(length,0);
        for(int left=0,right=length-1;left<=right;)
        {
            if(nums[left]*nums[left]>nums[right]*nums[right])
            {
                result[flag--]=nums[left]*nums[left];
                left++;

            }
            else
            {
                result[flag--]=nums[right]*nums[right];
                right--;
            }

        }
        return result;

    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Leetcode.长度最小的子数组

2.1题目链接：209.长度最小的子数组

文章讲解：代码随想录
视频讲解：卡哥B站视频

2.2思路：看到该题没有思路，感觉是暴力列举法也写不完整，写了半天暴力列举法，采用两个for循环，后面的细节确实总出问题；看了卡哥的视频讲解学会了采用滑动窗口也即双指针思想可以更简单的完成题目要求。所谓滑动窗口就是采用一前一后两个指针维持一个不断移动的窗口元素，使其满足窗口内的元素之和大于等于给定值。两个指针起始点一样，快指针进行遍历直到满足所遍历的元素之和大于等于给定值，然后再进行慢指针的向前移动，如果移动之后仍然满足条件就继续移动慢指针，知道不满足条件退出循环，即可得到所寻求的最小子数组长度。

2.3附加代码实现如下所示：

（1）暴力解法：时间复杂度 O(n×n)

//暴力列举法
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum=0;
        int result=INT32_MAX;//代表32位有符号最大值，这是C++中宏定义
        int minlength=0;//子序列长度
        for(int i=0;i<nums.size();i++)//子序列起始位置从i
        {
            sum=0;//每遍历一次循环sum值要重新归零
            for(int j=i;j<nums.size();j++)//子序列终止位置从j
            {
                sum+=nums[j];
                if(sum>=target)
                {
                    minlength=j-i+1;
                    result=result<minlength ?result:minlength;
                    break;//跳出循环，已经找到所寻找的子序列
                }
            }
        }
        return result==INT32_MAX?0:result;//没有被赋值的话就返回零否则就是所求子序列的长度


    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

(2)双指针法：时间复杂度 O(n)

//双指针法也为滑动窗口法
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
            int i=0;//慢指针
            int sum=0;//子数组和
            int result=INT32_MAX;
            int sublength=0;//滑动窗口长度大小，也即子序列长度
            for(int j=0;j<nums.size();j++)//快指针
            {
                sum+=nums[j];
                while(sum>=target)//这里不能用if而是用while，是因为如果sum值一直大于target就可以继续慢指针移动
                {
                    sublength=j-i+1;
                    sum=sum-nums[i++];
                    result=result<sublength?result:sublength;
                   
                }
            }
            return result==INT32_MAX?0:result;//result被赋值的话就返回该值，没有的话就返回零
        

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Leetcode 螺旋矩阵Ⅱ

3.1题目链接：59.螺旋矩阵Ⅱ

文章讲解：代码随想录
视频讲解：卡哥B站视频

3.2思路：本题目没接触过，思路一点没有 ，看了卡哥的视频，要遵循循环不变量原则，这样才能保持每次遍历的时候都保持一致，螺旋矩阵每遍历一圈，行列都是减少2，所以遍历的圈数就是n/2,奇数的情况需要单独考虑，奇数情况遍历完后会剩下一个1×1矩阵，单独处理。

3.3附加代码如下所示：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>res(n,vector<int>(n,0));
        int startx=0;//遍历的列起始点
        int starty=0;//遍历的行起始点
        int loop=n/2;//要进行的循环遍历圈数
        int offset=1;//需要控制的每遍历完一圈要收缩一位
        int count=1;//给数组元素赋值的
        int mid=n/2;//对n为奇数特殊情况，另外处理最后一圈剩余的单独数组元素赋值
        int i,j;
        
        while(loop--)
        {
            i=startx;
            j=starty;
            //模拟填充上行从左到右（左闭右开）
            for( j=starty;j<n-offset;j++)//在这里切勿使用for(int j=starty;j<n-offset;j++) 不然在循环中声明了int j，那么它将会覆盖外部的j
            {
                res[startx][j]=count++;
            }

            //模拟填充右列从上到下（满足上闭下开）
            for( i=startx;i<n-offset;i++)
            {
                res[i][j]=count++;
            }

            //模拟填充下行从右到左（满足右闭左开）
            for(;j>starty;j--)//这里的j是继承前面的j的值所以不需要再重新赋值，同理下面的for循环里的i
            {
                res[i][j]=count++;
            }

            //模拟填充左列从下到上（满足下闭上开）
            for(;i>startx;i--)
            {
                res[i][j]=count++;
            }
            startx++;
            starty++;
            offset+=1;
        }
        //给n为奇数情况最后剩余的中间位置单独赋值
        if(n%2)
        {
            res[mid][mid]=count;
        }
        return res;

    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

总结：在写代码时候区别：for( j=starty;j<n-offset;j++)与for(int j=starty;j<n-offset;j++)差异