【Leetcode】随笔

🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：接雨水（LeetCode 42，困难）

题目分析：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。例如：输入height = [0,1,0,2,1,0,1,3,2,1,2,1]，输出6（雨水区域如题目示意图所示，总面积为6）；输入height = [4,2,0,3,2,5]，输出9。

解题思路：

单调栈法（最优解法之一）：利用单调栈维护“递减的柱子高度序列”，当遇到比栈顶高的柱子时，说明栈顶柱子可作为“凹槽底部”，此时弹出栈顶，计算该凹槽能接的雨水量（需找到凹槽左侧的“左边界”和右侧的“右边界”）。
核心原理：

1. 栈存储柱子的索引（通过索引可获取高度和位置，计算宽度），栈内索引对应的高度严格递减；
2. 遍历每个柱子（索引i）：
   • 若栈非空且当前柱子高度height[i] > height[栈顶索引]：
     • 弹出栈顶索引top（凹槽底部）；
     • 若栈为空（无左边界，无法形成凹槽），终止当前计算；
     • 计算凹槽的“左边界”（新栈顶索引left）和“右边界”（当前索引i）；
     • 凹槽高度 = min(height[left], height[i]) - height[top]（取左右边界的最小值，减去底部高度，即雨水深度）；
     • 凹槽宽度 = i - left - 1（左右边界之间的距离，减去1是因为底部已弹出）；
     • 累加雨水量：total += 凹槽高度 * 凹槽宽度；
   • 若当前柱子高度 ≤ 栈顶高度，将当前索引i入栈（维持递减序列）；
3. 遍历结束后，total即为能接的雨水总量。

示例代码：

def trap(height):
    if not height:
        return 0
    
    total = 0
    stack = []  # 存储柱子索引，对应高度严格递减
    n = len(height)
    
    for i in range(n):
        # 遇到比栈顶高的柱子，开始计算凹槽雨水
        while stack and height[i] > height[stack[-1]]:
            # 弹出凹槽底部索引
            top = stack.pop()
            # 无左边界，无法形成凹槽
            if not stack:
                break
            # 计算左边界（新栈顶）和右边界（当前i）
            left = stack[-1]
            # 凹槽高度 = 左右边界最小值 - 底部高度
            trap_height = min(height[left], height[i]) - height[top]
            # 凹槽宽度 = 右边界 - 左边界 - 1
            trap_width = i - left - 1
            # 累加雨水总量
            total += trap_height * trap_width
        # 维持栈的递减序列，入栈当前索引
        stack.append(i)
    
    return total

# 测试示例
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
print("能接的雨水量1：", trap(height1))  # 输出：6

height2 = [4,2,0,3,2,5]
print("能接的雨水量2：", trap(height2))  # 输出：9

代码解析：

单调栈法的核心是“通过递减栈定位凹槽的底部、左边界和右边界”，每个元素仅入栈和出栈一次，时间复杂度O(n)，空间复杂度O(n)（栈的最大存储量为n），是兼顾时间和空间的最优解法。

• 栈存储索引而非高度的原因：需通过索引计算凹槽宽度（左右边界的距离），同时通过索引获取对应高度，一举两得；
• 凹槽计算的关键逻辑：弹出底部后，新栈顶是左边界（比底部高），当前柱子是右边界（比底部高），三者形成“U型凹槽”，雨水深度由左右边界的最小值决定，宽度由两者距离决定；
• 边界处理：栈为空时无左边界，需终止当前计算（如最左侧的递减序列，无法形成凹槽）；
• 对比其他方法：动态规划法（需两次遍历计算左右最大高度，空间O(n)）、双指针法（空间O(1)，但逻辑较抽象），单调栈法更直观地体现了“凹槽积水”的物理过程，易理解和维护。

题目二：正则表达式匹配（LeetCode 10，困难）

题目分析：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。其中：

• '.' 匹配任意单个字符。
• '*' 匹配零个或多个前面的那一个元素。

