本日刷题继续练习数组相关的题目。进一步熟悉双指针的使用方法。
977 有序数组的平方 Squares of a Sorted Array
题目：
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4-
numsis sorted in non-decreasing order.
要点
- 可以直接顺着题目的叙述，先遍历数组，再排序（处理负数平方后大的问题）。遍历的复杂度是 O(N)，快速排序
sort(nums.begin(), nums.end())的复杂度是 O(NlogN)。重点注意记住 C++ Python 语言的默认排序函数用法。 - 题目在最后让我们思考 O(N) 的解法，可以使用双指针（相向处理，因为平方最大的肯定在两端，遍历一次即可把平方后的值按非递减顺序排好。
代码
暴力遍历再排序
时间复杂度 O(NlogN) (N + NlogN)
C++
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// O(NlogN)
int size = nums.size();
vector<int> nums_sqrs(size);
for (int i = 0; i < size; i++) {
nums_sqrs[i] = nums[i] * nums[i];
}
// sort
sort(nums_sqrs.begin(), nums_sqrs.end());
return nums_sqrs;
}
};
Python 注意 list.sort() 方法是原位操作。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
nums_sqrs = []
for i in range(len(nums)):
nums_sqrs.append(nums[i] ** 2)
nums_sqrs.sort()
return nums_sqrs
双指针
时间复杂度 O(N)
C++
两次写了两版代码，略有区别，第一次是把 k 用 for 遍历了，内层嵌套 while (i<=j)。由于其实
k 遍历完整与 while (i<=j) 是同一时刻，所以应该没什么太大问题。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = 0;
int j = nums.size() - 1;
vector<int> sorted_sqrs(nums.size());
for (int k = nums.size() - 1; k >= 0; k--) {
while (i <= j) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
sorted_sqrs[k--] = nums[i] * nums[i++];
} else {
sorted_sqrs[k--] = nums[j] * nums[j--];
}
}
}
return sorted_sqrs;
}
};
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
vector<int> nums_sqrs(nums.size());
int idx = nums.size() - 1;
while (left <= right) {
if (nums[left] * nums[left] < nums[right] * nums[right]) {
nums_sqrs[idx--] = nums[right] * nums[right--];
} else {
nums_sqrs[idx--] = nums[left] * nums[left++];
}
}
return nums_sqrs;
}
};
Python
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left = 0
right = len(nums) - 1
sorted_sqrs = [0 for _ in range(len(nums))]
idx = len(nums) - 1
while left <= right:
if nums[left] ** 2 < nums[right] ** 2:
sorted_sqrs[idx] = nums[right] ** 2
right -= 1
idx -=1
else:
sorted_sqrs[idx] = nums[left] ** 2
left += 1
idx -= 1
return sorted_sqrs
209 长度最小的子数组 Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).
要点
- 双指针实现比较直观。右侧指针每往右侧移动一步，当前的和
curr_sum加上右侧移动后位置的值。每次挪动左指针都要判断curr_sum是否大于等于（greater or equal to）target，所以用while (curr_sum >= target)而非if（只判断一次后左指针动一次）。 - 此题主要记忆求最小值的时候，初始化可以初始化成最大的整型：C++
INT_MAX，Python 里可以写成import math后math.inf或者float("inf")
代码
双指针
时间复杂度 O(N)
C++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i = 0;
int min_length = INT32_MAX;
int curr_sum = 0;
for (int j = 0; j < nums.size(); j++) {
curr_sum += nums[j];
while (curr_sum >= target) {
min_length = min(min_length, (j - i + 1));
curr_sum -= nums[i++];
}
}
if (min_length == INT32_MAX) {
return 0; // no such subarray
}
return min_length;
}
};
Python
import math
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
i = 0
min_length = math.inf
curr_sum = 0
for j in range(len(nums)):
curr_sum += nums[j]
while curr_sum >= target:
min_length = min(min_length, (j - i + 1))
curr_sum -= nums[i]
i += 1
if min_length == math.inf:
return 0
return min_length
59 螺旋矩阵II Spiral Matrix II
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
1 <= n <= 20
要点
- 关注循环不变量，思路上轻松的方法就是保证左开右闭。按照代码随想录的题解思路，遍历上、右、下、左的时候，都左开右闭。转一圈后距离边界的
offset + 1，总offset数为n // 2。当n为奇数的时候，还需要补充中间的值。这个写法其实从流程上总体有点麻烦的。 - 把过程写得更简略一些，则是每次都把这一行一列遍历完，立刻挪动遍历完的这一行或者列的边界值。也不需要补充中间值了。
- 注意记忆初始化矩阵的方式:
a. C++vector<int> vec(n); vector<vector<int>> mat(n, vec);
b. Python[[0 for _ in range(n)] for _ in range(n)] - 注意行和列的索引！先索引的是行，然后是列。
代码
模拟每次挪动的写法
C++
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<int> vec(n);
vector<vector<int>> mat(n, vec);
int t = 0, l = 0, b = n - 1, r = n - 1;
int k = 1;
while (k <= n * n) {
// left to right, top++
for (int i = l; i <= r; i++) {
mat[t][i] = k++;
}
t++;
// top to bottom, right--
for (int i = t; i <= b; i++) {
mat[i][r] = k++;
}
r--;
// right to left, bottom--
for (int i = r; i >= l; i--) {
mat[b][i] = k++;
}
b--;
// bottom to top, left++
for (int i = b; i >= t; i--) {
mat[i][l] = k++;
}
l++;
}
return mat;
}
};
Python
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
mat = [[0 for _ in range(n)] for _ in range(n)]
l, t, b, r = 0, 0, n - 1, n - 1
k = 1
while k <= n * n:
# left to right, top++
for i in range(l, r + 1):
mat[t][i] = k
k += 1
t += 1
# top to bottom, right--
for i in range(t, b + 1):
mat[i][r] = k
k += 1
r -= 1
# right to left, bottom--
for i in range(r, l - 1, -1):
mat[b][i] = k
k += 1
b -= 1
# bottom to top, left++
for i in range(b, t - 1, -1):
mat[i][l] = k
k += 1
l += 1
return mat
数组总结
- 数组的内存空间地址连续，所以删除或者增添元素的时候就需要移动其它元素的地址。
- 数组的元素不能删除，只能覆盖
数组常见题目类型
- 二分法 注意循环不变量的问题。多写多练习，很容易错
- 双指针法 一个快指针和一个慢指针，在一层循环里完成两层循环的工作
- 滑动窗口 根据当前子序列大小和状况，不断调节子序列起始位置，将 O(n^2) 降低为 O(n)
- 模拟行为 注意循环不变量，辅以画图、写好注释以防搞乱。
