🏗️ 数据结构与算法模式 + 面向对象 + 实战

为什么重要

模式加上结构，能把随性的编码变成可靠的问题求解。

核心思想

大多数面试题不过是少数几种模式：双指针、滑动窗口、前缀和、BFS/DFS、哈希表计数、二分查找。先识别出模式，再套用模板。

试一试

双指针——在已排序数组上求和为目标值的一对元素：

def two_sum_sorted(nums, target):
  l, r = 0, len(nums) - 1
  while l < r:
      s = nums[l] + nums[r]
      if s == target:
          return (l, r)
      if s < target:
          l += 1
      else:
          r -= 1
  return None

print(two_sum_sorted([1, 2, 4, 7, 11, 15], 13))
print(two_sum_sorted([1, 2, 4, 7, 11, 15], 99))

前缀和——经过 O(n) 的预处理后，以 O(1) 回答"任意区间之和"：

nums = [2, 4, 5, 1, 9, 3, 7]
prefix = [0]
for x in nums: prefix.append(prefix[-1] + x)

def range_sum(l, r):
  # inclusive l, exclusive r
  return prefix[r] - prefix[l]

print(range_sum(1, 4))   # 4 + 5 + 1 = 10
print(range_sum(0, len(nums)))  # all

面向对象——一个带类型注解的小小 Stack：

class Stack:
  def __init__(self):
      self._data: list = []
  def push(self, x):
      self._data.append(x)
  def pop(self):
      if not self._data: raise IndexError("pop from empty stack")
      return self._data.pop()
  def peek(self):
      return self._data[-1] if self._data else None
  def __len__(self):
      return len(self._data)
  def __repr__(self):
      return f"Stack({self._data!r})"

s = Stack()
for x in [1, 2, 3]: s.push(x)
print(s, "len:", len(s))
print("pop:", s.pop())
print("peek:", s.peek())

模式模板

把骨架背下来；问题只需填入具体的条件。

滑动窗口

l = 0
for r in range(len(arr)):
    # expand window with r
    # shrink from the left when the condition fails
    if condition:
        l += 1

栈模式

stack = []
for ch in s:
    if stack and ch == stack[-1]:
        stack.pop()
    else:
        stack.append(ch)

面向对象基础

class Player:
    def __init__(self, name):
        self.name = name
        self.score = 0

    def add(self, points):
        self.score += points

• 类（class） 定义一张蓝图。
• 实例（instance） 是一个具体的对象。
• self 指代当前对象。

数据结构与算法模式速查表

| 模式 | 何时使用 | | --- | --- | | 双指针 | 已排序数组，从两端取一对元素 | | 滑动窗口 | 满足某个和 / 条件的子数组 | | 前缀和 | 区间求和查询 | | 哈希表（dict） | 频率计数、补数查找 | | 栈 | 有效括号、单调栈 |

看到 X，就想到 Y

• "唯一元素" → set
• "频率计数" → dict
• "查找补数 / 之前见过的值" → dict
• "反转 / 回文 / 从两端取一对" → 双指针
• "累计总和" → 前缀和

必背的内置函数

len、type、range、enumerate、sorted、sum、min、max

练习体系

Bug 日志

每当你卡住时就用这个格式——目标是从每一个 bug 中提炼出一条可复用的规则：

• 日期：
• 问题：
• 我预期的：
• 实际发生的：
• 根本原因：
• 修复：
• 下次的规则：

根本原因示例：用了 b = a 而不是 a.copy()。

LeetCode 追踪表（示例）

| # | 题目 | 主题 | 状态 | 关键思路 | 错误 | 重做 | | - | ------- | ----- | ------ | -------- | ------- | ----- | | 1 | Two Sum | dict | | 补数查找 | | | | 2 | Valid Palindrome | strings | | 归一化 + 双指针 | | | | 3 | Contains Duplicate | set | | 比较集合长度 | | | | 4 | Valid Anagram | dict | | 频率计数 | | | | 5 | Running Sum | lists | | 前缀累计和 | | |

快速检查

• 问： 什么时候应该用类？ 答： 当状态和行为应当被放在一起时。

小练习

• 实现双指针反转。
• 写一个带两个方法的小类。

该做与不该做

• 该做：写一些可复用的小模板。
• 该做：保持类简单且聚焦。
• 不该做：在一个函数就够用时还过度设计。

常见错误

• 错误： 在循环里忘记更新指针。 修正： 每次至少移动一个指针。
• 错误： 为简单的数据滥用类。 修正： 先从函数开始，之后再重构。

关键要点

• 双指针：已排序数组，寻找一对 / 进行划分。
• 滑动窗口：带约束的连续子数组（最长、最短）。
• 前缀和：在固定数组上进行多次区间求和查询。
• 面向对象：封装状态；行为随之而来。用 __repr__ 让调试毫不费力。
• 保持一份 bug 日志和一份题目追踪表——记录错误是你进步最快的方式。