匹配应该覆盖 整个 字符串 s ，而不是部分字符串。例如：输入s = “aa”, p = “a”，输出false（“a"无法匹配"aa”）；输入s = “aa”, p = “a*”，输出true（“a*“可匹配零个或多个"a”，此处匹配两个"a”）；输入s = “ab”, p = ".“，输出true（”.“可匹配零个或多个任意字符，此处匹配"ab”）。

解题思路：

动态规划法：定义dp[i][j]表示“字符串s的前i个字符”与“模式p的前j个字符”是否匹配，通过分析s[i-1]（当前字符，因索引从0开始）与p[j-1]（当前模式字符）的关系，推导状态转移方程。
核心状态分析：

1. 当p[j-1]是普通字符（非.和*）：
   • 若s[i-1] == p[j-1]（当前字符匹配），则dp[i][j] = dp[i-1][j-1]（依赖前i-1和j-1的匹配结果）；
   • 否则dp[i][j] = false（字符不匹配）。
2. 当p[j-1] == '.'：
   • '.'匹配任意单个字符，因此dp[i][j] = dp[i-1][j-1]（只需前i-1和j-1匹配）。
3. 当p[j-1] == '*'（*需结合前一个字符p[j-2]分析）：
   • 情况1：*匹配零个前一个字符（即忽略p[j-2]和p[j-1]），则dp[i][j] = dp[i][j-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] = 情况1 或 情况2（两种情况满足一种即可）。

初始化条件：

• dp[0][0] = true（空字符串与空模式匹配）；
• dp[0][j]（空字符串与非空模式匹配）：仅当p[j-1] == '*'且dp[0][j-2] = true时为true（如p = "a*b*"，空字符串可匹配）；
• dp[i][0] = false（非空字符串与空模式不匹配）。

示例代码：

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
    
    # 整个s与整个p是否匹配
    return dp[m][n]

# 测试示例
s1, p1 = "aa", "a"
print("{}与{}是否匹配1：".format(s1, p1), isMatch(s1, p1))  # 输出：False

s2, p2 = "aa", "a*"
print("{}与{}是否匹配2：".format(s2, p2), isMatch(s2, p2))  # 输出：True

s3, p3 = "ab", ".*"
print("{}与{}是否匹配3：".format(s3, p3), isMatch(s3, p3))  # 输出：True

s4, p4 = "aab", "c*a*b"
print("{}与{}是否匹配4：".format(s4, p4), isMatch(s4, p4))  # 输出：True（c*匹配0个c，a*匹配2个a，b匹配b）

代码解析：

动态规划法的核心是“将复杂的匹配问题拆解为子问题”，通过状态转移方程覆盖所有匹配场景，尤其是*的“零个或多个”匹配特性，需分情况讨论。

• 索引偏移的原因：dp[i][j]对应前i和j个字符，因此s的第i个字符实际是s[i-1]，p同理，避免处理i=0或j=0时的索引越界；
• *的状态转移是关键：case1对应“不使用*”（如p = "a*"匹配空字符串），case2对应“使用*”（如p = "a*"匹配多个a，依赖前i-1个字符的匹配结果，实现“多匹配”）；
• 边界初始化的必要性：空字符串与*模式的匹配（如p = "a*b*"）需单独处理，否则后续状态转移会出错；
• 时间复杂度：O(m×n)（双重循环遍历m+1行n+1列的dp数组）；空间复杂度：O(m×n)（存储dp数组，可优化为O(n)，因dp[i]仅依赖dp[i-1]和dp[i]的前序状态）；
• 难点突破：*的“回溯性”（可匹配多个字符）通过dp[i-1][j]实现，无需实际回溯，而是通过子问题结果直接推导，效率远高于暴力递归。

题目三：寻找两个正序数组的中位数（LeetCode 4，困难）

