文章目录
🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨
题目一：编辑距离（LeetCode 72，困难）
题目分析
给你两个单词 word1 和 word2，请计算将 word1 转换成 word2 所使用的最少操作数。允许的操作有三种：
- 插入一个字符；
- 删除一个字符；
- 替换一个字符。
例如：输入word1 = "horse", word2 = "ros"，输出 3（horse→rorse（替换）→rose（删除）→ros（删除），共3步）；输入word1 = "intention", word2 = "execution"，输出 5（5步操作可完成转换）。
解题思路
采用动态规划法，核心是定义 dp[i][j] 表示“将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数”，通过分析字符匹配情况推导状态转移方程：
- 状态定义：
dp[i][j]对应子问题“word1[0..i-1]转word2[0..j-1]的最少操作数”（索引偏移是因为i=0或j=0代表空字符串）。 - 初始化边界：
- 若
i=0（word1为空）：需插入j个字符才能得到word2的前j个字符，故dp[0][j] = j； - 若
j=0（word2为空）：需删除i个字符才能得到空字符串，故dp[i][0] = i。
- 若
- 状态转移逻辑：
- 若
word1[i-1] == word2[j-1]（当前字符匹配）：无需额外操作，dp[i][j] = dp[i-1][j-1]（直接继承前i-1和j-1的最少操作数）； - 若
word1[i-1] != word2[j-1]（当前字符不匹配）：需从三种操作中选最少操作数：- 替换操作：将
word1[i-1]替换为word2[j-1]，操作数dp[i-1][j-1] + 1； - 删除操作：删除
word1[i-1]，操作数dp[i-1][j] + 1； - 插入操作：在
word1[i-1]后插入word2[j-1]，操作数dp[i][j-1] + 1； - 因此
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。
- 替换操作：将
- 若
- 结果获取：
dp[len(word1)][len(word2)]即为最终答案。
示例代码
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# dp[i][j]：word1前i个字符转word2前j个字符的最少操作数
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化边界：i=0（word1空）时，需插入j个字符
for j in range(1, n + 1):
dp[0][j] = j
# 初始化边界：j=0（word2空）时，需删除i个字符
for i in range(1, m + 1):
dp[i][0] = i
# 填充dp数组
for i in range(1, m + 1):
for j in range(1, n + 1):
# 当前字符匹配，无需额外操作
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
# 当前字符不匹配，取三种操作的最小值+1
else:
dp[i][j] = min(
dp[i-1][j-1], # 替换
dp[i-1][j], # 删除
dp[i][j-1] # 插入
) + 1
return dp[m][n]
# 测试示例
word1_1, word2_1 = "horse", "ros"
print("最少操作数1：", minDistance(word1_1, word2_1)) # 输出：3
word1_2, word2_2 = "intention", "execution"
print("最少操作数2：", minDistance(word1_2, word2_2)) # 输出：5
word1_3, word2_3 = "", "a"
print("最少操作数3：", minDistance(word1_3, word2_3)) # 输出：1（插入1个a）
代码解析
- 索引偏移的原因：
dp[i][j]对应“前i/j个字符”，而非“第i/j个字符”，避免处理i=0或j=0时的字符索引越界，同时自然覆盖空字符串的边界情况。 - 三种操作的逻辑对应：
- 替换操作：处理当前字符不匹配，一步替换后继承之前的子问题结果；
- 删除操作：删除
word1的当前字符，相当于用word1前i-1个字符匹配word2前j个字符，加1步删除； - 插入操作：插入
word2的当前字符，相当于用word1前i个字符匹配word2前j-1个字符，加1步插入；
- 复杂度分析：时间复杂度 O(m×n)（双重循环遍历
(m+1)×(n+1)的 dp 数组），空间复杂度 O(m×n)（可优化为 O(min(m,n))，通过滚动数组复用空间，核心逻辑不变）。
题目二：寻找两个正序数组的中位数（LeetCode 4，困难）
题目分析
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，找出并返回这两个正序数组的中位数。要求算法的时间复杂度为 O(log(min(m,n)))。例如：输入 nums1 = [1,3], nums2 = [2]，输出 2.0（合并后 [1,2,3]，中位数为 2）；输入 nums1 = [1,2], nums2 = [3,4]，输出 2.5（合并后 [1,2,3,4]，中位数为 (2+3)/2）。
解题思路
采用二分查找法（分割线思想），核心是通过二分查找在两个数组中找到一条“分割线”，使得分割线左侧所有元素 ≤ 右侧所有元素，且两侧元素总数相等（或左侧多1个，对应奇数长度），此时中位数可由分割线两侧元素计算得出：
- 预处理：确保
nums1是较短数组（m ≤ n），减少二分查找的次数（二分范围为0 ≤ i ≤ m，i是nums1的分割线位置）。 - 分割线定义：设
nums1的分割线为i（左侧有i个元素，右侧有m-i个），nums2的分割线为j（左侧有j个元素，右侧有n-j个），需满足i + j = (m + n + 1) // 2（确保左侧元素总数 ≥ 右侧，奇数时左侧多1个，方便取左最大值为中位数）。 - 二分查找逻辑：
- 初始化
left = 0，right = m； - 计算
i = (left + right) // 2，j = (m + n + 1) // 2 - i； - 定义分割线两侧的关键元素（用正负无穷处理边界，避免数组越界）：
nums1_left_max：nums1分割线左侧最大值（i=0时为-inf，i=m时为nums1[m-1]）；nums1_right_min：nums1分割线右侧最小值（i=0时为nums1[0]，i=m时为+inf）；nums2_left_max：nums2分割线左侧最大值（j=0时为-inf，j=n时为nums2[n-1]）；nums2_right_min：nums2分割线右侧最小值（j=0时为nums2[0]，j=n时为+inf）；
- 判断分割线合法性：
- 若
nums1_left_max > nums2_right_min（nums1左侧元素过大，需左移分割线）：right = i - 1； - 若
nums2_left_max > nums1_right_min（nums2左侧元素过大，需右移分割线）：left = i + 1； - 否则分割线合法，计算中位数：
- 若
(m + n)为奇数：中位数 =max(nums1_left_max, nums2_left_max)（左侧多1个元素，左最大值即为中位数）； - 若
(m + n)为偶数：中位数 =(max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2。
- 若
- 若
- 初始化
- 返回结果：二分查找结束后，返回计算得到的中位数。
示例代码
def findMedianSortedArrays(nums1, nums2):
# 确保nums1是较短数组，减少二分查找范围
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
total_left = (m + n + 1) // 2 # 左侧元素总数（确保奇数时左侧多1）
while left <= right:
# 计算nums1的分割线i，nums2的分割线j
i = (left + right) // 2
j = total_left - i
# 处理边界：用正负无穷表示“无元素”的情况
nums1_left_max = float('-inf') if i == 0 else nums1[i-1]
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_left_max = float('-inf') if j == 0 else nums2[j-1]
nums2_right_min = float('inf') if j == n else nums2[j]
# 分割线合法：左侧所有元素 <= 右侧所有元素
if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
# 判断总长度奇偶性
if (m + n) % 2 == 1:
# 奇数：左侧最大值为中位数
return max(nums1_left_max, nums2_left_max)
else:
# 偶数：(左侧最大值 + 右侧最小值)/2
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0
# nums1左侧元素过大，左移分割线
elif nums1_left_max > nums2_right_min:
right = i - 1
# nums2左侧元素过大，右移分割线
else:
left = i + 1
# 理论上不会走到这里（输入为正序数组，必存在合法分割线）
raise ValueError("Input arrays are not sorted")
# 测试示例
nums1_1, nums2_1 = [1,3], [2]
print("中位数1：", findMedianSortedArrays(nums1_1, nums2_1)) # 输出：2.0
nums1_2, nums2_2 = [1,2], [3,4]
print("中位数2：", findMedianSortedArrays(nums1_2, nums2_2)) # 输出：2.5
nums1_3, nums2_3 = [0,0], [0,0]
print("中位数3：", findMedianSortedArrays(nums1_3, nums2_3)) # 输出：0.0
代码解析
- 确保
m ≤ n的原因：二分查找的次数取决于较短数组的长度（log2(m)），若m > n，交换数组后可减少查找次数，同时避免j计算出现负数（j = total_left - i，i最大为m，total_left = (m+n+1)//2，m ≤ n时j ≥ 0）。 - 边界处理的技巧：用
+inf和-inf替代“分割线在数组两端”的无元素情况，避免额外的条件判断（如i=0时无需单独处理左侧无元素的场景）。 - 时间复杂度优化：O(log(min(m,n)))，完全满足题目要求，相比“合并数组后找中位数”（O(m+n)）效率大幅提升，尤其适合大规模数组。
题目三：正则表达式匹配（LeetCode 10，困难）
题目分析
给你一个字符串 s 和一个字符规律 p，实现支持 '.' 和 '*' 的正则表达式匹配。规则如下：
'.'匹配任意单个字符；'*'匹配零个或多个前面的那一个元素。
匹配需覆盖整个字符串s，而非部分匹配。例如：输入s = "aa", p = "a"，输出false（“a” 无法匹配 “aa”）；输入s = "aa", p = "a*"，输出true（“a*” 匹配两个 “a”）；输入s = "ab", p = ".*"，输出true（“.*” 匹配任意字符的任意次数）。
解题思路
采用动态规划法，核心是定义 dp[i][j] 表示“s 的前 i 个字符与 p 的前 j 个字符是否匹配”，通过分析 p[j-1]（当前模式字符）的类型推导状态转移方程：
- 状态定义：
dp[i][j]对应子问题“s[0..i-1]与p[0..j-1]是否匹配”（索引偏移原因同前，覆盖空字符串场景）。 - 初始化边界：
dp[0][0] = true（空字符串与空模式匹配）；dp[i][0] = false（非空字符串与空模式不匹配，i ≥ 1）；dp[0][j]（空字符串与非空模式匹配）：仅当p[j-1] == '*'且dp[0][j-2] = true时为true（如p = "a*b*"，*匹配零个前序字符）。
- 状态转移逻辑：
- 情况1：
p[j-1]是普通字符或'.'：- 若
s[i-1] == p[j-1]或p[j-1] == '.'（当前字符匹配），则dp[i][j] = dp[i-1][j-1]（继承前i-1和j-1的匹配结果）； - 否则
dp[i][j] = false（字符不匹配）。
- 若
- 情况2：
p[j-1] == '*'（*需结合前一个字符p[j-2]分析）：- 子情况2.1：
*匹配零个前序字符（忽略p[j-2]和p[j-1]），则dp[i][j] = dp[i][j-2]； - 子情况2.2：
*匹配一个或多个前序字符（需s[i-1]与p[j-2]匹配）：- 若
s[i-1] == p[j-2]或p[j-2] == '.'（当前字符与*前的字符匹配），则dp[i][j] = dp[i-1][j]（s的前i-1个字符已与p的前j个字符匹配，新增s[i-1]仍可被*覆盖）；
- 若
- 最终
dp[i][j] = 子情况2.1 或 子情况2.2（两种情况满足一种即可匹配）。
- 子情况2.1：
- 情况1：
- 结果获取：
dp[len(s)][len(p)]即为s与p是否完全匹配的结果。
示例代码
def isMatch(s: str, p: str) -> bool:
m, n = len(s), len(p)
# dp[i][j]：s前i个字符与p前j个字符是否匹配
dp = [[False] * (n + 1) for _ in range(m + 1)]
# 初始化：空字符串与空模式匹配
dp[0][0] = True
# 初始化：空字符串与非空模式的匹配情况（处理*）
for j in range(1, n + 1):
if p[j-1] == '*':
# *匹配零个前序字符，依赖p前j-2个字符的匹配结果
dp[0][j] = dp[0][j-2]
# 填充dp数组
for i in range(1, m + 1):
for j in range(1, n + 1):
# 情况1：p当前字符是普通字符或.
if p[j-1] != '*':
# 当前字符匹配（普通字符相等或.匹配任意字符）
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
# 不匹配则保持默认False
# 情况2：p当前字符是*，需结合前一个字符分析
else:
# 子情况2.1：*匹配零个前序字符（忽略p[j-2]和*）
case1 = dp[i][j-2]
# 子情况2.2：*匹配一个或多个前序字符（需s[i-1]与p[j-2]匹配）
case2 = False
if s[i-1] == p[j-2] or p[j-2] == '.':
case2 = dp[i-1][j]
# 两种情况满足一种即可
dp[i][j] = case1 or case2
return dp[m][n]
# 测试示例
s1, p1 = "aa", "a"
print(f"{s1} 与 {p1} 是否匹配：", isMatch(s1, p1)) # 输出：False
s2, p2 = "aa", "a*"
print(f"{s2} 与 {p2} 是否匹配：", isMatch(s2, p2)) # 输出：True
s3, p3 = "ab", ".*"
print(f"{s3} 与 {p3} 是否匹配：", isMatch(s3, p3)) # 输出：True
s4, p4 = "aab", "c*a*b"
print(f"{s4} 与 {p4} 是否匹配：", isMatch(s4, p4)) # 输出：True（c*匹配0个c，a*匹配2个a）
s5, p5 = "mississippi", "mis*is*p*."
print(f"{s5} 与 {p5} 是否匹配：", isMatch(s5, p5)) # 输出：False（最后p的.无法匹配s的i）
代码解析
- 索引偏移的必要性：
dp[i][j]对应“前i/j个字符”，而非“第i/j个字符”，既避免了i=0或j=0时的字符索引越界，又能自然处理“空字符串与空模式匹配”“空字符串与含*模式匹配”等边界场景。 *的状态转移核心：case1对应“不使用*”（如p="a*"匹配空字符串，直接继承dp[i][j-2]的结果）；case2对应“使用*”（如p="a*"匹配多个a，通过dp[i-1][j]实现“多字符覆盖”——只要前i-1个字符能匹配，新增的s[i-1]仍可被*覆盖）；
- 边界初始化的细节：空字符串与非空模式匹配的初始化（
dp[0][j]），仅当p[j-1]是*时才可能为True，且需依赖dp[0][j-2]（跳过*和其前序字符），否则均为False。 - 复杂度分析：时间复杂度 O(m×n)（双重循环遍历
(m+1)×(n+1)的 dp 数组），空间复杂度 O(m×n)（可优化为 O(n)，通过滚动数组复用空间，因dp[i]仅依赖dp[i-1]和dp[i]的前序状态）。
🏠 更多算法解析和实战技巧，欢迎到我的CSDN主页交流：山顶风景独好😍