【Leetcode】随笔

文章目录

• • 题目一：K 个一组翻转链表（LeetCode 25，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析
  • 题目二：最小覆盖子串（LeetCode 76，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析
  • 题目三：最长有效括号（LeetCode 32，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析

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

题目一：K 个一组翻转链表（LeetCode 25，困难）

题目分析

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
例如：输入 head = [1,2,3,4,5], k = 2，输出 [2,1,4,3,5]（前2个节点翻转，后2个节点翻转，最后1个节点保持不变）；输入 head = [1,2,3,4,5], k = 3，输出 [3,2,1,4,5]（前3个节点翻转，最后2个节点保持不变）。
要求：不能只是单纯改变节点内部的值，而是需要实际进行节点交换；进阶：空间复杂度 O(1)（只能使用常数额外空间）。

解题思路

采用迭代法（模拟翻转+拼接），核心是“分组处理→局部翻转→首尾拼接”，通过精准的指针管理避免节点丢失，同时满足空间复杂度要求：

1. 预处理（虚拟头节点）：创建虚拟头节点 dummy 并让 dummy.next = head，统一处理“第一组翻转”与后续组翻转的拼接逻辑，避免单独处理头节点的边界问题；定义 prev_group_tail = dummy，用于记录上一组的尾节点（初始时为虚拟头）。
2. 分组判断与定位：遍历链表时，先检查当前剩余节点是否足够 k 个（不足则直接返回结果），同时记录当前组的头节点 curr_group_head 和下一组的头节点 next_group_head（为后续拼接做准备）。
3. 局部翻转当前组：用双指针 prev（前驱节点，初始为 None）和 curr（当前节点，初始为 curr_group_head），循环 k 次翻转节点指向——每次暂存 curr.next 避免丢失后续节点，再将 curr.next 指向 prev，最后更新 prev 和 curr 指针，完成组内节点翻转。翻转后，prev 成为当前组的新头节点，curr_group_head 成为当前组的新尾节点。
4. 组间拼接：让上一组的尾节点 prev_group_tail.next 指向当前组的新头 prev，再将 prev_group_tail 更新为当前组的新尾 curr_group_head，最后让当前组的新尾指向 next_group_head，确保链表连贯。
5. 循环终止与返回：重复上述步骤，直至剩余节点不足 k 个，最终返回 dummy.next（新链表的头节点）。

示例代码

# 链表节点定义class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextdef reverseKGroup(head: ListNode, k: int) -> ListNode: # 虚拟头节点：简化头节点翻转的边界处理 dummy = ListNode(0) dummy.next = head # prev_group_tail：上一组的尾节点，初始为虚拟头 prev_group_tail = dummy while True: # 步骤1：检查剩余节点是否足够k个，同时定位下一组头节点 curr = prev_group_tail.next # 当前组的初始头节点 next_group_head = curr # 下一组头节点（初始假设为当前组头） count = 0  # 计数：当前剩余节点数 # 移动count次，确认剩余节点数并找到下一组头 while count < k and next_group_head: next_group_head = next_group_head.next count += 1 # 剩余节点不足k个，终止循环 if count < k: break # 步骤2：翻转当前组（共k个节点） curr_group_head = curr # 翻转前的头节点（翻转后成为尾节点） prev = None # 翻转时的前驱节点 for _ in range(k): # 暂存当前节点的下一个节点，避免翻转后丢失 next_node = curr.next # 翻转当前节点的指向 curr.next = prev # 更新前驱和当前节点，准备处理下一个 prev, curr = curr, next_node # 步骤3：拼接上一组、当前组、下一组 prev_group_tail.next = prev # 上一组尾 → 当前组新头 prev_group_tail = curr_group_head # 更新上一组尾为当前组新尾 prev_group_tail.next = next_group_head # 当前组尾 → 下一组头 return dummy.next# 辅助函数：链表转列表（测试用，便于查看结果）def linkedlist_to_list(head): res = [] while head: res.append(head.val) head = head.next return res# 辅助函数：列表转链表（测试用，便于构建输入）def list_to_linkedlist(arr): if not arr: return None head = ListNode(arr[0]) curr = head for val in arr[1:]: curr.next = ListNode(val) curr = curr.next return head# 测试示例arr1 = [1,2,3,4,5]k1 = 2head1 = list_to_linkedlist(arr1)reversed_head1 = reverseKGroup(head1, k1)print(\"k={}时翻转结果1：\".format(k1), linkedlist_to_list(reversed_head1)) # 输出：[2,1,4,3,5]arr2 = [1,2,3,4,5]k2 = 3head2 = list_to_linkedlist(arr2)reversed_head2 = reverseKGroup(head2, k2)print(\"k={}时翻转结果2：\".format(k2), linkedlist_to_list(reversed_head2)) # 输出：[3,2,1,4,5]

