代码随想录算法训练营第二天| 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ，总结

977.有序数组的平方

题目链接：977.有序数组的平方
文档讲解：977.有序数组的平方
视频讲解：977.有序数组的平方
状态：暴力法能够解决，双指针法自己也想到了，思路和卡哥基本一致，学习一下卡哥的代码书写😸

学习前的想法

给出的题目建议是理解双指针的思想，因此我下面将会先考虑暴力方法解决，之后独立思考一下双指针法如何实现。

顾名思义，我们需要对一个增序排列数组中的每个元素求平方，得到一个每个数字平方所组成的增序排列数组。

首先考虑暴力法求解，即求出每个元素的平方，将其重新排序，在这里我使用冒泡排序对新数组重新排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int k = 0; k < nums.size(); k++) {
            nums[k] = nums[k] * nums[k];
        }
        
        for(int i = 0; i < nums.size(); i++) {
            for(int j = 0; j < nums.size() - i - 1; j++) {
                if(nums[j] > nums[j+1]) {
                    int tmp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = tmp;
                }
            }
        }

        return nums;
    }
};

2024/2/22
代码成功ac，但是时间复杂度为O(n^2)，执行时间达到了1000+ms，效率太低，考虑可以采用快速排序法，优化时间效率。

下面考虑卡哥建议的双指针法，为了避免时间浪费，我在这里仅仅使用文字记录我的思路：

根据第一天的学习，目前我了解到的双指针包括 快慢指针 和 左右指针，考虑到数组增序排列，我的想法是使用左右指针，这样的话会有下面几种情况：

假定左指针为left指向起始位置，右指针为right指向终止位置。

若数组元素全部非负，即left >= 0，则只需将原数组元素求平方即可；

若数组元素包含负值，即left < 0，则分别左右遍历，取绝对值最大的数放置在新数组的末位。

综上，只需左右分别遍历，比较大小，将绝对值最大的数求平方存储。

2024/2/22
以上是我独立的一些想法，不知道对不对。😂

学习后的想法

数组特性：平方之后，最大元素在数组两侧，因此可以用 左右指针 ，逐步向中间合拢。

2022/2/22
和我想得差不多😼

假设左指针为left，右指针为right，值得注意的地方有下面几处：

有关循环条件的结束：left <= right，为什么需要采用这种形式，而不是left < right？
这是因为后者会导致left==right时指向的元素不能被正确加入到新数组中。

有关left和right的取值：如果left指向的元素大，则left++，right不变；如果right指向的元素大，则right--，left不变。注意，以上元素比较的是平方的大小。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义一个新的数组
vector<int> result;
int k = nums.size() - 1;

for(int left = 0, right = nums.size() - 1; left <= right;) {
	if(nums[left] * nums[left] > nums[right] * nums[right]) {
		result[k--] = nums[left] * nums[left];
		left++;
	} else {
		result[k--] = nums[right] * nums[right];
		right--;
	}
}

return result;

卡哥：这里还是说一下，大家不必太在意leetcode上执行用时，打败多少多少用户，这个就是一个玩具，非常不准确。

209.长度最小的子数组

题目链接：209.长度最小的子数组
文档讲解：209.长度最小的子数组
视频讲解：拿下滑动窗口！ | LeetCode 209 长度最小的子数组
题目建议：理解滑动窗口
状态：暴力法和滑动窗口发都没有想到，好菜🥲

学习前的想法

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

找出该数组中满足其总和大于等于target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

卡哥给出的建议是采用滑动窗口。

题外话 2024/2/22
滑动窗口这个名词在计算机领域经常出现，本人第一次了解是在学习计算机网络时，好像是在传送报文的时候使用的。最近是在学习LSTM（长短时记忆）算法中也有滑动窗口。

我的想法是，先取一个和数组等大的滑动窗口，求和，与target作比较，之后不断减小滑动窗口的大小，以获得最小的子序列。

但是感觉这样做似乎有点复杂，代码我也没有尝试去实现。

暴力法，因为刚开始就按卡哥引导的去思考了，所以没有去想，在下面会给出暴力法的实现。

学习后的想法

暴力法（两层for循环）：一层for循环用于改变起始位置，一层for循环用于改变终止位置，这样可以将所有可能的集合遍历完全。需要使用一个变量来存储符合条件集合的长度，并不断更新。

滑动窗口法：我认为滑动窗口的本质还是双指针，卡哥在视频中也提到了。

我们的滑动窗口，实际上是一个慢指针i，和一个快指针j，之间的距离。其中j也用来表示终止位置，i则表示起始位置。

使用一个for循环，不断的将j向后遍历，当其与i之间的集合所包含的元素之和sum大于或等于target，记录这时的集合长度length。

为什么for循环中遍历的是终止位置？
因为如果遍历的是起始位置，将无法遍历剩下的终止位置，而陷入暴力解法

此时，我们需要使用一个while循环来实现将i向后移动，不断减小sum的值，并更新length，直到sum的值小于target，跳出循环。

最终我们可以得到最小的子序列长度。

需要注意的是：

窗口内的值大于或等于target，移动起始位置；小于target，移动终止位置。

实现

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sum = 0; // 存储所取集合的值
int result = INT32_MAX; // 最终结果
int length = 0; // 子序列长度

for(int i = 0; i < nums.size(); i++) {
	sum = 0;
	for(int j = i; j < nums.size(); j++) {
		sum += nums[j];
		if(sum >= target) {
			length = j - i + 1;
			result = result < length ? result : length;
			break;
		} 
	}
}

// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;

滑动窗口（双指针法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i = 0; // 起始指针
int length = 0; // 滑动窗口的长度
int sum = 0; // 滑动窗口数值之和
int result = INT32_MAX;

for(int j = 0; j < nums.size(); j++) {
	sum += nums[j];
	while(sum >= target) {
		length = j - i + 1;
		result = result < length ? result : length;
		sum -= nums[i--];
	}
}

return result == INT32_MAX ? 0 : result;

59.螺旋矩阵II

题目链接：59.螺旋矩阵II
文档讲解：59.螺旋矩阵II
视频讲解：59.螺旋矩阵II
状态：本人最讨厌的矩阵相关题目😢完全没有头绪

学习前的想法

一看见矩阵就头大。

学习后的想法

面试中经常出现的题目，不涉及算法，实际上是一道模拟题目。

重点是边界处理问题！！！

循环不变量：不变量实际上就是我们做边界处理的规则，左闭右开 或是 左闭右闭。

多余的话不多说，根据n的值确定需要遍历多少圈，然后通过while循环一圈圈遍历，选择左闭右开的边界。

其中n的奇偶性需要进行一个讨论。

实现

2024/2/22
直接复制的卡哥的代码，是在是干不动了🤪，复习的时候再自己搞一下。

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
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 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

收获与学习时长

学习时长：2h 59min

收获

前两题可以说是强化了对双指针的使用，最后一题应该说是开拓了一下思维，强化了循环不变量的理解。

总结

2024/2/22
时间有点晚了，睡觉要紧，下次一定。