题目分析：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (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=2.5）。

解题思路：

二分查找法（基于“分割线”的最优解）：核心是通过二分查找在两个数组中找到一条“分割线”，使得分割线左侧的所有元素 ≤ 分割线右侧的所有元素，且分割线两侧的元素总数相等（或左侧比右侧多1，对应奇数长度），此时中位数可由分割线两侧的元素计算得出。
核心原理（假设m ≤ n，确保二分查找在较短数组上进行，优化效率）：

1. 定义分割线在nums1中的位置为i，在nums2中的位置为j，需满足：
   • i + j = (m + n + 1) // 2（左侧元素总数为(m+n+1)//2，确保左侧比右侧多1，方便取左最大值为中位数）；
   • nums1[i-1] ≤ nums2[j]且nums2[j-1] ≤ nums1[i]（分割线左侧所有元素 ≤ 右侧所有元素）。
2. 二分查找i的范围（0 ≤ i ≤ m）：
   • 初始化left = 0，right = m；
   • 计算i = (left + right) // 2，j = (m + n + 1) // 2 - i；
   • 处理边界情况（i=0表示nums1左侧无元素，i=m表示nums1右侧无元素，同理j）：
     • 左最大值max_left：若i=0则取nums2[j-1]，若j=0则取nums1[i-1]，否则取max(nums1[i-1], nums2[j-1])；
     • 右最小值min_right：若i=m则取nums2[j]，若j=n则取nums1[i]，否则取min(nums1[i], nums2[j])；
   • 判断分割线是否合法：
     • 若nums1[i-1] > nums2[j]（nums1左侧元素过大，需左移分割线）：right = i - 1；
     • 若nums2[j-1] > nums1[i]（nums2左侧元素过大，需右移分割线）：left = i + 1；
     • 否则分割线合法，计算中位数：
       • 若(m + n)为奇数：中位数 = max_left（左侧多1个元素，左最大值即为中位数）；
       • 若(m + n)为偶数：中位数 = (max_left + min_right) / 2。
3. 二分查找结束后，返回计算得到的中位数。

示例代码：

def findMedianSortedArrays(nums1, nums2):
    # 确保nums1是较短数组，优化二分查找效率
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    # 二分查找的范围：nums1 的分割线位置 i
    left, right = 0, m
    # 左侧元素总数：确保奇数时左侧多 1 个
    total_left = (m + n + 1) // 2

    while left <= right:
        # 计算 nums1 的分割线 i，nums2 的分割线 j
        i = (left + right) // 2
        j = total_left - i
        
        # 处理边界情况：i=0 表示 nums1 左侧无元素，用负无穷表示；
        # i=m 表示 nums1 右侧无元素，用正无穷表示
        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 左侧元素过大，左移分割线 i
        elif nums1_left_max > nums2_right_min:
            right = i - 1
        # nums2 左侧元素过大，右移分割线 i
        else:
            left = i + 1
    
    # 理论上不会走到这里（输入均为正序数组，必存在合法分割线）
    raise ValueError("Input arrays are not sorted or invalid")


# 测试示例
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

代码解析：

二分查找法的核心是“通过分割线将两个数组划分为左右两部分，利用正序特性判断分割线合法性”，时间复杂度O(log(min(m,n)))（仅在较短数组上二分），完全满足题目O(log(m+n))的要求，是该题的最优解法。

• 确保m ≤ n的原因：二分查找的次数取决于较短数组的长度，可减少递归/循环次数（如m=3、n=100，仅需log2(3)≈2次查找）；
• 分割线i和j的关系：i + j = (m+n+1)//2是关键，确保左侧元素总数要么等于右侧（偶数），要么比右侧多1（奇数），统一了中位数的计算逻辑；
• 边界值处理（负无穷/正无穷）：当分割线在数组两端时（如i=0表示nums1左侧无元素），用极值替代“不存在的元素”，避免后续max/min计算出错；
• 合法性判断逻辑：nums1_left_max ≤ nums2_right_min和nums2_left_max ≤ nums1_right_min确保分割线左侧所有元素都不大于右侧，符合“中位数两侧有序”的特性；
• 难点突破：将“找中位数”转化为“找合法分割线”，避免了合并数组（O(m+n)时间），通过二分查找将时间复杂度降至对数级，同时边界处理覆盖了所有极端情况（如空数组、单元素数组）。

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