文章目录
🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨
题目一：正则表达式匹配（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]是否完全匹配”（索引偏移是因为i=0或j=0代表空字符串，便于处理边界）。 - 初始化边界：
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]分析，代表“零个或多个p[j-2]”）：- 子情况2.1：
*匹配零个p[j-2]（忽略p[j-2]和p[j-1]），则dp[i][j] = dp[i][j-2]； - 子情况2.2：
*匹配一个或多个p[j-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匹配，新增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时的字符索引越界，又能自然处理“空字符串与含*模式匹配”的边界场景（如p="a*"匹配空字符串）。 *的状态转移核心：case1对应“不使用*”，直接跳过*和其前序字符，继承dp[i][j-2]的结果；case2对应“使用*”，通过dp[i-1][j]实现“多字符覆盖”——只要前i-1个字符能匹配，新增的s[i-1]仍可被*覆盖，无需回溯。
- 边界初始化细节：空字符串与非空模式匹配时，仅当
p[j-1]是*且前j-2个模式能匹配空字符串，才为True，否则均为False（如p="a*b"无法匹配空字符串，因b无法被忽略）。 - 复杂度分析：时间复杂度 O(m×n)（双重循环遍历
(m+1)×(n+1)的 dp 数组）；空间复杂度 O(m×n)（可优化为 O(n)，通过滚动数组复用空间，因dp[i]仅依赖dp[i-1]和dp[i]的前序状态）。
题目二：二叉树中的最大路径和（LeetCode 124，困难）
题目分析
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列（同一个节点至多出现一次）。路径和是路径中各节点值的总和。给你二叉树的根节点 root，返回其最大路径和。例如：输入根节点为 [1,2,3]（根 1，左子 2，右子 3），输出 6（路径 2→1→3，和为 6）；输入根节点为 [-10,9,20,null,null,15,7]，输出 42（路径 15→20→7，和为 42）；输入根节点为 [-3]，输出 -3（仅单个节点，路径和为节点值）。
解题思路
采用后序遍历（递归），核心是定义“节点贡献”——以当前节点为起点，向下延伸的最大路径和（路径只能向子节点延伸，不能分叉），通过递归计算每个节点的左右子树贡献，结合当前节点值更新全局最大路径和。具体步骤如下：
- 核心概念：
- 节点贡献：以当前节点为起点，向下延伸到任意叶子节点的路径中，最大的路径和（若子树贡献为负，可选择不包含该子树，贡献取 0）；
- 全局最大路径和：可能是“以当前节点为中心，连接左右子树的路径和”（左右子树贡献 + 当前节点值），也可能是递归过程中已记录的最大和，需实时比较更新。
- 递归函数设计：
- 函数
max_contribution(node)：返回以node为起点的最大贡献值。 - 终止条件：若
node为None，返回 0（空节点贡献为 0）。 - 递归计算：
- 计算左子树贡献
left_contrib = max(max_contribution(node.left), 0)（负贡献取 0，相当于不选左子树）； - 计算右子树贡献
right_contrib = max(max_contribution(node.right), 0)（同理处理负贡献）； - 计算“以当前节点为中心的路径和”
current_path_sum = node.val + left_contrib + right_contrib，若该值大于全局最大和max_sum，则更新max_sum； - 返回当前节点的最大贡献
node.val + max(left_contrib, right_contrib)（路径只能选左或右子树中的一条，避免分叉，供父节点使用）。
- 计算左子树贡献
- 函数
- 初始化与执行：
- 初始化全局变量
max_sum为负无穷（处理树中所有节点值为负的情况）； - 调用
max_contribution(root)，触发后序遍历； - 递归结束后，
max_sum即为二叉树的最大路径和。
- 初始化全局变量
示例代码
# 二叉树节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
# 全局变量：存储最大路径和（初始为负无穷，处理全负节点）
self.max_sum = float('-inf')
def max_contribution(node):
if not node:
return 0 # 空节点贡献为0
# 计算左右子树的最大贡献，负贡献取0（不选该子树）
left_contrib = max(max_contribution(node.left), 0)
right_contrib = max(max_contribution(node.right), 0)
# 计算以当前节点为中心的路径和，更新全局最大路径和
current_path_sum = node.val + left_contrib + right_contrib
if current_path_sum > self.max_sum:
self.max_sum = current_path_sum
# 返回当前节点的最大贡献（只能选左或右子树中的一条路径）
return node.val + max(left_contrib, right_contrib)
# 触发递归，计算所有节点的贡献
max_contribution(root)
return self.max_sum
# 测试示例
# 示例1：root = [1,2,3]
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
print("最大路径和1：", Solution().maxPathSum(root1)) # 输出：6
# 示例2：root = [-10,9,20,null,null,15,7]
root2 = TreeNode(-10)
root2.left = TreeNode(9)
root2.right = TreeNode(20)
root2.right.left = TreeNode(15)
root2.right.right = TreeNode(7)
print("最大路径和2：", Solution().maxPathSum(root2)) # 输出：42
# 示例3：root = [-3]（单个负节点）
root3 = TreeNode(-3)
print("最大路径和3：", Solution().maxPathSum(root3)) # 输出：-3
# 示例4：root = [2,-1]（包含负子树）
root4 = TreeNode(2)
root4.left = TreeNode(-1)
print("最大路径和4：", Solution().maxPathSum(root4)) # 输出：2（选根节点，不选左子树）
代码解析
- 负贡献处理：递归计算左右子树贡献时，用
max(contrib, 0)过滤负贡献，避免负数值拉低路径和（例如左子树贡献为 -5，选择左子树会让路径和更小，故取 0，即不选左子树）。 - 路径和的两种场景：
- “以当前节点为中心的路径”：包含左右子树，是一条完整的独立路径，需更新全局最大和；
- “当前节点的贡献”：仅包含左或右子树，是父节点路径的一部分，需返回给父节点使用（若返回包含左右子树的路径，会导致父节点路径分叉，不符合路径定义）。
- 时间复杂度：O(n)（
n为二叉树节点数，每个节点仅被访问一次，后序遍历）；空间复杂度：O(h)（h为二叉树高度，递归栈深度为h，最坏情况为 O(n)，如斜树）。
题目三：最长递增子序列（LeetCode 300，困难）
题目分析
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如：输入 nums = [10,9,2,5,3,7,101,18]，输出 4（最长递增子序列为 [2,3,7,101] 或 [2,5,7,101]）；输入 nums = [0,1,0,3,2,3]，输出 4；输入 nums = [7,7,7,7,7,7,7]，输出 1（严格递增，子序列长度为 1）。
解题思路
采用动态规划+二分查找（最优解法），核心是维护一个“递增序列”tails，通过二分查找优化动态规划的时间复杂度。具体步骤如下：
- 辅助数组定义：
tails[i]表示“长度为i+1的最长递增子序列（LIS）的最小末尾元素”。例如tails = [2,3,7]表示：长度为 1 的 LIS 最小末尾是 2，长度为 2 的 LIS 最小末尾是 3，长度为 3 的 LIS 最小末尾是 7。末尾元素越小，后续越容易拼接更长的子序列。 - 遍历数组：依次遍历
nums中的每个元素x，根据x与tails的关系处理：- 若
x > tails[-1]（x大于tails最后一个元素）：x可接在当前最长 LIS 后，形成更长的子序列，将x追加到tails末尾，LIS 长度加 1。 - 否则（
x不大于tails最后一个元素）：在tails中找到第一个大于等于x的元素，用x替换该元素——目的是让“对应长度的 LIS 末尾元素更小”，为后续元素留出更多拼接空间（例如tails = [2,5]，遇到x=3时，替换为[2,3]，后续遇到4可直接追加为[2,3,4]）。
- 若
- 返回结果：
tails数组的长度即为最长递增子序列的长度（tails的长度始终等于当前 LIS 的长度，但其元素不一定是实际的 LIS，仅用于记录“最小末尾元素”）。
示例代码
import bisect
def lengthOfLIS(nums):
if not nums:
return 0
tails = [] # tails[i]：长度为i+1的LIS的最小末尾元素
for x in nums:
# 用bisect_left找到tails中第一个 >= x的元素索引
idx = bisect.bisect_left(tails, x)
if idx == len(tails):
# x比tails所有元素大，追加到末尾，LIS长度+1
tails.append(x)
else:
# 用x替换该元素，让对应长度的LIS末尾元素更小
tails[idx] = x
# tails的长度即为最长递增子序列的长度
return len(tails)
# 测试示例
nums1 = [10,9,2,5,3,7,101,18]
print("最长递增子序列长度1：", lengthOfLIS(nums1)) # 输出：4
nums2 = [0,1,0,3,2,3]
print("最长递增子序列长度2：", lengthOfLIS(nums2)) # 输出：4
nums3 = [7,7,7,7,7,7,7]
print("最长递增子序列长度3：", lengthOfLIS(nums3)) # 输出：1
nums4 = [4,10,4,3,8,9]
print("最长递增子序列长度4：", lengthOfLIS(nums4)) # 输出：3（如[4,8,9]或[3,8,9]）
nums5 = [1,3,6,7,9,4,10,5,6]
print("最长递增子序列长度5：", lengthOfLIS(nums5)) # 输出：6（如[1,3,6,7,9,10]）
代码解析
tails数组的意义：tails并非实际的最长递增子序列，而是“长度对应”的最小末尾元素集合。例如nums = [10,9,2,5,3,7]，遍历过程中tails变化为：[10]→[9]→[2]→[2,5]→[2,3]→[2,3,7]，最终长度 3 即为 LIS 长度，且每个元素都是对应长度的最小末尾，确保后续元素能更易拼接。- 二分查找的作用：
bisect_left函数在tails中快速定位“第一个 >= x 的元素”，时间复杂度 O(log k)（k为当前tails长度），替代传统动态规划的 O(n) 遍历，将整体时间复杂度从 O(n²) 降至 O(n log n)，大幅提升效率。 - 替换逻辑的必要性：当
x不大于tails[-1]时，替换“第一个 >= x 的元素”，能让对应长度的 LIS 末尾元素更小。例如tails = [2,5]遇到x=3，替换为[2,3]，后续若遇到4可直接追加为[2,3,4]，而原[2,5]无法接4，体现“最小末尾”的优势。 - 复杂度分析：时间复杂度 O(n log n)（遍历数组 O(n)，每次二分查找 O(log k)，
k最大为 n）；空间复杂度 O(n)（tails数组最大长度为 n，如数组严格递增时），是该题的最优解法。
✨ 本次分享的3道题分别聚焦“动态规划（正则匹配）”“二叉树递归（最大路径和）”“动态规划+二分（最长递增子序列）”，这类题型的核心在于“拆解子问题+选择合适的优化工具”。如果对某类算法的细节（如二分查找的应用场景、递归的终止条件设计）或其他困难题类型有进一步需求，随时告诉我哦！😊
🏠 更多算法解析和实战技巧，欢迎到我的CSDN主页交流：山顶风景独好😍