基础语法
Python 基础语法速览
变量与类型
# Python 是动态类型语言，不需要声明类型
a = 10 # 整数 (int)
b = 3.14 # 浮点数 (float)
c = "hello" # 字符串 (str)
d = True # 布尔值 (bool)
e = None # 空值 (NoneType)
# 类型转换
int("123") # → 123
str(456) # → "456"
float("3.14") # → 3.14
bool(0) # → False
条件判断
if x > 0:
print("正数")
elif x < 0:
print("负数")
else:
print("零")
循环
# for 循环（最常用）
for i in range(5): # 0, 1, 2, 3, 4
print(i)
for i in range(1, 5): # 1, 2, 3, 4 （左闭右开）
print(i)
for i in range(0, 10, 2): # 0, 2, 4, 6, 8 （步长为2）
print(i)
# while 循环
while n > 0:
n -= 1
# break: 跳出整个循环
# continue: 跳过本次迭代，继续下一次
函数
def add(a, b):
return a + b
# 带默认参数
def greet(name, msg="Hello"):
return f"{msg}, {name}!"
# Lambda 函数（匿名函数）
square = lambda x: x * x
add_two = lambda a, b: a + b
f-string（格式化字符串）
name = "Alice"
age = 25
print(f"{name} is {age} years old") # Alice is 25 years old
列表 (List) 全解
创建与初始化
# 直接创建
nums = [1, 2, 3, 4, 5]
# 创建空列表
empty = []
empty = list()
# 创建矩阵
zeros = [0] * 10 # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
squares = [x ** 2 for x in range(10)] # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
evens = [x for x in range(20) if x % 2 == 0] # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
matrix = [[0] * 3 for _ in range(3)] # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
索引与切片
nums = [10, 20, 30, 40, 50]
# 索引（从0开始）
nums[0] # 10 (第一个)
nums[-1] # 50 (最后一个)
nums[-2] # 40 (倒数第二个)
# 切片 [start:end:step] — 左闭右开
nums[0:3] # [10, 20, 30] 索引 0,1,2
nums[:3] # [10, 20, 30] 前4个 不包含第4
nums[2:] # [30, 40, 50] 第3个及后面
nums[::2] # [10, 30, 50] 步长为2
nums[::-1] # [50, 40, 30, 20, 10] 反转列表
num = [1, 2, 3, 4, 5]
i = 2
left = num[:i] # [1, 2] （切下来的左边）
right = num[i:] # [3, 4, 5]（切下来的右边）
print(left + right) # [1, 2, 3, 4, 5]（拼回去还是原来的）
增删改查
nums = [1, 2, 3]
# —— 增加 ——
nums.append(4) # 末尾追加 → [1, 2, 3, 4]
nums.insert(1, 99) # 在索引1插入99 → [1, 99, 2, 3, 4]
nums.extend([5, 6]) # 拼接另一个列表 → [1, 99, 2, 3, 4, 5, 6]
# —— 删除 ——
nums.pop() # 弹出最后一个元素，返回被删除的值 → 6
nums.pop(1) # 弹出索引1的元素
nums.remove(99) # 删除第一个值为99的元素
del nums[0] # 删除索引0的元素
# —— 修改 ——
nums[0] = 100 # 直接赋值
# —— 查找 ——
3 in nums # True / False — 判断是否存在
nums.index(3) # 返回第一个值为3的索引，不存在会报错
nums.count(3) # 统计3出现的次数
len(nums) # 列表长度
排序
nums = [3, 1, 4, 1, 5, 9]
# 原地排序（修改原列表）
nums.sort() # 升序 → [1, 1, 3, 4, 5, 9]
nums.sort(reverse=True) # 降序 → [9, 5, 4, 3, 1, 1]
nums.sort(key=abs, reverse=True) # 自定义排序（按绝对值降序）
# 返回新列表（不修改原列表）
sorted_nums = sorted(nums) # 升序
sorted_nums = sorted(nums, reverse=True) # 降序
常用内置函数
nums = [3, 1, 4, 1, 5]
max(nums) # 5 — 最大值
min(nums) # 1 — 最小值
sum(nums) # 14 — 求和
len(nums) # 5 — 长度
all(nums) # True — 是否全部为真
any(nums) # True — 是否存在真
# enumerate: 同时获取索引和值（⭐ 极其常用）
for i, num in enumerate(nums):
print(f"索引 {i}: 值 {num}")
# zip: 同时遍历多个列表
names = ["a", "b", "c"]
ages = [20, 30, 40]
for name, age in zip(names, ages):
print(f"{name} is {age}")
# 输出: a is 20 / b is 30 / c is 40
# map: 对每个元素应用函数
list(map(str, [1, 2, 3])) # ['1', '2', '3']
# filter: 过滤元素
list(filter(lambda x: x > 2, [1, 2, 3, 4])) # [3, 4]
列表推导式进阶
# 带条件的列表推导式
result = [x if x > 0 else 0 for x in [-1, 2, -3, 4]] # [0, 2, 0, 4]
# 嵌套列表推导式（二维数组展平）
matrix = [[1, 2], [3, 4], [5, 6]]
flat = [x for row in matrix for x in row] # [1, 2, 3, 4, 5, 6]
# 创建字典的推导式
d = {x: x ** 2 for x in range(5)} # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
# 创建集合的推导式
s = {x % 3 for x in range(10)} # {0, 1, 2}
字符串操作
s = "Hello World"
# 基本操作
len(s) # 11
s[0] # 'H'
s[-1] # 'd'
s[0:5] # 'Hello'
# 遍历
for ch in s:
print(ch)
# 常用方法
s.lower() # 'hello world'
s.upper() # 'HELLO WORLD'
s.split() # ['Hello', 'World'] — 按空格分割
s.split(",") # 按逗号分割
",".join(["a","b"]) # 'a,b' — 用分隔符拼接
s.strip() # 去除首尾空白
s.replace("H", "J") # 'Jello World'
s.find("Wo") # 6 — 返回子串首次出现位置，找不到返回 -1
s.count("l") # 3 — 统计出现次数
s.isdigit() # False — 是否纯数字
s.isalpha() # False — 是否纯字母
s = 'h' + s[1:] # 'hello World'
# 字符串转列表（常用）
chars = list("abc") # ['a', 'b', 'c']
chars = [ch for ch in "abc"] # 同上
字典 / 哈希表
字典是 LeetCode 中最重要的数据结构之一，用于 O(1) 时间查找、计数、缓存。
基本操作
# 创建
d = {} # 空字典
d = dict() # 同上
d = {"a": 1, "b": 2} # 字面量
d = dict(a=1, b=2) # 另一种写法
# 增 / 改
d["key"] = value # 设置键值对（不存在则创建，存在则更新）
# 查
d["key"] # 获取值，键不存在会报错 KeyError！
d.get("key", default) # 安全获取，不存在返回 default（默认 None）
# 删
del d["key"] # 删除键值对
val = d.pop("key", None) # 弹出并返回值，不存在返回 None
# 判断键是否存在
"key" in d # True / False (⭐ 只判断键，不判断值！)
# 遍历
for key in d: # 遍历键
for key, val in d.items(): # 遍历键值对（最常用）
for val in d.values(): # 遍历值
LeetCode 经典用例
# 1. 频率统计（最常用！）
from collections import Counter
nums = [1, 1, 2, 3, 3, 3]
count = Counter(nums) # Counter({3: 3, 1: 2, 2: 1})
# 手动统计
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
# 2. 两数之和 — 哈希表 O(n)
def twoSum(nums, target):
seen = {} # {值: 索引}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
# 3. 字符频率
s = "hello"
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
集合 (Set)
# 创建
s = set() # 空集合（⚠️ 不能用 {}，那是字典）
s = {1, 2, 3} # 有元素的集合
# 操作
s.add(4) # 添加
s.remove(2) # 删除（不存在报错）
s.discard(2) # 删除（不存在不报错）
3 in s # O(1) 存在性判断！⭐
# 集合运算
a = {1, 2, 3}
b = {2, 3, 4}
a | b # 并集 {1, 2, 3, 4}
a & b # 交集 {2, 3}
a - b # 差集 {1} (在a中但不在b中)
a ^ b # 对称差集 {1, 4} (只在一边)
# 去重（常用！）
nums = [1, 2, 2, 3, 3, 3]
unique = list(set(nums)) # [1, 2, 3]
栈与队列
栈 — 用 list 模拟
stack = []
# 入栈
stack.append(1) # [1]
stack.append(2) # [1, 2]
# 出栈
stack.pop() # 返回 2，栈变为 [1]
# 查看栈顶
stack[-1] # 1（不弹出）
# 判空
if not stack: # 空栈
print("empty")
# 典型应用：括号匹配
def isValid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stack # 栈空才算完全匹配
队列 — 用 collections.deque
from collections import deque
q = deque()
# 入队
q.append(1) # 右边进
q.append(2)
# 出队
q.popleft() # 左边出 → 1 (先进先出 FIFO)
# 也可以从左边进、右边出
q.appendleft(0) # 左边进
q.pop() # 右边出
# ⚠️ 不要用 list.pop(0)！它是 O(n)，deque.popleft() 是 O(1)
单调栈（单调队列）
# 单调递增栈：栈内元素始终保持递增
# 常用于解决"下一个更大元素"类问题
def nextGreaterElement(nums):
stack = []
result = [-1] * len(nums)
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
idx = stack.pop()
result[idx] = num
stack.append(i)
return result
堆 (Heap)
import heapq
# Python 只有最小堆！最大堆需要取反
nums = [3, 1, 4, 1, 5, 9]
# 堆化（原地）
heapq.heapify(nums) # [1, 1, 4, 3, 5, 9]
# 入堆
heapq.heappush(nums, 2) # O(log n)
# 出堆（弹出最小元素）
smallest = heapq.heappop(nums) # O(log n)，返回最小值
# 查看堆顶（不弹出）
nums[0] # O(1)
# Top K 问题（⭐ 高频考点！）
# 找到最大的 K 个元素
def topK(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) # 弹出最小的，保留 K 个最大的
return heap # K 个最大元素（无序）
# 最大堆：存负数！
max_heap = []
heapq.heappush(max_heap, -5) # 入堆时取负
largest = -heapq.heappop(max_heap) # 出堆时再取负
常用算法模式
双指针
# 反转数组
def reverse(nums):
left, right = 0, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 移除重复元素（有序数组）
def removeDuplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
滑动窗口
# 找无重复字符的最长子串长度
def lengthOfLongestSubstring(s):
seen = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
递归与回溯
# 递归三要素：
# 1. 终止条件（base case）
# 2. 递归调用（缩小问题规模）
# 3. 合并结果
# 二叉树最大深度
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
# 全排列（回溯）
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:]) # ⚠️ 要拷贝！
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop() # 撤销选择
used[i] = False # 撤销标记
backtrack([], [False] * len(nums))
return result
动态规划 (DP) 入门
# DP 核心：状态定义 + 状态转移方程
# 本质是"用数组记录中间结果，避免重复计算"
# 斐波那契数列
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 空间优化版
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
# 爬楼梯（经典 DP）
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
BFS / DFS
from collections import deque
# BFS 模板（层序遍历 / 最短路径）
def bfs(start):
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
# 处理 node
for neighbor in get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS 模板（递归版）
def dfs(node, visited=set()):
if node in visited:
return
visited.add(node)
# 处理 node
for neighbor in get_neighbors(node):
dfs(neighbor, visited)
# DFS 模板（迭代版 — 用栈）
def dfs_iterative(start):
stack = [start]
visited = set([start])
while stack:
node = stack.pop()
# 处理 node
for neighbor in get_neighbors(node):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
进阶数据结构速查
Defaultdict — 自带默认值
from collections import defaultdict
# 普通写法
d = {}
for num in nums:
if num not in d:
d[num] = []
d[num].append(num * 2)
# defaultdict 写法
d = defaultdict(list) # 默认值是一个空列表
for num in nums:
d[num].append(num * 2) # 不需要判断 key 是否存在！
d = defaultdict(int) # 默认值 0，适合计数
for num in nums:
d[num] += 1
OrderedDict — 保持插入顺序
from collections import OrderedDict
# Python 3.7+ 普通 dict 已经有序，但 OrderedDict 有额外方法
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od.move_to_end('a') # 把 'a' 移到最后
od.popitem(last=False) # 弹出第一个（FIFO）
lru_cache — 记忆化递归
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# 自动缓存结果，避免重复计算！DFS + 记忆化的神器
常用 Python 技巧速查
# 交换两个变量
a, b = b, a
# 同时赋值
x, y = 1, 2
# 一行反转
nums = nums[::-1]
# 最大值 / 最小值
float('inf') # 正无穷
float('-inf') # 负无穷
max_val = max(nums, default=0)
# 三元表达式
result = a if condition else b
# 快速去重 + 判断
if len(set(nums)) < len(nums): # 存在重复
# 列表转字符串
''.join(['a', 'b', 'c']) # 'abc'
# 整除与取模
7 // 2 # 3 (整除)
7 % 2 # 1 (取余)
divmod(7, 2) # (3, 1) 一步到位
系统学习笔记
滑动窗口与双指针
定长滑动窗口
基础
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = "aeiou" # 直接用字符串，无需 set
# 1. 初始化第一个窗口（前 k 个字符）
window_vowels = 0 # 当前窗口内元音数
for i in range(k):
if s[i] in vowels:
window_vowels += 1
max_vowels = window_vowels # 记录最大值，初始为第一个窗口
# 2. 滑动窗口，从索引 k 开始遍历
for i in range(k, len(s)):
# 右端点进入窗口
if s[i] in vowels:
window_vowels += 1
# 左端点离开窗口
if s[i - k] in vowels:
window_vowels -= 1
# 更新最大值
if window_vowels > max_vowels:
max_vowels = window_vowels
# 剪枝（若已达到理论最大值 k，提前结束）
if max_vowels == k:
break
return max_vowels
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k
不定长滑动窗口
求最长/最大
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = left = 0
cnt = defaultdict(int)
for right, c in enumerate(s):
cnt[c] += 1
while cnt[c] > 1:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
ans = left = 0
cnt = defaultdict(int)
for right, c in enumerate(s):
cnt[c] += 1
while cnt[c] > 2:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
单序列双指针
同向双指针
class Solution:
def reverseString(self, s: List[str]) -> None:
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
相向双指针
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
s = list(s)
left, right = 0, len(s) - 1
while left < right:
if s[left] > s[right]:
s[left] = s[right]
else:
s[right] = s[left]
left += 1
right -= 1
return ''.join(s)
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
同向双指针
class Solution:
def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
result = [] # 存放最终结果的索引列表
cursor = 0 # 去重游标，记录下一个待加入结果的索引位置
for pos, value in enumerate(nums):
if value != key:
continue
# 当前 key 的位置是 pos，可覆盖的索引范围是 [pos - k, pos + k]
# cursor 必须向右移动到当前区间左端点，避免重复添加
cursor = max(cursor, pos - k)
# 将 [cursor, pos + k] 范围内尚未添加的索引全部加入结果
while cursor <= min(pos + k, len(nums) - 1):
result.append(cursor)
cursor += 1
return result
背向双指针
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
length = len(nums)
max_score = cur_min = nums[k]
left = right = k
for _ in range(length - 1):
# 判断向哪一侧扩展：
# 1. 如果右指针已到边界，只能向左
# 2. 否则，比较左右两侧相邻的值，谁大就向谁扩展（尽量维持最小值不降太快）
if right == length - 1 or (left > 0 and nums[left - 1] > nums[right + 1]):
left -= 1
cur_min = min(cur_min, nums[left])
else:
right += 1
cur_min = min(cur_min, nums[right])
max_score = max(max_score, cur_min * (right - left + 1))
return max_score
原地修改
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
for fast in range(len(nums)):
if(nums[fast]!=val):
nums[slow]=nums[fast]
slow+=1
return slow
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]: # nums[i] 不是重复项
nums[k] = nums[i] # 保留 nums[i]
k += 1
return k
双序列双指针
双指针
class Solution:
def addSpaces(self, s: str, spaces: List[int]) -> str:
ans = []
ptr1 = ptr2 = 0
for ptr1, ch in enumerate(s):
if ptr2 < len(spaces) and spaces[ptr2] == ptr1:
ans.append(' ')
ptr2 += 1
ans.append(ch)
return ''.join(ans)
class Solution:
def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
ptr1 = ptr2 = 0
while ptr1 < len(nums1) and ptr2 < len(nums2):
if nums1[ptr1] == nums2[ptr2]:
return nums1[ptr1]
elif nums1[ptr1] <= nums2[ptr2]:
ptr1 += 1
else:
ptr2 += 1
return -1
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
ptr1 = ptr2 = 0
ans = []
while ptr1 < len(nums1) and ptr2 < len(nums2):
if nums1[ptr1] == nums2[ptr2]:
ans.append(nums1[ptr1])
ptr1 += 1
ptr2 += 1
elif nums1[ptr1] < nums2[ptr2]:
ptr1 += 1
else:
ptr2 += 1
return ans
判断子序列
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if not s:
return True
i = 0
for ch in t:
if s[i] == ch:
i += 1
if i == len(s):
return True
return False
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
res = ""
for word in dictionary:
ptr1 = 0
ptr2 = 0
# 不断寻找 一直更新s指针ptr2
while ptr1 < len(word) and ptr2 < len(s):
# 如果符合 更新word中的ptr1
if word[ptr1] == s[ptr2]:
ptr1 += 1
ptr2 += 1
# 扫描结束 ptr1 == len(word)时才说明可以生成子序列
# 如果符合条件 更新res为当前word
# 条件1：长度等同word
if ptr1 == len(word):
# 条件2：word长度比现有res更长 或 长度相等时字母序更小 (题目要求)
if len(word) > len(res) or (len(word) == len(res) and word < res):
res = word
return res
分组循环
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
ans = 0
cur = 0
for i in range(len(nums)):
if nums[i] ==1:
cur += 1
ans = max(cur, ans)
else:
cur = 0
return ans
class Solution:
def maxPower(self, s: str) -> int:
ans = 1
cur = 1
s = list(s)
for i in range(len(s)-1):
if s[i] == s[i+1]:
cur += 1
ans = max(cur, ans)
else:
cur = 1
return ans
class Solution:
def checkZeroOnes(self, s: str) -> bool:
max_0, max_1 = 0, 0
num_0, num_1 = 0, 0
s = list(s)
for i in range(len(s)):
if s[i] == '1':
num_1 += 1
max_1 = max(num_1, max_1)
num_0 = 0
else:
num_0 += 1
max_0 = max(num_0, max_0)
num_1 = 0
return max_1 > max_0
二分算法
二分查找
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
else:
return middle
return -1
HOT100
128. 最长连续序列
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums)
ans = 0
for x in st:
if x-1 in st:
continue
y = x + 1
while y in st:
y += 1
ans = max(ans, y-x)
return ans
283. 移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
stack_size = 0
for x in nums:
if x:
nums[stack_size] = x # 把 x 入栈
stack_size += 1
for i in range(stack_size, len(nums)):
nums[i] = 0
11. 盛最多水的容器
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
ans = 0
while left < right:
ans = max(ans, (right - left) * min(height[left], height[right]))
if height[left] < height[right]:
left += 1
else:
right -= 1
return ans
如果改成“移动较高的那一侧”，那么：
- 宽度减小了，但短板（较矮的一侧）没有动，新的面积一定 ≤ 当前面积（因为高度上限还是那个短板，而宽度变小）；
- 因此你会错失那些通过移动短板、遇到更高柱子来增加面积的可能性。
最终算法会陷入局部，无法到达全局最优解。
15. 三数之和
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
n = len(nums)
for i in range(n - 2):
x = nums[i]
if i > 0 and x == nums[i - 1]: # 跳过重复数字 因为重复数字构成的数组相同
continue
# 剪枝优化
if x + nums[i + 1] + nums[i + 2] > 0: # 优化一：数组有序 当前大于0以后一定大于0
break
if x + nums[-2] + nums[-1] < 0: # 优化二：数组有序 加上最大两个数小于0一定全小于0
continue
# 双指针开始
j = i + 1
k = n - 1
while j < k:
s = x + nums[j] + nums[k]
if s > 0:
k -= 1
elif s < 0:
j += 1
else: # 三数之和为 0
# 避免重复
# j = i+1 表示刚开始双指针，此时 j 左边没有数字
# nums[j] != nums[j-1] 说明与上一轮循环的三元组不同
if j == i + 1 or nums[j] != nums[j - 1]:
ans.append([x, nums[j], nums[k]])
j += 1
k -= 1
return ans
力扣刷题心得
通信研0 零基础转码LeetCode-day1
今日完成：《编程入门》中的前10道题 目前进度10/18 MySQL题没有做，现在应该还不用做。 今天对leetcode模式有了些认识，大概知道是怎么用的了。第一次遇到二叉树问题，虽然只是简单的加法，但因为对力扣定义不熟悉，但还是一脸懵逼，后面就知道怎么弄了 今天对数组的操作又熟练了一些，用到了append join等 今天还遇到了&优先级高于>=的问题，导致最后一行判断代码出错。实际上是知道的但是写代码很容易疏忽，很自然的不加括号学到了。
通信研0 零基础转码LeetCode-day2
今日完成：《编程入门》中的所有题目 目前进度18/18
今天基接触到一些简单的数学问题，比如按位运算判断2幂次、判断质因数等
今天用到了list(str)、ans[:i]和ans[i:]左分割和右分割、s.count("1")等，并且接触了一道矩阵题目与一些数组题目
明日计划：总结这两天题目
通信研0 零基础转码LeetCode-day3
【一天一道，大厂报到】语言：python
今日完成：结合ai，总结了这两天题目所用到的基础知识，主要是列表、索引和切片
明日计划：《编程0到1》33道题 应该能写8-10道
通信研0 零基础转码LeetCode-day4
语言：python
今日完成：《编程0到1》6道题
今天的题难度明显偏上，感觉不像是入门级别的（也有可能是我太菜了）移动零这道题题解用双指针，我不会写也没看懂。好几道题都与数组有关，需要对算术有充分理解和全面考虑。再接再厉。
明日计划：《编程0到1》33道题 看情况 可能写6-8道
通信研0 零基础转码LeetCode-day5
语言：python 昨天因为看比赛和停电 鸽了一天
今日完成：《编程0到1》如图进度
今天的题比day4刚上来的题简单了很多，但是有的也很难，比如罗马数字转换我直到现在还没看懂。今天还写了几道模拟题，都是一些真实过程比如井字棋、走循环什么的。也是有些有点难
明日计划：《编程0到1》还剩16道题 明天后天各8道
通信研0 零基础转码LeetCode-day6
语言：python
今日完成：《编程0到1》6道题
今天本来要做8道题，奈何矩阵那部分实在不会。感觉现在对矩阵的使用还是很生疏，碰到稍微复杂一点的就不会用了。后面还是要把矩阵数组等知识点再重新用熟练一点。
今天后半部分做的数学问题，反而感觉友好一点。接触了简单的贪心算法等等，不能暴力求解了。
明日计划：《编程0到1》最后8道题
通信研0 零基础转码LeetCode-day7
语言：python
今日完成：《编程0到1》4道题
今天本来要做8道题，但是我发现链表部分内容我没接触过，而且看b站讲解也看不懂。看来还是要补点数据结构的基础知识，不然力扣定义都看不懂。
今天是手动实现pow、向量叉乘判断共线都挺有意思，又复习了一点数学知识。
后面的都是开会员才能做的问题，不管了。
明日计划：看代码随想录，学点基础知识，然后总结这七天的题型和知识点。
通信研0 零基础转码LeetCode-day8
语言：python 今日完成：总结python基础语言用法
今天看了看代码随想录，发现他里面都是教的C++实现，而不是python，请教一下各位有没有必要看，还是因为我没有找到python。
明日计划：学点基础知识，然后总结这七天的题型和知识点。
通信研0 零基础转码LeetCode-day9
语言：python 昨天又鸽了一天 没有理由 单纯爱玩
今日学习：学习了定长窗口滑动，学了一道例题，做了一道题。
都是给定数组或字符串，定长k，求最值。例题是求最大元音子串，练习题是求最大均值。两个的主要思想都是窗口滑动。先求前k项，然后在窗口滑动的同时增减左右项。需要特别注意边界数值。比如窗口右端是i，左端应该是i-k+1。但是在右移增加的是nums[i]，减去左端的是nums[i-k]。
今天又简单看了看代码随想录，觉得还是不太适合我，太乱了看着难受。发现灵茶山艾府的题单和讲解看着很舒服。所以决定这段时间按照这个来进行。
明日计划：按题单继续慢慢来，争取一天一个知识点。
# 1456
class Solution:
def maxVowels(self, s: str, k: int) -> int:
# total: 记录所有长度为 k 的子串中元音的最大数量
# ans: 记录当前滑动窗口内的元音数量
total = ans = 0
# i 是窗口的右端点，c 是 s[i]
for i, c in enumerate(s):
# 1. 右端点字符进入窗口
# 如果当前字符是元音，则窗口内元音数 +1
if c in "aeiou":
ans += 1
# 计算窗口的左端点索引
left = i - k + 1
# 如果 left < 0，说明窗口内字符数还不足 k 个
# 此时不能进行统计（窗口不完整），也不能移除左端点（索引为负）
# 直接跳过本轮循环，等待窗口填满
if left < 0:
continue
# 2. 窗口已完整（长度为 k），更新全局最大值
total = max(ans, total)
# 如果当前窗口元音数已经达到理论最大值 k
# 不可能有更大的值了，直接结束循环（剪枝优化）
if ans == k:
break
# 3. 窗口向右滑动：左端点离开窗口
# 如果左端点字符是元音，需要从当前窗口中减掉
if s[left] in "aeiou":
ans -= 1
# 返回最大元音数
return total
通信研0 零基础转码LeetCode-day10
语言：python
今日学习：学习了不定长窗口滑动，其实就学了一道题，但这道题好像是高频考点。
相比较于定长窗口滑动，不定长窗口解决的是最长问题。并且学到了利用字典，统计字符出现个数。比如最长不重复字串，在右窗口确定之后，滑动左窗口。每次右端确定时，右端字符统计值＋1，如果有重复，再滑动左端，同时去除上一个左端的统计值。最后所求ans是所有cnt[c] == 1的窗口长度，也就是right-left+1。
第二道题是每个字符最多出现两次的最长子字符串，观察后发现只需将第一题判断改为>2即可。
明日计划：一天一个知识点。
通信研0 零基础转码LeetCode-day11
语言：python
今日学习：学习了反转字符串和相向双指针
本质上是都是相向双指针。是指s[left]与s[right]一起向中间移动，其中left是i，right=n-1-i。当left < right时，二者同时向中间移动。也可以写成单指针形式，在range(len(s)//2)内，分别是s[i]与s[-i-1]。
同时学到s[i].isalnum()是判断是否为字母或者数字。
明日计划：同向双指针与背向双指针
#字典序最小回文串
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
s = list(s)
for i in range(len(s) // 2):
if s[i] > s[-i - 1]:
s[i] = s[-i - 1]
else:
s[-i - 1] = s[i]
return ''.join(s)
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
s = list(s)
left, right = 0, len(s) - 1
while left < right:
if s[left] > s[right]:
s[left] = s[right]
else:
s[right] = s[left]
left += 1
right -= 1
return ''.join(s)
通信研0 零基础转码LeetCode-day12
语言：python
今日学习：学习了同向双指针和背向双指针
同向双指针是两个指针一直向右移动。背向双指针是从中间开始两个指针分别向两端移动。
一开始写找相邻k下标题的时候，自己想了一个暴力办法，先把索引全部存入数组，然后再用两个循环添加符合条件的角标，也能通过了。后面看了题解，学习了同向双指针，了解到了可以根据pos和cursor同时向右更新的双指针写法，同时更新cursor可以避免重复加入。见图3
下一道学习背向双指针的题还是比较难的。要求从k开始向两边扩展，所以叫做背向，为了满足最小面积的题意，所以在扩展的时候要优先扩展较大的数，才能保持最小值变化小（因为向左向右长度都是1）。
明日计划：原地修改2-3道题学习
# 2200 同向双指针
class Solution:
def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
index ,ans = [], []
for i in range(len(nums)):
if nums[i] == key:
index.append(i)
for jiaobiao in range(len(nums)):
for i in range(len(index)):
if abs(jiaobiao - index[i]) <= k:
ans.append(jiaobiao)
break
return ans
class Solution:
def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
result = [] # 存放最终结果的索引列表
cursor = 0 # 去重游标，记录下一个待加入结果的索引位置
for pos, value in enumerate(nums):
if value != key:
continue
# 当前 key 的位置是 pos，可覆盖的索引范围是 [pos - k, pos + k]
# cursor 必须向右移动到当前区间左端点，避免重复添加
cursor = max(cursor, pos - k)
# 将 [cursor, pos + k] 范围内尚未添加的索引全部加入结果
while cursor <= min(pos + k, len(nums) - 1):
result.append(cursor)
cursor += 1
return result
# 1793
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
length = len(nums)
max_score = cur_min = nums[k]
left = right = k
for _ in range(length - 1):
# 判断向哪一侧扩展：
# 1. 如果右指针已到边界，只能向左
# 2. 否则，比较左右两侧相邻的值，谁大就向谁扩展（尽量维持最小值不降太快）
if right == length - 1 or (left > 0 and nums[left - 1] > nums[right + 1]):
left -= 1
cur_min = min(cur_min, nums[left])
else:
right += 1
cur_min = min(cur_min, nums[right])
max_score = max(max_score, cur_min * (right - left + 1))
return max_score
首先，做一个假设：已经具备了解决某算法问题其中之一解所需要的知识点。这个假设非常的重要，很多时候做不出来题目是因为缺乏了某个思维技巧或者知识点。
感悟： 拿到题目千万不要一上来就恨不得马上想出最优解。 拿到题目千万不要一上来就恨不得马上想出最优解。 拿到题目千万不要一上来就恨不得马上想出最优解。
一个更好的思考链路应该是这样的：
-
确保读懂题目并且把normal case和edge case都想一想怎么得出正确答案
-
在不考虑时间或者空间复杂度的情况下，想出暴力解。这里我要非常的强调，千万千万千万不要小看暴力解。因为能得出暴力解说明至少你读懂了题目要什么和你要干什么
-
以暴力解为锚点，思考暴力解最慢的瓶颈在哪里。
-
知道瓶颈在哪里之后，就可以有针对性的思考怎么解决瓶颈。举一个例子，假设一个暴力姐需要我们枚举每个元素的时候都要遍历元素的左边来找到左边的最小值，那么这个暴力解最慢的瓶颈就在于每次都要重复的向左遍历，于是我们就可以想到用前缀最小来优化时间复杂度。
-
在新的思路下重新思考题解，注意过程中的细节和确保edge case能过。
在使用以上思路的时候，认真体会这句话： 算法的本质就两种：聪明的枚举（枚举右维护左，哈希表，前缀，前缀和等等）和无遗漏（DFS/BFS/DP等等）的枚举。
通信研0 零基础转码LeetCode-day13
语言：python 今日学习：学习了原地修改几道题型 本质还是双指针
但是这个双指针是快慢指针。比如移除元素、删除重复项，都是两个同向双指针不同速移动。
明日计划：双序列双指针
# 27 移除元素
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
stack_size = 0
for x in nums:
if x != val:
nums[stack_size] = x
stack_size += 1
return stack_size
# 26 删除有序数组中的重复项
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]: # nums[i] 不是重复项
nums[k] = nums[i] # 保留 nums[i]
k += 1
return k
明日计划：原地修改2-3道题
通信研0 零基础转码LeetCode-day14
语言：python 今日学习：做了三道分组循环的题
一开始不懂这个分组循环的意思，就按照正常想法自己做，也很简单，都一下子做出来了。
做完以后结合ai揣摩了一下，逐渐理解了分组循环写法的含义，并且更新了答案。不过就复杂度而言，两者并没有什么差别，但是更不容易犯错了。比如我第一次代码就忘了在更新当前组的时候重置其他组，但是分组循环就不存在这个问题。遇到“最长连续递增子段”、“最长连续奇偶段”、“压缩字符串”等同类题型都可以用。
明日计划：暂没定
class Solution:
def checkZeroOnes(self, s: str) -> bool:
max_0, max_1 = 0, 0
num_0, num_1 = 0, 0
s = list(s)
for i in range(len(s)):
if s[i] == '1':
num_1 += 1
max_1 = max(num_1, max_1)
num_0 = 0
else:
num_0 += 1
max_0 = max(num_0, max_0)
num_1 = 0
return max_1 > max_0
# 分组循环写法
class Solution:
def checkZeroOnes(self, s: str) -> bool:
n = len(s)
i = 0
max_0 = 0
max_1 = 0
while i < n:
j = i
# 内层循环：找到与 s[i] 相同的连续段的右边界（不包含）
while j < n and s[j] == s[i]:
j += 1
# 此时 s[i:j] 是一组连续的相同字符，长度为 j - i
length = j - i
if s[i] == '1':
max_1 = max(max_1, length)
else: # s[i] == '0'
max_0 = max(max_0, length)
# 跳到下一组
i = j
return max_1 > max_0
通信研0 零基础转码LeetCode-day15
语言：python 昨天又鸽了 单纯不想学
今日学习：双序列双指针
双序列双指针，顾名思义就是两个列表或者数组，二者内在存在联系。通法是定义ptr1和ptr2，分别在两个序列上移动，符合条件时，可以进行操作。
对于350两个数组的交集，我使用固定双指针写法如图。题解给了一个更好用的判断，用counter数元素个数，更快更方便。
明日计划：判断子序列
# 350 两个数组的交集
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
ptr1 = ptr2 = 0
ans = []
while ptr1 < len(nums1) and ptr2 < len(nums2):
if nums1[ptr1] == nums2[ptr2]:
ans.append(nums1[ptr1])
ptr1 += 1
ptr2 += 1
elif nums1[ptr1] < nums2[ptr2]:
ptr1 += 1
else:
ptr2 += 1
return ans
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
cnt = Counter(nums1)
ans = []
for x in nums2:
if cnt[x] > 0:
cnt[x] -= 1
ans.append(x)
return ans
通信研0 零基础转码LeetCode-day16
语言：python
今日学习：判断子序列
今天做了两道判断子序列的题，本质还是双指针，同样规定ptr1与ptr2。判断应该依旧是在指针位置与所需字符长度相等时进行。我想了想也是沿着这个思路写，最后发现和标准题解的思路一样。
第二道题感觉比较难，复制了点。其中删去字符一开始搞的我不知道怎么办。后来，发现似乎是快慢指针的应用，用两个不同缩进的ptr+=就可以做到。顺利解决。
今天还知道了字典序的判断，python可以直接比较字典序。
明日计划：暂未定
通信研0 零基础转码LeetCode-day17
语言：python
今日整理：滑动窗口与指针的做过题目
今天把这几天做的第一部分的所有题目整理到了md里，方便重新阅读和思考（超链接挺好用的）。
明日计划：这几天都消化笔记 重新读题 争取总结出自己的模板
通信研0 零基础转码LeetCode-day18
语言：python
今日学习：hot100 2/100
今天做了两道题，不能说是做了，只能说是认真学习与记忆...可能性价比最高的就是记忆
第一道是128.连续最长序列，要求复杂度为O(n)。set排序以后，很巧妙的运用if x-1 in st:审查是否为起点，来减少循环次数。x和y实际上也是一个双指针问题。
第二道是283.移动0，要求原地修改。可以把非零元素入栈，并同时记录个数，入栈完成后把剩余的所有元素都置零，也就是for i in range(stack_size, len(nums))置零。
通信研0 零基础学习LeetCode-day19
语言：python
今日学习：hot100×2 总进度4/100
第一道是11.盛最多水的容器。这道题是正常的相向双指针，但是我在做的时候仍然对指针的移动判断反了。后来搞清楚，木桶问题容量要根据短的木板来定，短木板移动时面积可能增大或减小，长木板移动时新的面积一定 ≤ 当前面积，移动长木板会错失那些通过移动短板、遇到更高柱子来增加面积的可能性，所以才尽量保证短指针先移动，这才解释清楚。
第二道是15.三数之和。这道题需要考虑的很多，最重要的就是去重问题。排序以后，先固定x，然后在剩余范围内进行相向双指针寻找。和第一题一样，考虑指针移动的先后顺序，要求三数之和为0，对于排列好顺序的数组而言，三数之和大于0需要右指针左移，小于0需要左指针右移。
本题涉及以下几个点
-
定第一个数x后，如果第一个数与前面一个数相同，则直接去除，因为算法相同，之后得到的三数一定也相同。
-
优化1：定第一个数x后，如果x + nums[i + 1] + nums[i + 2]大于0，那么之后所有的x构成的三元数组一定都大于0，一定不存在符合条件的数组，直接break。
-
优化2：定第一个数x后，对于有序数组，加上最大两个数小于0一定全小于0，可以跳过这个x直接进行下一个x。
-
去重策略1：当第二个数j是初始位置时 j == i + 1 一定不是重复数组
-
去重策略2：nums[j] != nums[j - 1]当第二个数j不是初始位置时，判断当前 nums[j]是否和左指针的上一个值相同，不相同一定不是重复数组