leetcode刷题记录
挑选了leetcode几道算法题
1. 合并两个有序数组 (88. Merge Sorted Array)
难度: 简单
标签: 数组, 双指针, 排序
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。
代码与注释
from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
思路：逆向双指针法。
因为 nums1 的后半部分是空的，为了不覆盖 nums1 前面的有效元素，
我们可以从两个数组的末尾开始比较，把较大的数放到 nums1 的最后面。
"""
# p1 指向 nums1 有效元素的末尾
p1 = m - 1
# p2 指向 nums2 的末尾
p2 = n - 1
# p 指向 nums1 的最末尾（即合并后数组的最后一个位置）
p = m + n - 1
# 当 p1 和 p2 都还没遍历完时
while p1 >= 0 and p2 >= 0:
# 比较两个指针当前的数值，谁大谁就放到 nums1[p] 的位置
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
# 填完一个位置，p 向前移动
p -= 1
# 如果 nums2 还有剩余元素（说明 nums2 中有些元素比 nums1 所有的元素都小）
# 直接把它们拷贝到 nums1 的最前面
# 注意：如果 p1 还有剩余不用管，因为它们本身就在 nums1 里且是有序的
nums1[:p2 + 1] = nums2[:p2 + 1]
2. 删除有序数组中的重复项 (26. Remove Duplicates from Sorted Array)
难度: 简单
标签: 数组, 双指针
题目描述
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
代码与注释
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""
思路：快慢指针法。
slow 指针维护“无重复数组”的边界，fast 指针用来遍历寻找新元素。
"""
if not nums:
return 0
# slow 指针指向当前已经处理好的、不重复序列的最后一个位置
slow = 0
# fast 指针从第二个元素开始遍历
for fast in range(1, len(nums)):
# 如果发现 fast 指向的元素和 slow 指向的不同
# 说明找到了一个新的不重复元素
if nums[fast] != nums[slow]:
# slow 向前移动一位
slow += 1
# 将这个新元素复制到 slow 的位置
nums[slow] = nums[fast]
# 返回长度，长度 = 索引 + 1
return slow + 1
3. 多数元素 (169. Majority Element)
难度: 简单
标签: 数组, 哈希表, 分治, 计数, 排序
题目描述
给定一个大小为 n 的数组 nums ，返回其中的 多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
代码与注释
class Solution:
def majorityElement(self, nums: List[int]) -> int:
"""
思路：Boyer-Moore 投票算法 (摩尔投票法)。
核心思想是“抵消”。如果把多数元素记为 +1，其他元素记为 -1，
因为多数元素超过一半，所有元素加起来的和一定大于 0。
"""
count = 0
candidate = None
for num in nums:
# 如果计数器为 0，说明前面的都抵消完了，重新假设当前数字为候选人
if count == 0:
candidate = num
# 如果当前数字等于候选人，票数 +1
# 否则票数 -1
if num == candidate:
count += 1
else:
count -= 1
return candidate
4. 买卖股票的最佳时机 (121. Best Time to Buy and Sell Stock)
难度: 简单
标签: 数组, 动态规划
题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
代码与注释
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""
思路：贪心 / 一次遍历。
我们只需要关心两个值：
1. 历史最低点买入价格 (min_price)
2. 当前价格卖出能得到的最大利润 (max_profit)
"""
min_price = float('inf') # 初始化为一个无穷大的数
max_profit = 0
for price in prices:
# 如果当前价格比历史最低价还低，更新最低价
if price < min_price:
min_price = price
# 否则，尝试计算如果在今天卖出（当前价格 - 历史最低价）是否能赚钱更多
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit
5. 跳跃游戏 (55. Jump Game)
难度: 中等
标签: 贪心, 数组, 动态规划
题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
代码与注释
class Solution:
def canJump(self, nums: List[int]) -> bool:
"""
思路：贪心算法。
维护一个变量 max_reach，表示当前能到达的最远位置。
遍历数组，如果当前位置 i 在 max_reach 范围内，
就尝试更新 max_reach = max(max_reach, i + nums[i])。
"""
max_reach = 0
n = len(nums)
for i in range(n):
# 如果当前位置 i 已经超过了能到达的最远距离，说明断了，无法继续
if i > max_reach:
return False
# 更新最远能到达的距离
# i + nums[i] 代表从当前格子能跳到的最远位置
max_reach = max(max_reach, i + nums[i])
# 如果最远距离已经覆盖了最后一个下标，直接返回 True
if max_reach >= n - 1:
return True
return False
6. 除自身以外数组的乘积 (238. Product of Array Except Self)
难度: 中等
标签: 数组, 前缀和
题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 要求：不要使用除法，且在 O(n) 时间复杂度内完成。
代码与注释
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
"""
思路：左右乘积列表。
answer[i] 其实等于 (i 左边所有数的乘积) * (i 右边所有数的乘积)。
我们可以先遍历一遍计算左边的乘积，再反向遍历一遍乘上右边的乘积。
"""
n = len(nums)
answer = [0] * n
# 1. 计算左侧乘积
# answer[i] 暂时存放 i 左边所有元素的乘积
answer[0] = 1
for i in range(1, n):
answer[i] = nums[i - 1] * answer[i - 1]
# 2. 计算右侧乘积并直接乘到 answer 中
# R 为右侧所有元素的乘积，初始为 1
R = 1
for i in range(n - 1, -1, -1):
# 对于索引 i，answer[i] 已经是左边的乘积了
# 现在乘上右边的乘积 R
answer[i] = answer[i] * R
# 更新 R，包含当前 nums[i]
R *= nums[i]
return answer
7. 加油站 (134. Gas Station)
难度: 中等
标签: 贪心, 数组
题目描述
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
代码与注释
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
"""
思路：贪心算法。
1. 如果总油量小于总消耗，一定无法跑完一圈。
2. 如果总油量 >= 总消耗，一定有解。
核心逻辑：如果不可能是从 A 跑到 B (中间断油了)，那么 A 到 B 之间的任何一个站点都不可能是起点。
"""
# 总剩余油量 (判断是否有解)
if sum(gas) < sum(cost):
return -1
current_gas = 0
start_station = 0
for i in range(len(gas)):
# 当前这一步的净剩油量
current_gas += gas[i] - cost[i]
# 如果累积油量小于 0，说明从 start_station 到 i 走不通
# 那么起点肯定不是 start_station 到 i 之间的任何一个
# 只能尝试 i + 1 作为新的起点
if current_gas < 0:
start_station = i + 1
current_gas = 0 # 归零，重新累计
return start_station
8. 无重复字符的最长子串 (3. Longest Substring Without Repeating Characters)
难度: 中等
标签: 哈希表, 字符串, 滑动窗口
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
代码与注释
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
思路：滑动窗口。
维护一个窗口 [left, right]，保证窗口内没有重复字符。
使用一个哈希表记录字符上一次出现的位置。
"""
# 记录字符最后出现的位置 {字符: 索引}
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
char = s[right]
# 如果字符已经在窗口里（即上次出现的位置 >= left）
if char in char_map and char_map[char] >= left:
# 移动 left 指针，直接跳到重复字符的下一位
left = char_map[char] + 1
# 更新当前字符的位置
char_map[char] = right
# 计算当前窗口长度，并更新最大值
max_len = max(max_len, right - left + 1)
return max_len
9. 三数之和 (15. 3Sum)
难度: 中等
标签: 数组, 双指针, 排序
题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
代码与注释
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""
思路：排序 + 双指针。
1. 先将数组排序，方便去重和移动指针。
2. 固定第一个数 nums[i]，然后在剩下的部分用双指针找 nums[L] + nums[R] = -nums[i]。
"""
n = len(nums)
res = []
nums.sort() # 排序是关键
for i in range(n):
# 如果当前数字大于 0，后面肯定也大于 0，和不可能为 0，直接结束
if nums[i] > 0:
break
# 去重：如果当前数字和前一个一样，跳过，避免重复结果
if i > 0 and nums[i] == nums[i-1]:
continue
# 双指针寻找另外两个数
L = i + 1
R = n - 1
while L < R:
total = nums[i] + nums[L] + nums[R]
if total == 0:
res.append([nums[i], nums[L], nums[R]])
# 找到答案后，继续寻找下一组，同时去重
while L < R and nums[L] == nums[L+1]:
L += 1
while L < R and nums[R] == nums[R-1]:
R -= 1
L += 1
R -= 1
elif total < 0:
# 和太小，左指针右移变大
L += 1
else:
# 和太大，右指针左移变小
R -= 1
return res
10. 接雨水 (42. Trapping Rain Water)
难度: 困难
标签: 栈, 数组, 双指针, 动态规划
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
代码与注释
class Solution:
def trap(self, height: List[int]) -> int:
"""
思路：双指针法。
核心原理：一个位置能接多少水，取决于它左右两边最高柱子中较矮的那一个 (木桶效应)。
min(max_left, max_right) - height[i]
"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
ans = 0
while left < right:
# 如果左边的柱子比右边矮，说明瓶颈在左边
# 此时我们只需要关注 left_max 即可，因为右边一定有比 left_max 更高的挡着（或者就是 right 本身）
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left] # 更新左边最高
else:
ans += left_max - height[left] # 计算水量
left += 1
else:
# 同理，如果右边比左边矮，瓶颈在右边
if height[right] >= right_max:
right_max = height[right] # 更新右边最高
else:
ans += right_max - height[right] # 计算水量
right -= 1
return ans