【基础】leetcode 977 有序数组的平方
基本思路能想出来，有个优化的点没想到：我自己的方法是每次在结果数组后面append，最后将结果数组reverse，这样时间就要double；因为已知结果数组的长度，更好的做法是先声明一个相应长度的数组，再往里面填数。
“先声明一个相应长度的数组” 这个要会写
平方运算符要会写
# python3
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
i, j = 0, n - 1
while i<=j:
i_sqr = nums[i] ** 2
j_sqr = nums[j] ** 2
if i_sqr >= j_sqr:
res[j-i] = i_sqr # (len-1)-(i+(len-1-j))=j-i
i += 1
else:
res[j-i] = j_sqr
j -= 1
# 如果nums=[], 那么len(nums)=0, res=[]
return res
// c++
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
int i = 0, j = n - 1;
while (i <= j) {
int i_sqr = nums[i] * nums[i];
int j_sqr = nums[j] * nums[j];
if (i_sqr >= j_sqr) {
res[j-i] = i_sqr;
i++;
}
else {
res[j-i] = j_sqr;
j--;
}
}
return res;
}
};
【基础】leetcode 209 长度最小的子数组
又看错题目了。。看成了和等于target的最小子数组
自己写的时候while那里没想到，用了if，每次只减去一次nums[i]，逻辑错误
todo：[https://leetcode.cn/problems/QTMn0o/](和为k的子数组) 前缀和方法也可解本题
值得再刷窗口函数：
在本题中实现滑动窗口，主要确定如下三点：
窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？
# python3
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
res, sums, i = float("inf"), 0, 0
for j in range(len(nums)):
sums += nums[j]
while sums >= target:
res = min(res, j-i+1) # 这里min，所以第一行不能初始化res=0
sums -= nums[i]
i += 1
return 0 if res == float("inf") else res
// c++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT32_MAX;
int i = 0;
int sums = 0;
for (int j = 0; j < nums.size(); j++) {
sums += nums[j];
while (sums >= target) {
res = min(res, j - i + 1);
sums -= nums[i++];
}
}
return res == INT32_MAX ? 0 : res;
}
};
【基础】leetcode 59 螺旋矩阵2⃣️
知道难点在于区间一致性之后，自己可以做出来，思路竟然跟一年前一模一样，我还是那个我啊！
题目又又看错了，从1开始看成从0开始
还有一些小细节没写对伪代码 - 看题解 - 写代码 的流程果然要快一丢丢
# python
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
upper, left = 0, 0
lower, right = n - 1, n - 1
matrix = [[0] * n for _ in range(n)] # 二维数组的初始化
cnt = 1 # 题目让从1开始，不是从0
if n % 2:
matrix[n // 2][n // 2] = n ** 2
while left < right and upper < lower:
for i in range(left, right):
matrix[upper][i] = cnt # 二维数组元素的取法是m[i][j]，不是m[i, j]
cnt += 1
for i in range(upper, lower):
matrix[i][right] = cnt
cnt += 1
for i in range(right, left, -1): # 注意[right, left)的写法
matrix[lower][i] = cnt
cnt += 1
for i in range(lower, upper, -1):
matrix[i][left] = cnt
cnt += 1
left += 1
upper += 1
right -= 1
lower -= 1
return matrix
// c++
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// 初始化结果数组
vector<vector<int>> matrix(n, vector<int>(n, 0));
int upper = 0, left = 0;
int lower = n - 1, right = n - 1;
int cnt = 1;
int mid = n / 2;
if (n % 2) {
matrix[mid][mid] = n * n;
}
while (upper < lower && left < right) {
for (int i = left; i < right; i++) {
matrix[upper][i] = cnt++;
}
for (int i = upper; i < lower; i++) {
matrix[i][right] = cnt++;
}
for (int i = right; i > left; i--) {
matrix[lower][i] = cnt++;
}
for (int i = lower; i > upper; i--) {
matrix[i][left] = cnt++;
}
upper++;
left++;
lower--;
right--;
}
return matrix;
}
};
day2 语法积累
- python 声明一个数组
res = [-1] * n
- c++ 声明一个数组
vector<int> res(n, -1);
- c++ 打印数组，需要遍历打印，下面是打印一个元素：
cout << res[0] << endl;
- python 平方运算
i ** 2
- 无穷大值
python float("inf")
c++ INT32_MA
- python 初始化一个二维数组，取数：m[i][j]
[[0] * n for _ in range(n)]
- c++ 初始化一个二维数组
vector<vector<int>> matrix(n, vector<int>(n, 0));
- python 逆序区间，right，right-1，···，left+1
range(right, left, -1)
- c++逆序区间，注意是大于而不是小于了
for (int i = right; i > left; i--)
