当前位置：首页 > news >正文

经典算法题解析：从思路到实现，掌握核心编程思维

news 2025/7/29 10:03:57

算法是编程的灵魂，也是面试中的重点考察内容。本文精选了几道经典算法题，涵盖字符串处理、链表操作、树遍历等常见场景，通过详细解析帮助你理解算法设计思路与实现细节，提升解题能力。

一、无重复字符的最长子串

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例：

输入：s = "abcabcbb" → 输出：3（最长子串是 "abc"）
输入：s = "bbbbb" → 输出：1（最长子串是 "b"）
输入：s = "pwwkew" → 输出：3（最长子串是 "wke"）

解题思路：滑动窗口 + 哈希表

滑动窗口是处理子串问题的高效方法，核心是维护一个动态窗口 [left, right]，确保窗口内的字符无重复。配合哈希表记录字符最后出现的位置，可快速调整窗口边界。

代码实现

def length_of_longest_substring(s):char_map = {}  # 记录字符最后出现的位置left = 0       # 滑动窗口左边界max_len = 0    # 最大长度for right in range(len(s)):current_char = s[right]# 若当前字符已存在且在窗口内，移动左边界if current_char in char_map and char_map[current_char] >= left:left = char_map[current_char] + 1# 更新字符的最新位置char_map[current_char] = right# 计算当前窗口长度并更新最大值current_len = right - left + 1max_len = max(max_len, current_len)return max_len

详细解析

核心变量：
- left 和 right 分别为窗口的左右边界，初始时 left=0。
- char_map 存储每个字符最后一次出现的索引，用于快速判断重复。
- max_len 记录最长无重复子串的长度。
窗口调整逻辑：
- 遍历字符串时，right 不断右移，扩大窗口范围。
- 若当前字符 current_char 已在 char_map 中，且上次出现的位置在窗口内（char_map[current_char] >= left），说明出现重复，需将左边界 left 移到上次出现位置的下一位（char_map[current_char] + 1），确保窗口内无重复。
- 每次移动后，计算当前窗口长度（right - left + 1），并更新 max_len。
复杂度分析：
- 时间复杂度：O (n)，每个字符仅被遍历一次。
- 空间复杂度：O (min (n, m))，m 为字符集大小（如 ASCII 字符集为 256）。

二、合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解题思路：递归法

递归是处理链表问题的常用思路，通过比较两个链表的当前节点值，递归合并剩余节点，代码简洁直观。

代码实现

# 定义链表节点
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists(l1, l2):# 若其中一个链表为空，直接返回另一个if not l1:return l2if not l2:return l1# 递归合并if l1.val <= l2.val:l1.next = merge_two_lists(l1.next, l2)return l1else:l2.next = merge_two_lists(l1, l2.next)return l2

详细解析

递归终止条件：
- 若 l1 为空，返回 l2（空链表与非空链表合并结果为非空链表）。
- 若 l2 为空，返回 l1，逻辑同上。
递归逻辑：
- 比较 l1.val 和 l2.val，选择值较小的节点作为当前合并链表的节点。
- 递归合并该节点的 next 指针与另一个链表，形成新的链表。
- 返回当前选择的节点，作为合并后链表的一部分。
示例验证：
以 l1 = [1,2,4] 和 l2 = [1,3,4] 为例：
- 比较 l1.val=1 和 l2.val=1，选择 l1，递归合并 l1.next=[2,4] 与 l2=[1,3,4]。
- 后续步骤类似，最终合并结果为 [1,1,2,3,4,4]。
复杂度分析：
- 时间复杂度：O (m + n)，m 和 n 分别为两链表长度，需遍历所有节点。
- 空间复杂度：O (m + n)，递归栈深度最坏情况下为两链表长度之和。

三、有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例：

输入：s = "()" → 输出：True
输入：s = "()[]{}" → 输出：True
输入：s = "(]" → 输出：False

解题思路：栈结构

栈的 “后进先出” 特性非常适合处理括号匹配问题：左括号入栈，右括号则弹出栈顶元素检查是否匹配。

代码实现

def is_valid(s):stack = []  # 存储左括号的栈mapping = {')': '(', ']': '[', '}': '{'}  # 右括号到左括号的映射for char in s:# 若为右括号，检查栈顶元素是否匹配if char in mapping:# 栈为空或栈顶元素不匹配，返回Falseif not stack or stack.pop() != mapping[char]:return False# 若为左括号，直接入栈else:stack.append(char)# 遍历结束后，栈应为空return len(stack) == 0

详细解析

栈与哈希表的配合：
- 栈 stack 用于存储左括号，遇到左括号直接入栈。
- 哈希表 mapping 存储右括号到左括号的映射，方便快速查找匹配的左括号（如 ')' 对应 '('）。
匹配逻辑：
- 遍历字符串中的每个字符：
  - 若为右括号：
    - 若栈为空，说明没有左括号与之匹配，返回 False。
    - 弹出栈顶元素，若与当前右括号不匹配（如 ')' 对应栈顶不是 '('），返回 False。
  - 若为左括号，直接入栈。
- 遍历结束后，若栈不为空，说明存在未匹配的左括号，返回 False；否则返回 True。
示例验证：
输入 s = "([)]"：
- 遍历到 '('，入栈 → 栈：['(']。
- 遍历到 '['，入栈 → 栈：['(', '[']。
- 遍历到 ')'，栈顶为 '['，不匹配 → 返回 False。
复杂度分析：
- 时间复杂度：O (n)，遍历字符串一次。
- 空间复杂度：O (n)，最坏情况下栈存储所有左括号。

四、二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历结果。（中序遍历顺序：左子树 → 根节点 → 右子树）

示例：
输入：root = [1,null,2,3]（二叉树结构：根节点 1，右子节点 2，2 的左子节点 3）
输出：[1,3,2]

解题思路：递归法

递归是实现树遍历的直观方法，中序遍历的递归逻辑为：先遍历左子树，再访问根节点，最后遍历右子树。

代码实现

# 定义二叉树节点
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorder_traversal(root):result = []def inorder(node):if node is None:return# 递归遍历左子树inorder(node.left)# 访问根节点result.append(node.val)# 递归遍历右子树inorder(node.right)inorder(root)return result

详细解析

递归函数设计：
- 辅助函数 inorder(node) 用于实现中序遍历，参数为当前节点 node。
- 终止条件：若 node 为空，直接返回（空树无需遍历）。
遍历顺序：
- 递归遍历左子树：inorder(node.left)，确保左子树所有节点先于根节点被访问。
- 访问根节点：将当前节点值加入结果列表 result。
- 递归遍历右子树：inorder(node.right)，确保右子树所有节点后于根节点被访问。
示例验证：
对于 root = [1,null,2,3]：
- 调用 inorder(1)，先遍历左子树（为空），访问 1 → result = [1]。
- 递归遍历右子树 2，先遍历其左子树 3：访问 3 → result = [1,3]。
- 访问 2 → result = [1,3,2]，最终返回 [1,3,2]。
复杂度分析：
- 时间复杂度：O (n)，遍历所有节点一次。
- 空间复杂度：O (h)，h 为树的高度，递归栈深度取决于树高，最坏情况（链状树）为 O (n)。