1 介绍
本博客用来记录代码随想录leetcode200题中数组部分的题目。
2 训练
题目1：704二分查找
C++代码如下，
class Solution {
public:
int search(vector<int>& nums, int target) {
int res = -1;
int l = 0, r = nums.size() - 1;
//找到>=target的下标
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] >= target) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (res == -1) return res;
else return nums[res] == target ? res : -1;
}
};
python3代码如下，
class Solution:
def search(self, nums: List[int], target: int) -> int:
res = -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] >= target:
res = mid
r = mid - 1
else:
l = mid + 1
if res == -1:
return res
else:
return res if nums[res] == target else -1
题目2：27移除元素
C++代码如下，
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
for (int j = 0; j < nums.size(); ++j) {
if (nums[j] != val) nums[i++] = nums[j];
}
return i;
}
};
python3代码如下，
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
题目3：977有序数组的平方
C++代码如下，
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
//从最大数开始排
int n = nums.size();
int i = 0, j = n - 1;
vector<int> res(n);
int k = n - 1;
while (i <= j) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
res[k] = nums[i] * nums[i];
i++;
k--;
} else {
res[k] = nums[j] * nums[j];
j--;
k--;
}
}
return res;
}
};
python3代码如下，
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
i, j = 0, n - 1
k = n - 1
res = [0] * n
while i <= j:
if nums[i] * nums[i] > nums[j] * nums[j]:
res[k] = nums[i] * nums[i]
i += 1
k -= 1
else:
res[k] = nums[j] * nums[j]
j -= 1
k -= 1
return res
题目4：209长度最小的子数组
C++代码如下，
//往大了讲，与子数组的最大和类似
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//滑动窗口法
int res = INT_MAX;
int s = 0;
for (int r = 0, l = 0; r < nums.size(); ++r) {
s += nums[r];
while (s >= target) {
res = min(res, r - l + 1);
s -= nums[l++];
}
}
return res == INT_MAX ? 0 : res;
}
};
python3代码如下，
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
s = 0
l, r = 0, 0
n = len(nums)
res = 1e10
while r < n:
s += nums[r]
while s >= target:
res = min(res, r - l + 1)
s -= nums[l]
l += 1
r += 1
return res if res != 1e10 else 0
题目5：59螺旋矩阵 II
C++代码如下，
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int val = 1;
for (int k = 0; k <= n / 2; k += 1) {
//起点(0 + k, 0 + k)
int x0 = k, y0 = k;
int length = n - 2 * k;
//向右
for (int step = 0; step < length - 1; ++step) {
int x = x0;
int y = y0 + step;
res[x][y] = val++;
}
//向下
x0 = x0;
y0 = y0 + length - 1;
for (int step = 0; step < length - 1; ++step) {
int x = x0 + step;
int y = y0;
res[x][y] = val++;
}
//向左<--
x0 = x0 + length - 1;
y0 = y0;
for (int step = 0; step < length - 1; ++step) {
int x = x0;
int y = y0 - step;
res[x][y] = val++;
}
//向上
x0 = x0;
y0 = y0 - length + 1;
for (int step = 0; step < length - 1; ++step) {
int x = x0 - step;
int y = y0;
res[x][y] = val++;
}
//最后一步
if (length == 1) {
res[x0][y0] = val;
}
}
return res;
}
};
python3代码如下，
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0] * n for _ in range(n)]
val = 1
for k in range(n // 2 + 1):
x0, y0 = k, k
length = n - 2 * k
#向右走-->
for step in range(length-1):
x, y = x0, y0 + step
res[x][y] = val
val += 1
x0, y0 = x0, y0 + length - 1
#向下走
for step in range(length-1):
x, y = x0 + step, y0
res[x][y] = val
val += 1
x0, y0 = x0 + length - 1, y0
#向左走<--
for step in range(length-1):
x, y = x0, y0 - step
res[x][y] = val
val += 1
x0, y0 = x0, y0 - length + 1
#向上走
for step in range(length-1):
x, y = x0 - step, y0
res[x][y] = val
val += 1
if length == 1:
res[x0][y0] = val
val += 1
return res
