LeetCode刷题记录（数组篇）
LeetCode刷题记录（数组篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。
[704] Binary Search
难度：Easy
语言：C++
题目描述。
确定好并保持区间一致性即可，例如是闭区间还是开区间，不变量贯彻到底即可。
int search(vector<int>& nums, int target) {
int size = nums.size();
int lower = 0;
int upper = size - 1;
int index = 0;
while (true) {
if (upper < lower) {
return -1;
}
index = (lower + upper) / 2;
int now = nums[index];
if (now == target) {
return index;
}
if (target < now) {
upper = index - 1;
} else {
lower = index + 1;
}
}
}
[27] Remove Element
难度：Easy
语言：Python
题目描述。
利用元素顺序可以改变的特性，左右指针往中间靠拢即可。
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
head_index = 0
tail_index = len(nums) - 1
while tail_index >= 0 and nums[tail_index] == val:
tail_index -= 1
while head_index < tail_index:
if nums[head_index] == val:
nums[head_index] = nums[tail_index]
tail_index -= 1
head_index += 1
while head_index <= tail_index and nums[tail_index] == val:
tail_index -= 1
return tail_index + 1
[977] Squares of a Sorted Array
难度：Easy
语言：Rust
题目描述。
原数组是有序的，因此平方后最大值一定在两端。利用双指针往中间靠拢即可。
pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
let (mut left, mut right) = (0, nums.len() - 1);
let mut cur_index = right;
let mut res: Vec<i32> = vec![0; right + 1];
while left <= right {
let (left_squares, right_squares) =
(nums[left] * nums[left], nums[right] * nums[right]);
if left_squares < right_squares {
right -= 1;
res[cur_index] = right_squares;
} else {
left += 1;
res[cur_index] = left_squares
};
cur_index -= 1;
}
res
}
[209] Minimum Size Subarray Sum
难度：Medium
语言：C++
题目描述。
使用滑动窗口（其实也相当于快慢指针）即可。每次sum >= target了就开始注意更新left指针，最后返回min_len即可。复杂度O(n)。说是Medium但是是做起来最快的一道。
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0;
int left = 0;
int right = 0;
int n = nums.size();
int min_len = n + 1;
while (right < n) {
sum += nums[right];
if (sum >= target) {
while (sum - nums[left] >=
target) { // if target can be zero, the condition should be
// (left <= right && sum - nums[left] >= target
sum -= nums[left];
left++;
}
if (right - left + 1 < min_len) {
min_len = right - left + 1;
}
}
right++;
}
return min_len > n ? 0 : min_len;
}
[59] Spiral Matrix II
难度：Medium
语言：Python
题目描述。
没什么算法可言，就是锻炼代码能力，难点在于边界条件的判断。
一般来说坚持循环不变量即可，例如每次循环坚持左闭右开。但是有特殊情况，那就是n如果是奇数就会有一个中心点，如果都坚持左闭右开的话就会导致中心点永远填不到。网上一些解法是特殊处理，单独最后填中心点的值。
本人的解法则是牺牲了一定的循环不变量，即每个round第一个循环（矩阵上方从左到右）采用了左闭右闭，第二、三个循环采用左开右闭，第四个循环（矩阵左边从下到上）采用左开右开（右开与第一个循环的左闭相对应），避免了中心点的单独处理（第一个循环是左闭右闭，所以能够处理中心点）。这种解法与前面那种各有利弊，见仁见智。
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
ret = [[0] * n for _ in range(n)]
round_index = 0
cur_num = 1
while cur_num <= n * n:
for i in range(0 + round_index, n - round_index):
ret[0 + round_index][i] = cur_num
cur_num += 1
for i in range(0 + round_index + 1, n - round_index):
ret[i][n - round_index - 1] = cur_num
cur_num += 1
for i in range(n - round_index - 2, 0 + round_index - 1, -1):
ret[n - round_index - 1][i] = cur_num
cur_num += 1
for i in range(n - round_index - 2, 0 + round_index, -1):
ret[i][0 + round_index] = cur_num
cur_num += 1
round_index += 1
return ret
个人总结
数组作为最基础的数据结构之一，内容也很简单。就做的几道经典题而言，要掌握的就是两个内容：