14 · 高频手撕代码题库

定位：笔试/面试现场写题专用。游戏岗手撕比例 20~30%，常考两类：①经典算法题（排序/链表/树/DP/滑动窗口）②手写 C++ 基础类（智能指针/字符串类/线程池/单例）。 用法：每题先自己想思路（含复杂度）再对代码；每周至少手写 3 题，15 分钟内完成为标准。考前清单：排序、链表反转、二分、BFS/DFS、背包、字符串类。

---

1. 排序（必考）

1.1 快速排序（高频中的高频）

思路：选 pivot → 分区（左边小于 pivot，右边大于）→ 递归两边。期望 O(nlogn)，最坏 O(n²)（有序数组+固定 pivot）。

void quickSort(std::vector<int>& a, int l, int r) {
    if (l >= r) return;
    int pivot = a[(l + r) / 2];      // 取中间值避免有序数组退化
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < pivot) ++i;
        while (a[j] > pivot) --j;
        if (i <= j) { std::swap(a[i], a[j]); ++i; --j; }
    }
    quickSort(a, l, j);              // 递归左半
    quickSort(a, i, r);              // 递归右半
}
// 复杂度：期望 O(nlogn)，空间 O(logn)（递归栈）

1.2 归并排序

思路：分治：拆两半 → 各自排好 → 合并有序数组。稳定、O(nlogn)、空间 O(n)。链表排序也用它。

void merge(std::vector<int>& a, int l, int m, int r) {
    std::vector<int> tmp(a.begin() + l, a.begin() + r + 1);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r)
        a[k++] = tmp[i - l] <= tmp[j - l] ? tmp[i++ - l] : tmp[j++ - l];
    while (i <= m) a[k++] = tmp[i++ - l];
    while (j <= r) a[k++] = tmp[j++ - l];
}
void mergeSort(std::vector<int>& a, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

排序对比表（背）：

算法	平均	最坏	空间	稳定
快排	O(nlogn)	O(n²)	O(logn)	否
归并	O(nlogn)	O(nlogn)	O(n)	是
堆排	O(nlogn)	O(nlogn)	O(1)	否
冒泡/插入	O(n²)	O(n²)	O(1)	是（插入稳定）

---

2. 链表（必考三件套：反转/环/合并）

2.1 反转链表（迭代 + 递归都要会）

struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };

// 迭代（三指针）
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* nxt = cur->next;   // 先存下一个
        cur->next = prev;            // 指向前一个
        prev = cur; cur = nxt;       // 前进
    }
    return prev;                     // 新头
}

// 递归（理解：先反转后面的，再把自己接上去）
ListNode* reverseListRec(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseListRec(head->next);
    head->next->next = head;         // 下一个节点指向自己
    head->next = nullptr;
    return newHead;
}

2.2 检测环（快慢指针）

bool hasCycle(ListNode* head) {
    ListNode* slow = head, * fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // 相遇即有环
    }
    return false;
}
// 进阶：找环入口 —— 相遇后 slow 从头、fast 从相遇点，同速走，再相遇即入口

2.3 合并两个有序链表

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);                 // 哑节点省去头特判
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

链表题通用技巧：哑节点（dummy）+ 快慢指针 + 画图推演。

---

3. 二叉树（遍历是基础中的基础）

3.1 四种遍历（前/中/后/层）

struct TreeNode { int val; TreeNode* left, * right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} };

// 前序（根→左→右），递归版
void preorder(TreeNode* root) {
    if (!root) return;
    visit(root);            // 处理
    preorder(root->left);
    preorder(root->right);
}

// 层序（BFS，用队列）—— 高频
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int n = q.size();
        std::vector<int> level;
        for (int i = 0; i < n; ++i) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

递归遍历三行记忆：前序（根左右）、中序（左根右）、后序（左右根）——改 visit 的位置即可。

3.2 其他高频树题

题	思路一句话	复杂度
最大深度	递归 1 + max(左深, 右深)	O(n)
判断平衡	后序返回深度，左右差>1 即不平衡	O(n)
最近公共祖先 LCA	递归：左/右各找，两边都有→当前节点	O(n)
验证 BST	中序遍历是否递增（或递归传范围）	O(n)
二叉树前序非递归	栈模拟：压右压左	O(n)