代码解析

• 虚拟头节点的价值：无需单独判断“第一组翻转后是否需要修改头节点”，统一所有组的拼接逻辑，让代码更简洁。
• 分组判断的必要性：提前确认剩余节点数量，避免对不足 k 个的节点进行无效翻转，同时定位 next_group_head 减少后续遍历，提升效率。
• 局部翻转的关键：通过 prev 和 curr 双指针配合暂存 next_node，确保每个节点的指向翻转后不丢失后续节点，循环 k 次精准控制翻转范围。
• 空间与时间复杂度：空间复杂度 O(1)（仅用常数个指针变量），满足进阶要求；时间复杂度 O(n)（每个节点仅被访问 2 次：一次分组判断，一次翻转），效率最优。

题目二：最小覆盖子串（LeetCode 76，困难）

题目分析

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 \"\" 。
例如：输入 s = \"ADOBECODEBANC\", t = \"ABC\"，输出 \"BANC\"（或\"BCA\"，最小子串长度为3）；输入 s = \"a\", t = \"a\"，输出 \"a\"；输入 s = \"a\", t = \"aa\"，输出 \"\"（s 中只有1个 a，无法覆盖 t 的2个 a）。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

解题思路

采用滑动窗口法（双指针+哈希表），核心是“扩展窗口满足覆盖要求，收缩窗口寻找最小长度”，通过哈希表跟踪字符频率，高效判断窗口有效性：

1. 哈希表预处理：
   • target_freq：记录 t 中各字符的频率（明确需要覆盖的目标）；
   • window_freq：记录当前滑动窗口内各字符的频率（实时跟踪窗口状态）；
   • need：t 中不同字符的数量（需满足“窗口内该字符频率≥target_freq”的字符总数）；
   • valid：当前窗口中已满足“频率≥target_freq”的字符数量（valid == need 时，窗口完全覆盖 t）。
2. 窗口初始化：左指针 left = 0，右指针 right = 0；start 记录最小子串的起始索引，min_len 记录最小子串长度（初始为无穷大，用于后续比较更新）。
3. 扩展窗口（右指针移动）：
   • 取当前右指针指向的字符 c = s[right]，若 c 在 target_freq 中，更新 window_freq[c]（加1）；
   • 若 window_freq[c] == target_freq[c]，说明该字符已满足覆盖要求，valid 加1；
   • 右指针 right += 1，扩大窗口范围。
4. 收缩窗口（窗口有效时，左指针移动）：当 valid == need 时，窗口已覆盖 t，此时尝试收缩左指针减小窗口：
   • 计算当前窗口长度 current_len = right - left，若 current_len < min_len，更新 min_len = current_len 和 start = left（记录最小子串的位置）；
   • 取左指针指向的字符 d = s[left]，若 d 在 target_freq 中：
     • 若 window_freq[d] == target_freq[d]，说明收缩后该字符将不满足覆盖要求，valid 减1；
     • 更新 window_freq[d]（减1）；
   • 左指针 left += 1，缩小窗口范围。
5. 结果处理：遍历结束后，若 min_len 仍为无穷大，说明无有效子串，返回 \"\"；否则返回 s[start:start+min_len]。

