本日刷題繼續(xù)練習(xí)數(shù)組相關(guān)的題目。進(jìn)一步熟悉雙指針的使用方法。
977 有序數(shù)組的平方 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.
要點(diǎn)
- 可以直接順著題目的敘述，先遍歷數(shù)組，再排序（處理負(fù)數(shù)平方后大的問題）。遍歷的復(fù)雜度是 O(N)，快速排序
sort(nums.begin(), nums.end())的復(fù)雜度是 O(NlogN)。重點(diǎn)注意記住 C++ Python 語言的默認(rèn)排序函數(shù)用法。 - 題目在最后讓我們思考 O(N) 的解法，可以使用雙指針（相向處理，因?yàn)槠椒阶畲蟮目隙ㄔ趦啥?，遍歷一次即可把平方后的值按非遞減順序排好。
代碼
暴力遍歷再排序
時(shí)間復(fù)雜度 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
雙指針
時(shí)間復(fù)雜度 O(N)
C++
兩次寫了兩版代碼，略有區(qū)別，第一次是把 k 用 for 遍歷了，內(nèi)層嵌套 while (i<=j)。由于其實(shí)
k 遍歷完整與 while (i<=j) 是同一時(shí)刻，所以應(yīng)該沒什么太大問題。
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 長度最小的子數(shù)組 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)).
要點(diǎn)
- 雙指針實(shí)現(xiàn)比較直觀。右側(cè)指針每往右側(cè)移動一步，當(dāng)前的和
curr_sum加上右側(cè)移動后位置的值。每次挪動左指針都要判斷curr_sum是否大于等于（greater or equal to）target，所以用while (curr_sum >= target)而非if（只判斷一次后左指針動一次）。 - 此題主要記憶求最小值的時(shí)候，初始化可以初始化成最大的整型：C++
INT_MAX，Python 里可以寫成import math后math.inf或者float("inf")
代碼
雙指針
時(shí)間復(fù)雜度 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
要點(diǎn)
- 關(guān)注循環(huán)不變量，思路上輕松的方法就是保證左開右閉。按照代碼隨想錄的題解思路，遍歷上、右、下、左的時(shí)候，都左開右閉。轉(zhuǎn)一圈后距離邊界的
offset + 1，總offset數(shù)為n // 2。當(dāng)n為奇數(shù)的時(shí)候，還需要補(bǔ)充中間的值。這個(gè)寫法其實(shí)從流程上總體有點(diǎn)麻煩的。 - 把過程寫得更簡略一些，則是每次都把這一行一列遍歷完，立刻挪動遍歷完的這一行或者列的邊界值。也不需要補(bǔ)充中間值了。
- 注意記憶初始化矩陣的方式:
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
數(shù)組總結(jié)
- 數(shù)組的內(nèi)存空間地址連續(xù)，所以刪除或者增添元素的時(shí)候就需要移動其它元素的地址。
- 數(shù)組的元素不能刪除，只能覆蓋
數(shù)組常見題目類型
- 二分法 注意循環(huán)不變量的問題。多寫多練習(xí)，很容易錯(cuò)
- 雙指針法 一個(gè)快指針和一個(gè)慢指針，在一層循環(huán)里完成兩層循環(huán)的工作
- 滑動窗口 根據(jù)當(dāng)前子序列大小和狀況，不斷調(diào)節(jié)子序列起始位置，將 O(n^2) 降低為 O(n)
- 模擬行為 注意循環(huán)不變量，輔以畫圖、寫好注釋以防搞亂。