// 最近公共祖先（背这个递归）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    if (l && r) return root;      // 两边都有 → 当前就是 LCA
    return l ? l : r;             // 只有一边有 → 返回那边
}

---

4. 二分查找（背模板）

// 标准二分（找目标值）
int binarySearch(std::vector<int>& a, int target) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;      // 防溢出
        if (a[mid] == target) return mid;
        else if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

// 左边界变体（找第一个 ≥ target 的位置，高频）
int lowerBound(std::vector<int>& a, int target) {
    int l = 0, r = (int)a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}

二分三问（面试必追问）：

1. while (l <= r) vs while (l < r) 区别？→ ≤ 用 [l,r] 闭区间，找到即返回；< 用 [l,r) 半开区间，收缩找边界
2. mid 为什么要 l + (r-l)/2？→ 防 l+r 溢出
3. 能二分的条件？→ 单调性（有序或“条件的前后状态有界”）

---

5. 滑动窗口（高频套路）

套路：右指针扩张 → 窗口不满足条件时收缩左指针 → 记录答案。适用“最长/最短连续子数组/子串”。

// 经典题：无重复字符的最长子串
int lengthOfLongestSubstring(std::string s) {
    std::unordered_map<char, int> window;   // 字符 → 出现次数
    int left = 0, ans = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        window[s[right]]++;
        while (window[s[right]] > 1) {       // 有重复 → 收缩左边界
            window[s[left]]--;
            ++left;
        }
        ans = std::max(ans, right - left + 1);
    }
    return ans;
}
// 变体题：最小覆盖子串、长度最小的子数组、水果成篮

---

6. 动态规划 DP（背模板 + 两个经典）

6.1 DP 五步法（背）

1. 定义状态 dp[i]：表示什么
2. 状态转移：dp[i] 怎么由之前的推出来
3. 初始化：边界值
4. 遍历顺序：从小到大/从大到小
5. 返回答案：dp[n] 或最值

6.2 爬楼梯（入门必会）

// 状态：dp[i] = 到第 i 阶的方法数
// 转移：dp[i] = dp[i-1] + dp[i-2]   （从 i-1 走 1 步 或 从 i-2 走 2 步）
int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;              // dp[1], dp[2]
    for (int i = 3; i <= n; ++i) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}
// 本质是斐波那契，空间压到 O(1)

6.3 0/1 背包（必考模板）

// 状态：dp[j] = 容量 j 能装的最大价值
// 转移：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])（选/不选第 i 件）
int knapsack(int capacity, std::vector<int>& weight, std::vector<int>& value) {
    int n = weight.size();
    std::vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = capacity; j >= weight[i]; --j) {   // 倒序：保证每件只取一次
            dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}
// 完全背包：内层正序（每件可无限取）

6.4 最长回文子串