示例代码

from collections import defaultdictdef minWindow(s: str, t: str) -> str: # 目标字符频率表：记录t中各字符需要的数量 target_freq = defaultdict(int) for c in t: target_freq[c] += 1 # 当前窗口字符频率表：记录窗口内各字符的数量 window_freq = defaultdict(int) need = len(target_freq) # 需要满足的不同字符总数 valid = 0 # 已满足频率要求的字符数 left = 0  # 窗口左边界 start = 0 # 最小子串的起始索引 min_len = float(\'inf\') # 最小子串的长度（初始设为无穷大） # 扩展窗口：移动右边界 for right in range(len(s)): c = s[right] # 若当前字符是目标字符，更新窗口频率 if c in target_freq: window_freq[c] += 1 # 当窗口内该字符数量达到目标数量时，满足度+1 if window_freq[c] == target_freq[c]: valid += 1 # 窗口已完全覆盖t，开始收缩左边界寻找最小子串 while valid == need: # 1. 更新最小子串的信息 current_len = right - left if current_len < min_len: min_len = current_len start = left # 2. 收缩左边界：处理左边界字符 d = s[left] if d in target_freq: # 若该字符当前刚好满足目标数量，收缩后将不满足，需减少满足度 if window_freq[d] == target_freq[d]:  valid -= 1 # 减少窗口内该字符的数量 window_freq[d] -= 1 # 3. 左边界右移，缩小窗口 left += 1 # 判断是否找到有效子串 return \"\" if min_len == float(\'inf\') else s[start:start + min_len]# 测试示例s1 = \"ADOBECODEBANC\"t1 = \"ABC\"print(\"最小覆盖子串1：\", minWindow(s1, t1)) # 输出：\"BANC\"s2 = \"a\"t2 = \"a\"print(\"最小覆盖子串2：\", minWindow(s2, t2)) # 输出：\"a\"s3 = \"a\"t3 = \"aa\"print(\"最小覆盖子串3：\", minWindow(s3, t3)) # 输出：\"\"

代码解析

• 哈希表的核心作用：target_freq 明确覆盖目标，window_freq 实时反馈窗口状态，valid 和 need 配合快速判断窗口是否有效，避免每次遍历 target_freq 检查，大幅提升效率。
• 窗口收缩的时机：仅当窗口有效时收缩，确保每次收缩都是在“满足覆盖要求”的前提下寻找更小窗口，避免无效操作。
• 边界处理细节：对非 t 中的字符，无需记录其频率（不影响覆盖结果）；收缩左边界时，仅当字符频率刚好等于目标频率时才减少 valid，避免重复调整（例如窗口内字符频率远超目标时，收缩一次仍满足要求）。
• 复杂度分析：时间复杂度 O(n + m)（n 为 s 长度，m 为 t 长度，预处理 t 为 O(m)，滑动窗口遍历 s 为 O(n)）；空间复杂度 O(k)（k 为 t 中不同字符的数量，哈希表存储量不超过 k）。

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

题目分析

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

解题思路

采用动态规划法，核心是定义 dp[i] 为“以 s[i] 结尾的最长有效括号子串的长度”，通过分析 s[i] 与前序字符的关系，推导状态转移方程，避免暴力遍历所有子串：

