977. 有序数组的平方
题目链接：click here
文章讲解：click here
题目描述：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思路：
这道题是原本有序的数组经过平方操作后变无序，需要以O(N)的复杂度实现输出依旧有序。朴素的想法就是先挨个平方，再调用排序接口输出。但这显然不满足复杂度要求。
O(N)意味着只能遍历一遍，结合原本有序的数组经过平方操作后，结果是两头大，中间小的特征，采取双指针法从两边往中间遍历，并实时对比大小，大的一方结果压入结果向量，指针移动，如此循环直到双指针碰撞，此时对应的数仍未被放入结果向量，所以不退出循环，继续执行。
代码：
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
26class Solution
{
public:
vector<int> sortedSquares(vector<int> &nums)
{
vector<int> res_vec;
int left = 0;
int right = nums.size() - 1;
int k = right;
res_vec.resize(k + 1);
while (left <= right)
{
if (nums[left] + nums[right] <= 0)
{
res_vec[k--] = nums[left] * nums[left];
left++;
}
else
{
res_vec[k--] = nums[right] * nums[right];
right--;
}
}
return res_vec;
}
};细节：
我的实现采用 nums[left] + nums[right] <= 0 判别式，减少冗余的乘方计算，确保每个乘方只计算一次。
直白的说，nums[left] + nums[right] <= 0时，必然优先压入 nums[left] 的平方，因为它负数且比正数 nums[right] 的绝对值大（跳过对0的特殊讨论）。
而，nums[left] + nums[right] >= 0时，存在两种情况：
一是 nums[left] 小于0，此时无疑问优先压入 nums[right] 的平方；
二是 nums[left] 大于0，由于原数组有序性，显然 nums[right] > nums[left]，优先压入 nums[right] 平方；
这两种情况就可以兼并成一种了。从教程里学到先 resize vector，配合一个下标 k 记录位置来从后往前插入数据到 vector 里，我一开始的版本是先写到一个 deque 里再转存到 vector 输出，浪费存储空间。
209. 长度最小的子数组
题目链接：click here
文章讲解：click here
题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums l, nums l+1, …, nums r-1, nums r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路：
直觉思路是，暴力双循环遍历，第二层循环开始从第一层循环位置处累计sum，sum满足大于等于target的条件后记录一次区间长度，并尝试更新最短区间长度。
讲解提示了使用滑动窗口，下面描述自己的想法：
滑动窗口需要设计左右边界的移动规则：
右边界：当滑窗内部数之和小于 target 时（或者其他规则，此时意味着暂未满足规则），继续向右探索，更新滑窗内数之和（或者其他规则）。
左边界：当滑窗内部数之和大于等于 target 时（或者其他规则，此时意味着已经满足规则），记录一次区间长度，并尝试更新最短区间长度，并尝试更短的区间是否依旧满足规则，所以左边界向右移动，更新滑窗内数之和（或者其他规则）。对于结果输出，滑窗已经囊括整个数组且尚未满足要求，输出0，期间能满足要求，则输出最短区间长度。
遂记初始结果为数组长度加1，最终若仍然是这个结果，则输出0，反之正常输出所记结果。
代码：
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
43class Solution
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
int res = 0;
int min_res = nums.size() + 1;
int left = 0, right = 0;
int size = nums.size();
int now_sum = nums[0];
while (right < size)
{
if (now_sum < target)
{
if (right < size - 1)
{
now_sum += nums[++right];
}
else
{
break;
}
}
else
{
res = right - left + 1;
if (res == 1)
{
return 1;
}
if (res < min_res)
{
min_res = res;
}
now_sum -= nums[left++];
}
}
return min_res > size ? 0 : min_res;
}
};细节：
讲解的示例代码中使用 for 循环遍历数组，且每轮for循环都会右移滑窗右边界并更新sum，这是另一套思路：
右边界从数组最左开始向右移动，扩大滑窗以求满足滑窗内sum大于等于target的条件。
每当条件满足时，记录滑窗长度并通过不断右移左边界来缩小滑窗，直到不再满足条件。
这里对右边界的扩张似乎是无感情的，因为扩张的目的是隐含在下文中where的退出条件里（当前窗口内数据尚未满足条件，需要扩张），而非显式表达出来。两种思路相比，私以为我的想法和代码实现更加直观地回答了讲解中的三个问题：
- 窗口内是什么？
尝试满足条件的数据。 - 如何移动窗口的结束位置？
当前窗口内数据尚未满足条件，需要扩张。 - 如何移动窗口的起始位置？
当前窗口内数据已经满足条件，为追求窗口长度最短，尝试右移起始位置，缩减窗口长度。
- 窗口内是什么？
讲解示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int minSubArrayLen(int s, 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 >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
59. 螺旋矩阵II
题目链接：click here
文章讲解：click here
题目描述：给你一个正整数 ，生成一个包含 到 所有元素，且元素按顺时针顺序螺旋排列的 x 正方形矩阵 matrix 。
思路：
- 比较朴素的一道题，需要细致的把控绕圈的逻辑。
我的思路是：
将变量 k 从 到 遍历，每次向当前index内填写数据 k；
设计4种前进方向：上、下、左、右，分别对应不同的index递增规则；
再分别给4种前进方向分别设置虚拟墙，即提示中所言“区间边界”，当撞墙时，需要扭头到下一种前进方向。
完成遍历后即生成螺旋矩阵完毕，时间开销O().
- 比较朴素的一道题，需要细致的把控绕圈的逻辑。
代码：
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90class Solution
{
public:
vector<vector<int>> generateMatrix(int n)
{
// 初始化结果
vector<vector<int>> res(n, vector<int>(n,0));
// 定义四种前进方向及其墙
std::vector<std::pair<std::pair<int, int>, int>> head_set;
// 分别表示 <<前进方向>,wall>
head_set.push_back({{0, 1}, n - 1});
head_set.push_back({{1, 0}, n - 1});
head_set.push_back({{0, -1}, 0});
head_set.push_back({{-1, 0}, 1});
int head_index = 0;
// 填写数据的下标
int index_i = 0;
int index_j = 0;
for (int k = 1; k < n * n + 1; k++)
{
res[index_i][index_j] = k;
// 检查是否撞墙
auto &wall = head_set[head_index].second;
switch (head_index)
{
case 0:
if (index_j >= wall)
{
// 撞了，则需要扭头 + 缩进墙
head_index++;
wall--;
}
break;
case 1:
if (index_i >= wall)
{
head_index++;
wall--;
}
break;
case 2:
if (index_j <= wall)
{
head_index++;
wall++;
}
break;
case 3:
if (index_i <= wall)
{
head_index = 0;
wall++;
}
break;
default:
break;
}
// 根据最新前进方向，修改下标
auto &head_now = head_set[head_index];
auto &head_ = head_now.first;
index_i += head_.first;
index_j += head_.second;
}
// for (int i = 0; i < n; i++)
// {
// for (int j = 0; j < n; j++)
// {
// std::cout << res[i][j] << " ";
// }
// std::cout << std::endl;
// }
return res;
}
};
int main()
{
Solution sol;
sol.generateMatrix(10);
}细节：
四种前进方向是循环执行的。
每次填写数据后，检查是否撞墙时，根据当前所处的前进方向，可以知道该用哪个下标去和哪堵墙进行比较。
撞墙后扭头，待再次执行到该前进方向时，墙实际已经向内缩进一格，因此扭头时需要同步修改墙。我的方法与讲解中的方法的对比：
讲解中的方法左闭右开的区间设计以及着色可视化能让人直观地理解矩阵的填充过程，但是这种思路所实现出的代码确实有较多边界条件需要着重考虑。
也就是trick太多：loop和mid 的 int型 的 除二 向下取整特性；人为的设计每次loop画一整圈，随后画更小的圈；奇数时还需要在循环外部额外给矩阵中心赋值，等等。我的方法设计4种前进方向、维护各个前进方向各自的墙，并设计在检测到与墙碰撞时自然扭头到下一个前进方向，并自然地缩进这堵墙，
相比之下，我的方法的代码实现是对思路的直译，更加容易理解，也没用过多的边界条件需要考虑。
今日收获
个人博客更新，昨天新增点击130次，占据总浏览量18%，希望我的刷题记录和一些科研工作对大家有帮助。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
有序数组平方：结合数据有序 + 平方后数据两头大中间小的特性，设计左右双指针向中间遍历的方法，生成顺序的平方结果。所使用的判别trick能减少平方的计算。
长度最小子数组：在一堆数据中找满足某种条件的最短连续子串，适合使用滑窗法，关键是定义好滑窗内容的意义、滑窗前后边界的移动目的。
螺旋矩阵2：关于区间（墙）的定义和绕圈的前进方向与撞墙时扭头逻辑，以及墙的缩进需要细致把控。耗时：3h