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

学习链接

题目链接：

https://leetcode.cn/problems/squares-of-a-sorted-array/

https://leetcode.cn/problems/minimum-size-subarray-sum/

https://leetcode.cn/problems/spiral-matrix-ii/

文章链接：

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://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://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

视频链接：

https://www.bilibili.com/video/BV1QB4y1D7ep

https://www.bilibili.com/video/BV1tZ4y1q7XE

https://www.bilibili.com/video/BV1SL4y1N7mV/

第一想法

有序数组的平方

题目给出一个非递减的整数型数组（可能包含负数），需要返回一个非递减且原数组经过平方之后的新数组。要求时间复杂度为O(n）。

初步想法：将数组中每个值平方得到一个新的数组，之后对数组进行排序。

思考二：由于没有内存的限制，可以利用一个辅助数组。先对原数组中每个元素平方，同时将其排序后插入到新数组。

思考三：先对原数组中的值取绝对值，进行一个非递减排序后，再挨个平方组成新的数组。

长度最小的子数组

这个问题一看就有点难。

思路一：暴力求解，相当于双指针求解。直接两层for循环，遍历的找。第一层for循环决定起点，第二层for循环看加到第几个数。如果加起来超过了目标值，则退出。如果没超过目标值，就往后移。等于目标值的时候，记录长度。用一个变量来记录最小长度。

思路二：首先一个一个的看，是否有对应的目标值。之后两个块一起看，是否有满足的序列，有则返回序列长度，没有则三个快一起看。两个快可以用i 和i+1 ,这样来表示。不知道这是不是滑动窗口。

螺旋矩阵II

看完代码随想录之后的想法

有序数组的平方

题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

最初实现：

部分结果正确，但是提交会出现超时问题。排序算法可以优化一下

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int length = nums.size();
        int middle;
        for(int i = 0; i < length; i++){
            nums[i] = nums[i] * nums[i];  
        }
        for(int j = 0; j < length; j++){
            for(int k = 0; k < length-1; k++){
                if(nums[k] > nums[k + 1]){
                    middle = nums[k];
                    nums[k] = nums[k + 1];
                    nums[k + 1] = middle;
                }
            }
        }
        return nums;
    }
};

#优化后的代码：
#（1）暴力破解法 时间复杂度是 O(n + nlogn)
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
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

利用双指针法，两个指针i和j，分别指向起始和结束位置，依次从数组两端挑选最大的数。放到一个新的数组中，新数组的指针指向终止位置，以此从后往前填充。斯巴拉西。

双指针法真好用。

#依照双指针思路写的代码  时间复杂度为O(n)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int  length = nums.size()-1;
        int j = length;
        int i = 0;
        vector<int> result(nums.size(), 0);

        while(i <= j){
            int double_i = nums[i] * nums[i];
            int double_j = nums[j] * nums[j];
            if(double_i > double_j){
                result[length--] = double_i;
                i++;
            }else{
                result[length--] = double_j;
                j--;
            }
        }
        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

需要注意的点包括：双指针思路，vector 变量定义。（C++ 还是不熟，得加快学习速度）。

长度最小的子数组

题目：

给定一个含有 n ****个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ****≥ target **的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。

自己思路：

1）暴力解法—先两个两个加起来看超不超过，两个没有超过的，那就三个连续的加起来。可能会有多个符合的，但是只需要返回长度，所以找到一个就行。有从小到大长度去试和从大到小去试两种思路。

2）暴力解法2：用两个变量指示窗口，i，j。然后两层for循环。

初始代码：

显示超过了时间限制，也不知道有没有bug。（有的，当不满足，返回0）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int length = nums.size() - 1;
        int min = 1;
        int sum = 0;

        while(sum < target){
            for(int i = 0; i <= length; i++){
                int sum = 0;
                for(i = 0; i < min; i++){
                    sum += nums[i];
            }
            if(sum >= target){
                break;
            }else{
                min++;
            }
            }
        }
        return min;
    }
};

#两层for循环，暴力解法
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

滑动窗口：不断调节子序列的起始位置和终止位置，从而得出我们想要的结果。

只用一个for循环，应该表示的是遍历的终止位置。

我之前自己思考从大往小去找的思路跟这个很像。

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

牛逼！

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0;  //滑动窗口中总数之和
        int i = 0;    //滑动窗口起始位置
        int sublength = 0;   //滑动窗口的长度
        for(int j = 0; j < nums.size(); j++){
            sum += nums[j];
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while(sum >= target){
                sublength = (j - i + 1);   // 取子序列的长度
                result = result > sublength? sublength : result;
                sum -= nums[i++];   // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        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

• 时间复杂度：O(n)
• 空间复杂度：O(1)

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

螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qstntN6u-1685171525400)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1cb7305b-78a9-40f9-91bf-e052b105fa22/Untitled.png)]

自己思路：首先，生成1-n平方的所有元素，不难。关于排序，最初想法是找规律。但是针对奇偶数，不同排的情况各不一样，应该不能这样做。想了十分钟，没有思路，直接看解析。

代码随想录思路：本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。一定要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n,0));  // 使用vector定义一个二维数组
        int startx = 0, starty = 0;   // 定义每循环一个圈的起始位置
        int loop = n / 2;    // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2;    // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1;   // 用来给矩阵中每一个空格赋值
        int offset = 1;   // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i, j;
        while(loop--){
            i = startx;
            j = starty;
						
						// 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for(j = starty; j < n -offset; j++){
                res[startx][j] = count++;
        }
						// 模拟填充右列从上到下(左闭右开)
            for(i = startx; i < n - offset; i++){
                res[i][j] = count++;
            }
						// 模拟填充下行从右到左(左闭右开)
            for(; j > starty; j--){
                res[i][j] = count++;
            }
						// 模拟填充左列从下到上(左闭右开)
            for(; i > startx; i--){
                res[i][j] = count++;
            }
// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
            offset += 1;    // offset 控制每一圈里每一条边遍历的长度
    }
				// 如果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

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)

这种模拟题得找到它的规律去做，我刚开始想得找每一行的规律，但这样太复杂了。还要各种判断，题目给出了顺时针赋值，但是有很多圈。要想办法找到能够重复的模板，比如如何赋值一圈。

今日收获

1、sort函数的排序方法类似于快排方法仅适用于普通数组和部分类型的容器，时间复杂度为n*log2(n)

sort(起始地址，结束地址，比较器); 其中比较器可以省略，默认升序

**对vector排序：**sort(vec.begin(),vec.end()）

其中vec.begin()返回的是一个迭代器，该迭代器指向vec的起始元素。

2、滑动窗口

3、模拟题