1. 状态定义：dp[i] 表示以字符串 s 的第 i 个字符（索引从 0 开始）结尾的最长有效括号子串的长度。
2. 初始化：dp 数组长度为 len(s)，初始值全部为 0——因为单个字符（无论是 \'(\' 还是 \')\'）都无法构成有效括号子串，长度为 0。
3. 状态转移逻辑：仅当 s[i] == \')\' 时，dp[i] 才可能大于 0（右括号才可能是有效子串的结尾，左括号结尾的有效长度必为 0），分两种情况讨论：
   • 情况 1：s[i-1] == \'(\'（当前右括号与前一个左括号直接匹配，形成 \"()\" 结构）：
     • 若 i >= 2（当前位置前有至少两个字符），dp[i] = dp[i-2] + 2——即当前的 \"()\" 加上以 s[i-2] 结尾的最长有效子串长度；
     • 若 i == 1（仅两个字符 \"()\"），dp[i] = 2（无前置有效子串，直接取 2）。
   • 情况 2：s[i-1] == \')\' 且 i - dp[i-1] - 1 >= 0 且 s[i - dp[i-1] - 1] == \'(\'（当前右括号的前一个字符也是右括号，但前一个有效子串的左侧存在匹配的左括号，形成 \" ( ... ) \" 结构）：
     • 若 i - dp[i-1] - 2 >= 0（左侧匹配左括号前还有字符），dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]——即前一个有效子串长度（dp[i-1]） + 当前匹配的 2 个括号（(...) 的外层） + 左侧匹配左括号之前的有效子串长度（dp[i - dp[i-1] - 2]）；
     • 若 i - dp[i-1] - 2 < 0（左侧匹配左括号前无字符），dp[i] = dp[i-1] + 2——仅取前一个有效子串长度加外层的 2 个括号。
4. 结果计算：遍历 dp 数组，记录其中的最大值，即为整个字符串的最长有效括号子串长度。

示例代码

def longestValidParentheses(s: str) -> int: n = len(s) # 若字符串长度小于2，无法构成有效括号，直接返回0 if n < 2: return 0 # dp[i]：以s[i]结尾的最长有效括号子串长度 dp = [0] * n max_len = 0 # 记录最长有效括号子串的长度 # 从索引1开始遍历（索引0无法构成有效子串） for i in range(1, n): # 仅当当前字符是右括号时，才可能构成有效子串 if s[i] == \')\': # 情况1：前一个字符是左括号，形成\"()\"结构 if s[i-1] == \'(\': # 若i>=2，需加上i-2之前的有效长度；否则直接取2 dp[i] = dp[i-2] + 2 if i >= 2 else 2 # 情况2：前一个字符是右括号，检查是否形成\"(...)\"结构 else: # 计算左侧可能匹配的左括号索引：i - dp[i-1] - 1 left_idx = i - dp[i-1] - 1 # 左括号索引需合法，且该位置确实是左括号 if left_idx >= 0 and s[left_idx] == \'(\':  # 若左侧左括号前还有字符，需加上之前的有效长度  if left_idx >= 1: dp[i] = dp[i-1] + 2 + dp[left_idx - 1]  else: dp[i] = dp[i-1] + 2 # 更新最长有效长度 if dp[i] > max_len: max_len = dp[i] return max_len# 测试示例s1 = \"(()\"print(\"最长有效括号长度1：\", longestValidParentheses(s1)) # 输出：2s2 = \")()())\"print(\"最长有效括号长度2：\", longestValidParentheses(s2)) # 输出：4s3 = \"\"print(\"最长有效括号长度3：\", longestValidParentheses(s3)) # 输出：0s4 = \"()(())\"print(\"最长有效括号长度4：\", longestValidParentheses(s4)) # 输出：6（子串\"()(())\"）

代码解析

• 状态定义的合理性：聚焦“以当前字符结尾”的有效子串，避免重复计算，且能通过前序状态自然推导当前状态，符合动态规划“最优子结构”特性。
• 情况划分的关键：
  • 情况1直接处理简单的 \"()\" 匹配，逻辑直观；
  • 情况2针对嵌套或连续的右括号（如 \"())\" 或 \"(())))\"），通过 left_idx = i - dp[i-1] - 1 定位“可能匹配的左括号”，确保不遗漏嵌套结构的有效长度。
• 边界处理的细节：
  • 提前判断 n < 2 的情况，避免后续索引越界；
  • 计算 left_idx 时先检查合法性（left_idx >= 0），再判断是否为左括号，防止数组越界。
• 复杂度分析：时间复杂度 O(n)（仅遍历字符串一次），空间复杂度 O(n)（存储 dp 数组，可优化为 O(1)，但动态规划版更易理解，适合作为基础解法）。

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

企业管理培训