Hot100二刷
记录一些写起来还是磕磕绊绊的题目。
最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
哈希问题，用于快速查找相应元素是否存在。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums) # 将 nums 转化为哈希集合
m = len(st)
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) # 尝试更新最大长度
if ans * 2 >= m: # 裁剪，没有继续比较下去的必要了
break
# 虽然是双层循环，但是带入问题就能发现，不符合的都被跳过，每个元素至多被查找常数次
return ans
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
左右指针问题，注意移动指针的时机即可。
class Solution:
def maxArea(self, height: List[int]) -> int:
ans = 0
left, right = 0, len(height) - 1
while left < right:
volumn = (right - left) * min(height[left], height[right])
ans = max(ans, volumn)
if height[left] < height[right]:
# 左侧是短板，移动右侧垂线于事无补，尝试移动左侧
left += 1
else:
# 同理
right -= 1
return ans
三数之和
给你一个整数数组 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]]:
# 三数之和且需要返回值，考虑双指针，排序后固定一个元素转化为两数之和问题
result = []
nums.sort()
n = len(nums)
# 固定一个元素
for i in range(n - 2):
if nums[i] > 0: # 三数中的最小值大于0，剪枝
break
# 由于不能重复，对于首元素需要进行去重
if i > 0 and nums[i] == nums[i - 1]:
continue
# 转为目标和问题，左右指针
left = i + 1
right = n - 1
while left < right:
three_sum = nums[i] + nums[left] + nums[right]
if three_sum == 0: # 符合条件
result.append([nums[i], nums[left], nums[right]])
# 针对第二位元素的去重
while left < right and nums[left + 1] == nums[left]:
left += 1
# 第三位元素去重
while left < right and nums[right - 1] == nums[right]:
right -= 1
# 指针移动到下一个不同位置
left += 1
right -= 1
elif three_sum > 0:
# 三数和偏大，右指针移动
right -= 1
else:
# 三数和偏小，左指针移动
left += 1
# 每个位置去重，显然不是说每个元素在三个数字中只能出现一次，所以显然不能对原本的数组利用set去重
return result
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
直接看注释吧，写的很好。
class Solution:
def trap(self, height: List[int]) -> int:
if not height: return 0 # 边界保护（空数组无法接水）
ans = 0
# left_max: 动态记录「左指针当前位置及其左侧」遇到的最高柱子
# right_max: 动态记录「右指针当前位置及其右侧」遇到的最高柱子
left_max = right_max = 0
# 双指针初始化：分别从数组两端向中间靠拢
left, right = 0, len(height) - 1
# 核心前提：每个位置能接的雨水 = min(左侧最高, 右侧最高) - 当前柱高
# 双指针的精髓：我们不需要提前遍历两遍去存左右最大值数组（省空间）
# 而是通过“比较两侧已知的最大值”，动态判断当前指针位置的瓶颈是哪一侧
while left < right:
# 1. 实时更新两侧遍历至今的最高屏障
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
# 2. 【关键决策】为什么比大小就能移动指针？
# 如果 left_max < right_max：
# 说明 left 位置的“右侧最高”至少是 right_max（实际可能更高，但不影响）
# 因为 right_max 已经 > left_max，所以 left 位置的短板一定是 left_max
# 即：min(真实左高, 真实右高) = left_max ✅ 确定无疑
# 因此可以安全计算 left 处的水量，并放心地把 left 往右移
if left_max < right_max:
# 接水量 = 短板高度 - 当前柱子自身高度（若自身就是最高柱，水量为0，公式依然成立）
ans += left_max - height[left]
left += 1 # 左侧当前位置处理完毕，向内收缩
# 同理，如果 right_max <= left_max：
# 说明 right 位置的短板一定是 right_max
# 安全计算水量，并将 right 左移
else:
ans += right_max - height[right]
right -= 1 # 右侧当前位置处理完毕，向内收缩
return ans
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
连续子串问题，经典滑动窗口，无重复要求能够快速查找，配合哈希表，记忆一下set的主要操作是in、remove、add
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 连续子串问题，使用滑动窗口
char_set = set() # 子串中要不能含有重复字符，想到利用集合存储当前窗口字符，查找快速
left = 0
result = 0
for right in range(len(s)):
# 如果当前字符已经在窗口中，收缩窗口，即移动左指针直到移除该字符
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# 将当前字符加入窗口
char_set.add(s[right])
# 更新最大长度，写了几条感觉都没必要为了节省一点时间而判断更新，统一逻辑更新结果最为稳妥
result = max(result, right - left + 1)
return result
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
连续子串问题，且固定窗口大小，滑动窗口解决。
from typing import List
from collections import defaultdict
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
window_size = len(p)
total_size = len(s)
if total_size < window_size:
return []
result = []
left = 0
need = defaultdict(int) # 默认值为0
window = defaultdict(int)
for ch in p:
need[ch] += 1
for right in range(total_size):
# 扩展窗口
if s[right] in need:
window[s[right]] += 1
# 当窗口长度达到 window_size 时才判断
if right - left + 1 == window_size:
if need == window:
result.append(left)
# 收缩窗口（移动左指针）
if s[left] in need:
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
return result
使用字典记录窗口中的键和值并进行比较，简化写法借助于Counter优化代码。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
cnt_p = Counter(p) # 统计 p 的每种字母的出现次数
cnt_s = Counter() # 统计 s 的长为 len(p) 的子串 t 的每种字母的出现次数
ans = []
left = 0
for right, c in enumerate(s):
cnt_s[c] += 1 # 右端点字母进入窗口
if right - left + 1 == len(p):
if cnt_s == cnt_p: # t 和 p 的每种字母的出现次数都相同
ans.append(left) # t 左端点下标加入答案
cnt_s[s[left]] -= 1 # 左端点字母离开窗口
left += 1
return ans
和为 k 的子数组
给定一个整数数组和一个整数 k ，请找出该数组中和为 k 的连续子数组的个数。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
result = 0 # 记录结果
pre_sum = 0
records = Counter({0:1})
for num in nums:
pre_sum += num
result += records[pre_sum - k]
records[pre_sum] += 1
return result
- 创建一个字典
records，用于记录前缀和出现的次数。初始时，将0作为键，1作为值，表示前缀和为0的子数组出现的次数为1。 - 创建一个变量
pre_sum，用于记录当前前缀和。初始值为0。 - 遍历数组
nums，对每个元素进行处理。 - 将当前元素添加到
pre_sum中，得到当前前缀和。 - 检查
pre_sum - k是否存在于records中，如果存在，则说明存在一个子数组的起始位置为pre_sum - k，结束位置为当前位置，和为k。将结果result加1。 - 将当前前缀和
pre_sum作为键，出现次数加1，并更新records。
首先是前缀和思路，解决连续子数组的和，后来为了快速查询，想到时间换换空间，利用字典记录前缀和出现的次数，通过前缀和减去k，快速查询到和为k的子数组。
Counter就类似于字典，本质就是进行哈希。
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
每次都需要找出固定大小窗口中的最大值，由于需要从窗口中移除元素，使得问题变得复杂，单调队列？维持一个单调队列，左侧出，右侧进，最大值永远是最左侧元素。
单调队列套路：
- 右边入，元素进入队尾，同时维持队列单调性 pop
- 左边出，元素离开队首
- 记录/维持答案，通常是根据队首元素
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = []
q = deque() # 存储索引，不是值
for i in range(len(nums)):
# 1. 移除超出窗口的索引，即左边出
while q and q[0] <= i - k:
q.popleft()
# 2. 维护单调递减队列，即右边入
while q and nums[q[-1]] <= nums[i]:
q.pop()
# 3. 添加当前索引
q.append(i)
# 4. 当窗口形成后，记录结果
if i >= k - 1:
ans.append(nums[q[0]])
return ans
判断元素是不是窗口中合法元素，何时移除有时候很乱，但只要下标不符合窗口边界，必然需要移除，因此我们维持一个元素是下标的队列，队列的单调逻辑还是根据下标对应的实际值来的。
此时的窗口就是下标满足要求的元素，且内部为单调队列，故而直接取队头元素即可。存储索引而不是存储值！因为值可以很容易通过索引获得。
最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
思路：滑动窗口，窗口内包含t中的所有字符，则窗口内就是t的子串。
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 想到了左右指针滑动窗口，不满足条件就扩张，满足条件就记录并收缩窗口
if not s or not t:
return ""
# 是否包含每一个字符？还是比较的键和值，有点类似于字母异位词那道题目
cnt_t = Counter(t)
cnt_zero = Counter({key: 0 for key in cnt_t})
min_len = float('inf')
ans = ""
left = 0
for right, char_s in enumerate(s):
# 需要的字符
if char_s in cnt_t:
cnt_zero[char_s] += 1
# 满足条件时收缩窗口
while cnt_zero >= cnt_t:
# 先记录当前有效窗口，看能否更新结果
if right - left + 1 < min_len:
min_len = right - left + 1
ans = s[left : right + 1]
# 收缩
if s[left] in cnt_t:
cnt_zero[s[left]] -= 1
left += 1
return ans
Counter比较大小，在 Python 的 collections.Counter 中，>= 运算符被重载为 “超集（superset）”比较，其行为是：
对于 Counter 对象 a 和 b，a >= b 返回 True 当且仅当 b 中的每一个键 k 都满足 a[k] >= b[k]（对于 b 中有而 a 中没有的键，a[k] 视为 0）。
最大子数组和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路：动态规划，状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])，表示以nums[i]为结尾的子数组的最大和。最后返回这些值的最大值。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
f = [0] * len(nums)
f[0] = nums[0]
result = f[0]
for i in range(1, len(nums)):
f[i] = max(nums[i], f[i-1] + nums[i])
result = max(result, f[i])
return result
当然也可以使用分治的思路解决该问题，左侧最大和右侧最大以及横跨左右最大的比较。结果就是三者中的最大的那个，不断分治合并即可。
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 按照左端点从小到大先进行排序
intervals.sort(key=lambda p: p[0])
ans = []
for interval in intervals:
# 能够进行合并就合并
if ans and interval[0] <= ans[-1][-1]:
# 更新合并区间右端点
ans[-1][-1] = max(interval[1], ans[-1][-1])
else:
# 不相交，无法进行合并，将其作为新的区间加入结果中
ans.append(interval)
return ans
有一点贪心的味道，就是每次都进行合并，直到无法进行合并为止。但更多的是区间重叠选择问题，主体思路是排序加扫描。
轮转数组
给定一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
注意是以切片赋值，等号左边一定要加[:]，否则是会绑定到新的地址，而原列表纹丝不动。
切片赋值其实会创建临时列表需要额外空间，更加优雅的做法是进行三次反转。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k % n
# 辅助函数：反转区间 [left, right]
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 🔑 三次反转：
# 1. 整体反转: [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
reverse(0, n-1)
# 2. 反转前k个: [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]
reverse(0, k-1)
# 3. 反转后n-k个: [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4] ✓
reverse(k, n-1)
除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# 计算前缀和和后缀和，空间换时间
pre_result = [1] * len(nums)
suf_result = [1] * len(nums)
result = [0] * len(nums)
m = len(nums)
for i in range(1, m):
pre_result[i] = pre_result[i-1] * nums[i-1]
for i in range(m - 2, -1, -1):
suf_result[i] = suf_result[i+1] * nums[i+1]
for i in range(m):
result[i] = pre_result[i] * suf_result[i]
return result
不允许使用除法，考虑直接解决问题，利用前缀乘积和后缀乘积，相乘即为结果。
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 使用常数级额外空间？考虑直接利用现有数组，一共可以至多放n个数字，1-n
for i in range(n):
# 不断交换，直到这次操作的所有数字都在应该在的位置上
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# 需要调整并且应该在的位置上确实摆放了不应该的数字
correct_idx = nums[i] - 1
nums[correct_idx], nums[i] = nums[i], nums[correct_idx]
# 之所以是while循环，是防止还需要进一步调整
# 查找第一个位置与上面的数字不匹配的，这就是我们要找的答案
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
使用常数级别额外空间解决问题，这个时候就得考虑是不是可以进行原地修改一些什么东西，存储一些什么信息帮助我们解题。
缺失的正数，可以利用数组本身进行原地修改，将数字放在正确的位置上，然后进行查找。
相交链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p
A + C + B = B + C + A
因此同样走相同路程，最后的交点就是相交节点的位置。
杨辉三角
动态规划经典题目，动态规划问题问问自己几个问题：
- DP数组含义是什么？
dp[i]到底代表什么？ - 确定递归公式：
dp[i]如何由子问题的最优解推导而来，即状态转移方程 - 初始化？
dp[0]是多少 - 遍历顺序？从前往后还是从后往前
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
result = [[1] * (i + 1) for i in range(numRows)]
for i in range(2, numRows):
for j in range(1, i):
result[i][j] = result[i-1][j-1] + result[i-1][j]
return result
掌握一下初始化二维列表的写法，怎样能够更加节省内存和时间？尽量减少运算？这些都需要思考。
打家劫舍
也是经典的动态规划问题
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [nums[0]] * n
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1]
dp[i]表示到第i家时，所能偷盗的价值的最大值，取决于先前两个状态决定此刻是否进行偷盗。
莫名给我有种马尔可夫的意味在里面，只看当前状态或者当前状态的前几个状态进行决策。
完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution:
def numSquares(self, n: int) -> int:
sqrts = []
for j in range(1, n + 1):
if j * j <= n:
sqrts.append(j * j)
else:
break
# print (sqrts)
dp = [n + 1] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for num in sqrts:
if i - num < 0:
break
dp[i] = min(dp[i], dp[i - num] + 1)
return dp[n]
一看到题目还是没有思路，仔细想想要求和为n的完全平方数的最小数量，不妨先看看可以由哪些完全平方数组成，由此子问题便出来了。
零钱兑换
零钱兑换，也是经典的动态规划问题，和完全平方数一样，也是从最小的子问题开始，逐步构建出整体问题。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
# coins.sort()
for i in range(1, amount + 1):
for coin in coins:
if i < coin:
continue
dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[amount] == (amount + 1) else dp[amount]
区别仅仅在于可以选择的数这个问题是给了我们的的，不需要自己构建。
单词拆分
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [True] + [False] * n
for i, c in enumerate(s, start=1):
# print(i, c)
for word in wordDict:
if dp[i]:
break
m = len(word)
if i < m:
continue
if s[i-m:i] == word:
# print(word)
dp[i] = dp[i-m]
# print(dp)
return dp[n]
其实基本思路和之前两道题目还是一样，下面有利用哈希来进行优化的代码，不过我觉得下标有点绕，还如不上面的清楚：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
max_len = max(map(len, wordDict)) # 用于限制下面 j 的循环次数
words = set(wordDict) # 便于快速判断 s[j:i] in words
n = len(s)
f = [True] + [False] * n
for i in range(1, n + 1):
for j in range(i - 1, max(i - max_len - 1, -1), -1):
if f[j] and s[j:i] in words:
f[i] = True
break
return f[n]
最长递增子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
result = 1
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i-1, -1, -1):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
result = max(dp)
return result
思路其实都大同小异。
注意同前缀和以及单调栈问题区分开来，两者要求连续性以及不可回溯，与本题并不适配。
乘积最大子数组
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
# 初始化：第一个元素的最大、最小乘积和全局结果
cur_max = cur_min = result = nums[0]
for i in range(1, len(nums)):
num = nums[i]
# 三个候选值：前一个最大乘当前、前一个最小乘当前、当前单独
candidates = (cur_max * num, cur_min * num, num)
cur_max, cur_min = max(candidates), min(candidates)
# 更新全局最大值
result = max(result, cur_max)
return result
要求是连续子数组，由于可能出现负负得正的情况，所以要记录当前最大值和最小值，分别作为候选值。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
f_max = [0] * n
f_min = [0] * n
f_max[0] = f_min[0] = nums[0]
for i in range(1, n):
x = nums[i]
f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x)
f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x)
return max(f_max)
只依赖于前一项，所以其实也没必要使用动态规划数组。
需要注意这里动态规划数组的每一项的含义究竟是什么？表示以某项为结尾的子数组的最大乘积和最小乘积。
但显然全局结果并一定就是以最后一个元素为结尾，所以要取最大值。
一定要时刻清醒，动态规划数组的含义一定要清楚。
分割等和子集
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
# dp[i]表示能否凑出和为i的组合
dp = [True] + [False] * target
# 数字只能使用一次，因此可以将数字放在外层
for num in nums:
# 这一个数字可以覆盖的更新范围
# 为何从后往前？想象从前往后，可能刚刚用这个数字更新了前面某一个状态，再次使用该数字，显然不对
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
问题其实很好等价：就是看能否找到一个子集使得和为target//2
状态转移方程：dp[i] = dp[i] or dp[i - num]: 表示当前数字是否可以凑出和为i的组合。
这道题确实值得思考的地方很多，包括循环的设置，变量的更新范围。
最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
经典hard题目：
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 栈用来存储下标，核心思想：栈底始终存放“最后一个无法匹配的右括号的位置”
# 初始化栈，放入 -1 作为“虚拟的起始边界”。这样当有效括号从 index 0 开始时，长度计算依然正确。
st = [-1]
ans = 0 # 记录最长有效括号子串的长度
# 遍历字符串，i 是当前字符的下标，ch 是当前字符
for i, ch in enumerate(s):
if ch == '(':
# 遇到左括号，将其下标压入栈中，等待未来的右括号来匹配
st.append(i)
else:
# 遇到右括号，先检查栈中是否有可以匹配的左括号
# 注意：len(st) > 1 表示栈内除了栈底的边界外，至少有一个左括号下标
if len(st) > 1:
# 栈顶一定是最近的一个未匹配的左括号下标，弹出它，表示这个左括号和当前右括号匹配成功
st.pop()
# 此时栈顶的新元素是：上一个未匹配的位置（要么是边界 -1，要么是上一个未能匹配的右括号位置）
# 当前右括号下标 i 减去这个栈顶下标，就得到当前匹配成功的有效括号子串的长度
# 更新全局最大值
ans = max(ans, i - st[-1])
else:
# 栈中只有栈底的边界（-1）时，说明这个右括号无法匹配任何左括号
# 因此这个右括号成为了“新的无法匹配的右括号”，它会把有效括号子串截断
# 我们将栈底的边界更新为当前右括号的下标，作为后续子串计算的新起点
st[0] = i
return ans
代码其实并不难，就是思路有点会不过来。
总结就是使用栈，栈的栈底始终存放“最后一个无法匹配的右括号位置”，栈顶存放当前等待匹配的左括号位置。
本题还有一个动态规划解法，但是写起来不如栈的解法简单。
不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n] * m
# for i in dp[0]:
# i = 1
for i in range(n):
dp[0][i] = 1
for i in range(m):
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m-1][n-1]
经典二维动态规划，定义状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，注意初始化。
状态转移方程的含义：当前位置的路径数等于当前位置的上方路径数加上当前位置的左方路径数。
最小路径和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
for i in range(1, m):
grid[i][0] = grid[i-1][0] + grid[i][0]
for i in range(1, n):
grid[0][i] = grid[0][i-1] + grid[0][i]
for i in range(1, m):
for j in range(1, n):
grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
基本思路和上一题没什么区别，甚至我们不需要创建一个二维数组，而是直接在原数组上进行操作。
最长回文子串
中心扩展法：
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
ans_left = ans_right = 0 # 维护一个左闭右开区间
# 奇回文串
for i in range(n):
l = r = i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
# 循环结束时,s[l+1]到s[r-1]是回文串
if r - l - 1 > ans_right - ans_left:
ans_left, ans_right = l + 1, r
# 偶回文串
for i in range(n):
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r - l - 1 > ans_right - ans_left:
ans_left, ans_right = l + 1, r
return s[ans_left: ans_right]
分奇偶从中间往两边扩展，找到最长的回文串，解法偏暴力。
动态规划：
形象比喻：“回文就是‘剥洋葱’：两头字符相等，且去掉两头后，中间剩下的也是回文。” DP 做的就是：把每个子串是不是回文的结果记在表格里，短子串的结果用来推导长子串。
dp[i][j] 表示字符串 s[i:j+1] 是否是回文串。
状态转移方程：dp[i][j] = dp[i+1][j-1] and s[i] == s[j]，可以看出更新当前状态有赖于左下角状态。故而可以从下往上，从左往右进行状态转移。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
dp = [[False for _ in range(n)] for _ in range(n)]
result = 1
start = 0
for i in range(n-1, -1, -1):
for j in range(i, n):
if j - i < 2 and s[i] == s[j]:
dp[i][j] = True # 长度1或2，两头相等即为回文
else:
dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
if dp[i][j] and (j - i + 1) > result:
result = j - i + 1
start = i
return s[start:start+result]
注意一下我们是s[i:j+1]，所以只需要考虑dp数组的一部分，即可以看到内存循环中j的范围并不是[0, n-1]，而是[i, n-1]。
由于最后需要输出的是字符串，所以返回s[start:start+result]。我们需要维护一个变量start，记录最长回文串的起始位置。