// 思路：中心扩展（比 DP 好写）——每个位置向两边扩展
std::string longestPalindrome(std::string s) {
    int start = 0, maxLen = 1;
    auto expand = [&](int l, int r) {   // 从 (l,r) 向两边扩展，返回回文长度
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { --l; ++r; }
        return r - l - 1;
    };
    for (int i = 0; i < (int)s.size(); ++i) {
        int len1 = expand(i, i);        // 奇数长度回文
        int len2 = expand(i, i + 1);    // 偶数长度回文
        int len = std::max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substr(start, maxLen);
}

---

7. 手写 C++ 基础类（游戏岗特色题）

7.1 手写 shared_ptr（简化版，高频）

template <typename T>
class MySharedPtr {
    T* ptr_;
    int* count_;                     // 引用计数在堆上（所有共享者共同持有）
public:
    explicit MySharedPtr(T* p = nullptr) : ptr_(p), count_(new int(1)) {}
    MySharedPtr(const MySharedPtr& o) : ptr_(o.ptr_), count_(o.count_) {
        ++(*count_);                 // 拷贝 → 计数 +1
    }
    ~MySharedPtr() {
        if (--(*count_) == 0) {      // 析构 → 计数 -1，归零才释放
            delete ptr_;
            delete count_;
        }
    }
    MySharedPtr& operator=(const MySharedPtr& o) {
        if (this != &o) {
            // 先释放自己：计数-1，可能触发销毁
            if (--(*count_) == 0) { delete ptr_; delete count_; }
            ptr_ = o.ptr_; count_ = o.count_; ++(*count_);
        }
        return *this;
    }
    T& operator*() const { return *ptr_; }
    T* operator->() const { return ptr_; }
    int useCount() const { return *count_; }
};
// 面试重点：计数为什么在堆上 → 多个 shared_ptr 拷贝共享同一份计数；
// 循环引用问题 → 用 weak_ptr 打破（见 03 章）

7.2 手写 String 类（高频，考深拷贝/移动/运算符）

class MyString {
    char* data_;
    size_t size_;
public:
    MyString() : data_(new char[1]), size_(0) { data_[0] = '\0'; }
    MyString(const char* s) : data_(new char[strlen(s) + 1]), size_(strlen(s)) {
        strcpy(data_, s);
    }
    // 拷贝构造（深拷贝）
    MyString(const MyString& o) : data_(new char[o.size_ + 1]), size_(o.size_) {
        strcpy(data_, o.data_);
    }
    // 拷贝赋值（先释放再深拷贝 + 自赋值检查）
    MyString& operator=(const MyString& o) {
        if (this != &o) {
            delete[] data_;
            size_ = o.size_;
            data_ = new char[size_ + 1];
            strcpy(data_, o.data_);
        }
        return *this;
    }
    // 移动构造（偷指针，源置空）
    MyString(MyString&& o) noexcept : data_(o.data_), size_(o.size_) {
        o.data_ = nullptr; o.size_ = 0;
    }
    ~MyString() { delete[] data_; }
    const char* c_str() const { return data_ ? data_ : ""; }
    size_t size() const { return size_; }
};
// 考察点：深浅拷贝、自赋值、移动语义、noexcept、异常安全

7.3 手写线程安全单例（Magic Static，见 09 章）

class Singleton {
public:
    static Singleton& instance() {
        static Singleton inst;    // C++11 保证线程安全初始化
        return inst;
    }
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
private:
    Singleton() = default;
};

7.4 手写线程池（高级加分题）

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex m_;
    std::condition_variable cv_;
    bool stop_ = false;
public:
    explicit ThreadPool(size_t n) {
        for (size_t i = 0; i < n; ++i)
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> ul(m_);
                        cv_.wait(ul, [this] { return stop_ || !tasks_.empty(); });
                        if (stop_ && tasks_.empty()) return;   // 停止且任务清空 → 退出
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }
                    task();                                    // 锁外执行任务
                }
            });
    }
    template <typename F>
    void enqueue(F&& f) {
        {
            std::lock_guard<std::mutex> lg(m_);
            tasks_.emplace(std::forward<F>(f));
        }
        cv_.notify_one();
    }
    ~ThreadPool() {
        {
            std::lock_guard<std::mutex> lg(m_);
            stop_ = true;
        }
        cv_.notify_all();            // 唤醒所有等待线程退出
        for (auto& t : workers_) t.join();
    }
};
// 考点：RAII、条件变量配谓词（防虚假唤醒）、任务锁外执行、停止流程

---

8. 栈/队列专项（小而高频）

// 最小栈：O(1) 取最小值（辅助栈存当前最小值）
class MinStack {
    std::stack<int> st_, minSt_;
public:
    void push(int v) {
        st_.push(v);
        minSt_.push(minSt_.empty() ? v : std::min(v, minSt_.top()));
    }
    void pop() { st_.pop(); minSt_.pop(); }
    int top() { return st_.top(); }
    int getMin() { return minSt_.top(); }
};

// 用两个栈实现队列（压入栈 + 弹出栈）
class MyQueue {
    std::stack<int> in_, out_;
public:
    void push(int x) { in_.push(x); }
    int pop() {
        if (out_.empty())
            while (!in_.empty()) { out_.push(in_.top()); in_.pop(); }  // 倒一次
        int v = out_.top(); out_.pop();
        return v;
    }
    bool empty() { return in_.empty() && out_.empty(); }
};

