系统设计题完全详解¶

重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐⭐⭐ 学习时间：2-3天 前置知识：哈希表、链表、面向对象设计

📚 目录¶

设计题概述
LRU缓存
LFU缓存
其他设计题
LeetCode题目详解

设计题概述¶

什么是设计题？¶

设计题要求你设计并实现一个数据结构或系统组件，考察： - 面向对象设计能力 - 数据结构的综合运用 - 时间和空间复杂度的权衡

常见设计题类型¶

类型	代表题目	核心数据结构
缓存设计	LRU、LFU	哈希表 + 双向链表
数据结构实现	Trie、跳表	树、链表
系统设计	阻塞队列、连接池	队列、线程同步

LRU缓存¶

什么是LRU？¶

LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略。

核心思想：当缓存满时，淘汰最久未使用的数据。

生活例子：

Text Only

你的书桌只能放5本书：
1. 经常看的书放在手边（最近使用）
2. 不常看的书放远一些
3. 新书来了，最久没看的书被移走

实现思路¶

Text Only

需要O(1)时间完成：
1. get(key) - 获取值
2. put(key, value) - 插入/更新

数据结构：
- 哈希表：key -> 链表节点（O(1)查找）
- 双向链表：按使用顺序排列（O(1)移动）

双向链表节点：
[prev | key | value | next]

最近使用的在头部(head)
最久未使用的在尾部(tail)

Python实现¶

Python

class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """
    LRU缓存实现
    时间：get和put都是O(1)
    空间：O(capacity)
    """
    def __init__(self, capacity: int):
        self.cache = {}  # key -> DLinkedNode
        self.capacity = capacity
        self.size = 0

        # 伪头部和伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        """获取值，如果不存在返回-1"""
        if key not in self.cache:
            return -1

        # 移动到头部
        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        """插入或更新值"""
        if key not in self.cache:
            # 创建新节点
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            self.size += 1

            # 超出容量，删除尾部
            if self.size > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]
                self.size -= 1
        else:
            # 更新值并移动到头部
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)

    def _add_to_head(self, node):
        """添加节点到头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """删除节点"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node):
        """移动节点到头部"""
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_tail(self):
        """删除尾部节点"""
        node = self.tail.prev
        self._remove_node(node)
        return node

# 测试
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1
cache.put(3, 3)        # 淘汰key=2
print(cache.get(2))    # -1
cache.put(4, 4)        # 淘汰key=1
print(cache.get(1))    # -1
print(cache.get(3))    # 3
print(cache.get(4))    # 4

C++实现（竞赛风格）¶

C++

#include <bits/stdc++.h>  // 引入头文件
using namespace std;

/**
 * LRU缓存（LeetCode 146）
 * 时间：get和put都是O(1)
 * 空间：O(capacity)
 */
class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;  // (key, value)
    unordered_map<int, list<pair<int, int>>::iterator> map;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1;
        }

        // 移动到链表头部
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 更新值并移动到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }

        // 插入新节点
        cache.push_front({key, value});
        map[key] = cache.begin();

        // 超出容量，删除尾部
        if (cache.size() > capacity) {
            int lastKey = cache.back().first;
            map.erase(lastKey);
            cache.pop_back();
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;    // 1
    cache.put(3, 3);                 // 淘汰key=2
    cout << cache.get(2) << endl;    // -1
    cache.put(4, 4);                 // 淘汰key=1
    cout << cache.get(1) << endl;    // -1
    cout << cache.get(3) << endl;    // 3
    cout << cache.get(4) << endl;    // 4

    return 0;
}

LFU缓存¶

什么是LFU？¶

LFU（Least Frequently Used，最不经常使用）是另一种缓存淘汰策略。

核心思想：当缓存满时，淘汰使用次数最少的数据。

与LRU的区别： - LRU：看时间（最近使用） - LFU：看频率（使用次数）

实现思路¶

Text Only

需要维护：
1. key -> (value, freq)
2. freq -> keys list
3. minFreq

get/put时：
- 增加频率
- 从原频率列表移到新频率列表
- 更新minFreq

Python实现¶

Python

from collections import defaultdict, OrderedDict

