【Leetcode】随笔

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

题目一：二叉树的序列化与反序列化（LeetCode 297，困难）

题目分析

序列化是将数据结构或对象转换为可存储/传输的格式，反序列化则是将其重构为原结构。要求设计算法实现二叉树的序列化与反序列化，确保序列化后的字符串能准确还原为原二叉树。例如：输入二叉树 [1,2,3,null,null,4,5]，序列化可得到 "1,2,null,null,3,4,null,null,5,null,null"，反序列化后需还原为该二叉树；输入空树，输出空字符串。

解题思路

采用深度优先搜索（前序遍历），因前序遍历先访问根节点，便于反序列化时从字符串开头定位根节点，递归处理左右子树。具体步骤如下：

1. 序列化（serialize）：
   • 递归终止：若节点为空，添加 "null" 标记；
   • 前序遍历：先记录当前节点值，再递归序列化左、右子树；
   • 结果处理：用逗号拼接所有记录，形成序列化字符串。
2. 反序列化（deserialize）：
   • 预处理：将序列化字符串按逗号拆分，转为队列（保证顺序读取）；
   • 递归构建：从队列头部取元素，非 "null" 则创建节点，递归构建左、右子树（遵循前序顺序）；
   • 返回根节点：递归结束后得到重构的二叉树。

示例代码

from collections import deque