---

9. 高频面试题 Q&A（合上书能讲）

Q1：快排和归并的区别？什么时候选谁？ 快排原地、常数小、期望 O(nlogn) 但最坏 O(n²)，内部排序首选；归并稳定、最坏也是 O(nlogn) 但 O(n) 空间，适合链表排序/外部排序（磁盘）。

Q2：链表反转有几种写法？ 迭代（三指针 prev/cur/nxt）和递归（先反转后面，再把下一个指回自己）。两者都要会写。

Q3：怎么检测链表有环？找环入口？ 快慢指针，快两步慢一步，相遇即有环；找入口：相遇后慢指针回头部，快慢同速走，再次相遇即入口（距离关系推导）。

Q4：滑动窗口的套路是什么？ 右指针扩张加入元素 → while 不满足条件收缩左指针 → 每次更新答案。核心是维护“窗口内的状态”（如字符计数）。

Q5：DP 题怎么想到状态转移？ 五步法：定义状态 → 找转移 → 初始化 → 遍历顺序 → 答案。多做题积累套路（爬楼梯=斐波那契、背包=选不选、子串=中心扩展/区间 DP）。

Q6：手写 shared_ptr 的关键点？ 计数在堆上共享、拷贝+1、析构-1、归零才释放、赋值要自赋值检查。答出“计数为什么在堆上”是加分点。

Q7：手写 String 要注意什么？ 深拷贝、自赋值、移动构造置空、noexcept、内存泄漏。可以提“拷贝交换（copy-and-swap）“写法更异常安全。

Q8：线程池的退出流程？ 置 stop_ → notify_all 唤醒所有工作线程 → 每个线程在 wait 谓词看到 stop_ 且队列空时 return → join 全部线程。

Q9：二分查找容易错在哪？ 边界（l<=r vs l<r）、mid 溢出（l+(r-l)/2）、死循环（收缩不明确）。建议背熟模板 + 在纸上推演边界。

Q10：手撕题和八股哪个重要？ 笔试靠手撕（硬门槛），面试靠八股+项目（综合印象）。两手都要硬，但手撕过不了连面试都没有。

---

10. 本章自测（12 题，每道 15 分钟标准，先自己写再看代码）

1. 手写快排（含随机/中间 pivot 防退化）。

2. 手写链表反转（迭代版 + 递归版）。

3. 手写层序遍历返回每层数组。

4. 手写二分查找（含 lowerBound 变体）。

5. 无重复字符的最长子串（滑动窗口）。

6. 0/1 背包（一维滚动数组）。

7. 最长回文子串（中心扩展）。

8. 手写 MyString（拷贝构造、拷贝赋值、移动构造、析构）。

9. 手写 shared_ptr（简化版，含计数）。

10. 手写线程池（enqueue + 析构退出）。

11. 用两个栈实现队列。

12. 最小栈（O(1) getMin）。

答案：

1~12：参考上文对应代码块，写完逐行对照；重点检查：快排边界（i<=j）、链表指针顺序、DP 遍历方向（背包倒序）、字符串内存管理（delete[] 配 new[]）、线程池锁外执行任务。 - 自测标准：**每道 15 分钟内写完 + 能口头解释每行的作用**；卡壳的题标记，第二天重写一遍。 ---

## 11. 进阶追问（答不上来就回来复习）

• 快排最坏情况怎么来的？三数取中 / 随机 pivot 为什么有效？
• 归并排序为什么适合链表？（不需随机访问、空间 O(1) 版链表归并）
• Top K 问题：堆 vs 快选（快速选择）区别？
• 滑动窗口和双指针有什么区别和联系？
• 区间 DP（合并石子/回文分割）、背包变体（完全/多重）什么时候考？
• 手写 String 的 copy-and-swap 写法为什么异常安全？
• 手写 环形队列 / 阻塞队列（条件变量版）作为线程池任务队列的进阶题。