class LFUCache:
    """
    LFU缓存实现
    时间：get和put都是O(1)
    空间：O(capacity)
    """
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val_freq = {}  # key -> (value, freq)
        self.freq_to_keys = defaultdict(OrderedDict)  # freq -> {key: None}

    def get(self, key: int) -> int:
        if key not in self.key_to_val_freq:
            return -1

        value, freq = self.key_to_val_freq[key]
        self._increase_freq(key)
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return

        if key in self.key_to_val_freq:
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self._increase_freq(key)
            return

        # 容量已满，删除最少使用
        if len(self.key_to_val_freq) >= self.capacity:
            self._remove_min_freq_key()

        # 插入新节点
        self.key_to_val_freq[key] = (value, 1)
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

    def _increase_freq(self, key):
        """增加key的使用频率"""
        value, freq = self.key_to_val_freq[key]
        self.key_to_val_freq[key] = (value, freq + 1)

        # 从原频率列表删除
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1

        # 加入新频率列表
        self.freq_to_keys[freq + 1][key] = None

    def _remove_min_freq_key(self):
        """删除最少使用的key"""
        key = next(iter(self.freq_to_keys[self.min_freq]))
        del self.freq_to_keys[self.min_freq][key]
        if not self.freq_to_keys[self.min_freq]:
            del self.freq_to_keys[self.min_freq]
        del self.key_to_val_freq[key]

# 测试
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1，freq(1)=2
cache.put(3, 3)        # 淘汰freq(2)=1
print(cache.get(2))    # -1
cache.put(4, 4)        # 淘汰freq(3)=1
print(cache.get(1))    # 1
print(cache.get(3))    # -1
print(cache.get(4))    # 4

其他设计题¶

跳表（Skip List）¶

Python

import random

class Skiplist:
    """
    跳表实现
    时间：搜索/插入/删除平均O(log n)
    空间：O(n)
    """
    def __init__(self):
        self.MAX_LEVEL = 16
        self.P = 0.5
        self.head = self._create_node(self.MAX_LEVEL, -1)
        self.level = 1

    def _create_node(self, level, val):
        """创建节点"""
        return {
            'val': val,
            'next': [None] * level
        }

    def _random_level(self):
        """随机生成层级"""
        level = 1
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    def search(self, target: int) -> bool:
        """搜索"""
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            while curr['next'][i] and curr['next'][i]['val'] < target:
                curr = curr['next'][i]
        curr = curr['next'][0]
        return curr and curr['val'] == target

    def add(self, num: int) -> None:
        """插入"""
        update = [self.head] * self.MAX_LEVEL
        curr = self.head

        for i in range(self.level - 1, -1, -1):
            while curr['next'][i] and curr['next'][i]['val'] < num:
                curr = curr['next'][i]
            update[i] = curr

        level = self._random_level()
        if level > self.level:
            for i in range(self.level, level):
                update[i] = self.head
            self.level = level

        new_node = self._create_node(level, num)
        for i in range(level):
            new_node['next'][i] = update[i]['next'][i]
            update[i]['next'][i] = new_node

    def erase(self, num: int) -> bool:
        """删除"""
        update = [None] * self.MAX_LEVEL
        curr = self.head

        for i in range(self.level - 1, -1, -1):
            while curr['next'][i] and curr['next'][i]['val'] < num:
                curr = curr['next'][i]
            update[i] = curr

        curr = curr['next'][0]
        if not curr or curr['val'] != num:
            return False

        for i in range(self.level):
            if update[i]['next'][i] != curr:
                break
            update[i]['next'][i] = curr['next'][i]

        while self.level > 1 and not self.head['next'][self.level - 1]:
            self.level -= 1

        return True

LeetCode题目详解¶

题目1：LRU缓存¶

题目链接：LeetCode 146

Python

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.size = 0
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node

题目2：LFU缓存¶

题目链接：LeetCode 460

Python

from collections import defaultdict, OrderedDict  # defaultdict带默认值的字典，避免KeyError

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)

    def get(self, key: int) -> int:
        if key not in self.key_to_val_freq:
            return -1
        self._increase_freq(key)
        return self.key_to_val_freq[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return

        if key in self.key_to_val_freq:
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self._increase_freq(key)
            return

        if len(self.key_to_val_freq) >= self.capacity:
            self._remove_min_freq_key()

        self.key_to_val_freq[key] = (value, 1)
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

    def _increase_freq(self, key):
        value, freq = self.key_to_val_freq[key]
        self.key_to_val_freq[key] = (value, freq + 1)

        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1

        self.freq_to_keys[freq + 1][key] = None

    def _remove_min_freq_key(self):
        key = next(iter(self.freq_to_keys[self.min_freq]))
        del self.freq_to_keys[self.min_freq][key]
        if not self.freq_to_keys[self.min_freq]:
            del self.freq_to_keys[self.min_freq]
        del self.key_to_val_freq[key]

📝 总结¶

关键要点¶

✅ LRU缓存： - 哈希表 + 双向链表 - get/put都是O(1) - 最近使用的放头部

✅ LFU缓存： - 哈希表 + 频率列表 - get/put都是O(1) - 淘汰使用次数最少的

✅ 设计题技巧： - 先确定需要支持的操作 - 选择合适的数据结构组合 - 注意时间和空间复杂度

下一步¶

继续学习： - 数学算法 - 快速幂、质数筛

📚 扩展阅读¶

LeetCode设计题专题：https://leetcode.cn/tag/design/