# 二叉树节点定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string."""
        def dfs(node):
            if not node:
                res.append("null")
                return
            res.append(str(node.val))  # 记录根节点
            dfs(node.left)             # 递归左子树
            dfs(node.right)            # 递归右子树
        
        res = []
        dfs(root)
        return ",".join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree."""
        def build():
            val = queue.popleft()
            if val == "null":
                return None
            node = TreeNode(int(val))  # 构建根节点
            node.left = build()        # 递归构建左子树
            node.right = build()       # 递归构建右子树
            return node
        
        queue = deque(data.split(","))
        return build()

# 测试示例
# 构建二叉树 [1,2,3,null,null,4,5]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

codec = Codec()
serialized = codec.serialize(root)
print("序列化结果：", serialized)  # 输出：1,2,null,null,3,4,null,null,5,null,null
deserialized = codec.deserialize(serialized)

# 验证：前序遍历反序列化后的树
def preorder(node):
    return [node.val] + preorder(node.left) + preorder(node.right) if node else []
print("反序列化前序遍历：", preorder(deserialized))  # 输出：[1,2,3,4,5]

代码解析

• 标记空节点的必要性：用 "null" 标记空节点，确保反序列化时能准确识别树的层级结构，避免丢失叶子节点的左右子树信息（如叶子节点的左右均为 "null"）。
• 队列的作用：反序列化时将字符串转为队列，保证按前序顺序依次读取节点值，递归构建时自然匹配“根→左→右”的顺序，与序列化逻辑完全对应。
• 复杂度分析：时间复杂度 O(n)（序列化和反序列化均遍历所有节点一次）；空间复杂度 O(n)（递归栈深度最坏为 n，队列存储节点值需 O(n) 空间）。

题目二：最长有效括号（LeetCode 32，困难）

题目分析

给定只含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）的括号子串长度。例如：输入 s = "(()"，输出 2（最长子串 "()"）；输入 s = ")()())"，输出 4（最长子串 "()()"）；输入 s = ""，输出 0。

解题思路

采用动态规划法，定义 dp[i] 表示“以 s[i] 结尾的最长有效括号子串长度”，通过分析 s[i] 与前序字符的关系推导状态转移方程：

1. 状态定义：dp[i] 对应子问题“以第 i 个字符结尾的最长有效括号长度”，字符串索引从 0 开始。
2. 边界初始化：dp[0] = 0（单个字符无法构成有效括号），空字符串 dp 为空。
3. 状态转移（遍历 i 从 1 开始）：
   • 若 s[i] == '('：以 '(' 结尾的子串无效，dp[i] = 0；
   • 若 s[i] == ')'：
     • 子情况 1：s[i-1] == '('（当前与前一个构成括号）：dp[i] = dp[i-2] + 2（i≥2）或 2（i=1）；
     • 子情况 2：s[i-1] == ')'（当前与前一个均为 ')'）：若 i - dp[i-1] - 1 ≥ 0 且 s[i - dp[i-1] - 1] == '('，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（i - dp[i-1] - 2 ≥ 0）或 dp[i-1] + 2。
4. 结果：dp 数组的最大值即为最长有效括号长度。

示例代码

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * n
    max_len = 0
    
    for i in range(1, n):
        if s[i] == ')':
            # 情况1：当前')'与前一个'('配对
            if s[i-1] == '(':
                dp[i] = dp[i-2] + 2 if i >= 2 else 2
            # 情况2：当前')'与前一个')'配对，检查更前的'('
            else:
                prev = i - dp[i-1] - 1
                if prev >= 0 and s[prev] == '(':
                    dp[i] = dp[i-1] + 2 + (dp[prev-1] if prev >= 1 else 0)
        if dp[i] > max_len:
            max_len = dp[i]
    return max_len

# 测试示例
s1 = "(()"
print("最长有效括号1：", longestValidParentheses(s1))  # 输出：2

s2 = ")()())"
print("最长有效括号2：", longestValidParentheses(s2))  # 输出：4

s3 = "()(())"
print("最长有效括号3：", longestValidParentheses(s3))  # 输出：6

代码解析

• 状态转移的核心：针对 s[i] == ')' 的两种场景，分别处理相邻配对和间隔配对的情况。例如 s = "()(())" 中，i=5（最后一个 ')'）时，dp[4] = 2，prev = 5-2-1=2，s[2] = '('，故 dp[5] = 2+2+dp[1] = 6，准确计算出最长子串长度。
• 边界处理：计算时需判断索引是否越界（如 i-2 ≥ 0、prev ≥ 0），避免访问无效数组元素。
• 复杂度分析：时间复杂度 O(n)（仅遍历字符串一次）；空间复杂度 O(n)（dp 数组长度为 n），可优化为 O(1) 空间，但动态规划解法更直观。

题目三：跳跃游戏 II（LeetCode 45，困难）

题目分析

给定非负整数数组 nums，初始位于第一个位置，每个元素表示该位置最大跳跃长度，目标是用最少跳跃次数到达最后一个位置（假设必能到达）。例如：输入 nums = [2,3,1,1,4]，输出 2（路径 0→1→4）；输入 nums = [1,1,1,1]，输出 3；输入 nums = [10,9,8,...,0]，输出 1。

解题思路

采用贪心算法，核心是“每次跳跃选择能到达的最远范围”，通过记录关键边界实现最少跳跃：

1. 变量定义：
   • jump_count：已跳跃次数（初始 0）；
   • current_end：当前跳跃的最远边界（初始 0）；
   • farthest：下一次跳跃能到达的最远位置（初始 0）。
2. 遍历数组（到倒数第二个元素，因最后一个是终点）：
   • 更新 farthest = max(farthest, i + nums[i])（当前位置能到达的最远点）；
   • 若 i == current_end（到达当前跳跃边界）：
     • 跳跃次数 +1；
     • 更新 current_end = farthest（下一次跳跃边界）；
     • 若 current_end ≥ 终点，提前结束循环。
3. 返回结果：jump_count 即为最少跳跃次数。

示例代码

def jump(nums) -> int:
    n = len(nums)
    if n == 1:
        return 0
    jump_count = 0
    current_end = 0
    farthest = 0
    
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        # 到达当前跳跃边界，必须跳一次
        if i == current_end:
            jump_count += 1
            current_end = farthest
            if current_end >= n - 1:
                break
    return jump_count

# 测试示例
nums1 = [2,3,1,1,4]
print("最少跳跃次数1：", jump(nums1))  # 输出：2

nums2 = [2,3,0,1,4]
print("最少跳跃次数2：", jump(nums2))  # 输出：2

nums3 = [1,1,1,1]
print("最少跳跃次数3：", jump(nums3))  # 输出：3

代码解析

• 贪心策略的体现：每次跳跃都以“当前能到达的最远范围”为目标，确保覆盖最大区域。例如 nums = [2,3,1,1,4] 中，第一次跳跃边界是 0-2，其中位置 1 能到达 4，故 farthest=4，到达边界 2 时跳跃次数+1，此时 current_end=4 已达终点，总跳跃 2 次。
• 遍历终止条件：到倒数第二个元素停止，因到达最后一个元素即完成目标，避免多算一次跳跃。
• 复杂度分析：时间复杂度 O(n)（遍历数组一次）；空间复杂度 O(1)（仅用常数变量），是最优解法。

✨ 本次分享的3道题覆盖“DFS（二叉树序列化）”“动态规划（最长有效括号）”“贪心（跳跃游戏）”，核心是根据问题特性选择合适算法。若对某题的优化思路、拓展场景有疑问，或想了解其他困难题，随时告诉我！😊
🏠 更多算法解析欢迎到CSDN主页交流：山顶风景独好😍