Quartz 4

算法面试速查

9 min read

算法面试速查手册

整理常见手撕题的核心思路和代码模板，快速复习前用。

相关文档：面试经验总结

二叉树系列

层序遍历（记录高度）

关键：使用 size 来准确处理每一层

deque<TreeNode*> dq;
dq.push_back(root);
int h = 0;
 
if (root == nullptr) return 0;
 
while (!dq.empty()) {
    int layerSize = dq.size();  // 关键：先保存当前层大小
    
    for (int i = 0; i < layerSize; ++i) {
        TreeNode* cur = dq.front();
        dq.pop_front();
        
        // 对当前节点的操作
        // ...
        
        if (cur->left != nullptr) dq.push_back(cur->left);
        if (cur->right != nullptr) dq.push_back(cur->right);
    }
    ++h;  // 完成一层
}
return h;

对称二叉树

关键：递归判断时既要比较 left/right 的连接，也要比较 node 本身的值

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        
        deque<TreeNode*> dq;
        dq.push_back(root->left);
        dq.push_back(root->right);
        
        while (!dq.empty()) {
            TreeNode* a = dq.front(); dq.pop_front();
            TreeNode* b = dq.front(); dq.pop_front();
            
            // 都空：对称
            if (a == nullptr && b == nullptr) continue;
            
            // 一空一不空：不对称
            if (a == nullptr || b == nullptr) return false;
            
            // 都不空，值不同：不对称
            if (a->val != b->val) return false;
            
            // 都不空，值相同：交叉压入（a的左比b的右，a的右比b的左）
            dq.push_back(a->left);
            dq.push_back(b->right);
            dq.push_back(a->right);
            dq.push_back(b->left);
        }
        return true;
    }
};

二叉树展开为链表

思路：利用前序遍历的顺序，但改为在树上直接操作

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        
        // 递归打平左右子树
        flatten(root->left);
        flatten(root->right);
        
        // 保存右子树
        TreeNode* rightSubtree = root->right;
        
        // 将左子树移到右边
        root->right = root->left;
        root->left = nullptr;
        
        // 找到现在右子树的最后一个节点
        TreeNode* cur = root;
        while (cur->right) {
            cur = cur->right;
        }
        
        // 连接原来的右子树
        cur->right = rightSubtree;
    }
};

从前序中序建立二叉树

关键：用哈希表快速定位中序中的位置

class Solution {
public:
    map<int, int> hm;
    int preind = 0;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int size = inorder.size();
        for (int i = 0; i < size; ++i) {
            hm[inorder[i]] = i;
        }
        return build(preorder, 0, size);
    }
    TreeNode* build(vector<int>& pre, int l, int r) {
        if (l == r) return nullptr;
 
        int curval = pre[preind++];
        TreeNode* cur = new TreeNode(curval);
        
        int ind = hm[curval];
 
        cur->left = build(pre, l, ind);
        cur->right = build(pre, ind + 1, r);
        return cur;
    }
};

最近公共祖先（LCA）

思路：递归，左右都找到则返回当前节点，否则返回有结果的一边

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) return root;
        if (left != nullptr) return left;
        if (right != nullptr) return right;
    }
};

链表反转系列

反转链表基础

关键：三指针：prev（新链表头），cur（当前处理），tmp（保存后继）

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    
    while (cur) {
        ListNode* tmp = cur->next;  // 保存后继
        cur->next = prev;           // 反向指向
        prev = cur;                 // prev 前进
        cur = tmp;                  // cur 前进
    }
    return prev;
}

K 个一组反转链表

核心思路：

  1. 用 dummy 节点统一处理
  2. 每段内反转
  3. 将各段连接
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* prevGroup = dummy;
        
        while (true) {
            // 检查是否有 k 个节点
            ListNode* kth = prevGroup;
            for (int i = 0; i < k; i++) {
                kth = kth->next;
                if (!kth) return dummy->next;
            }
            
            // 反转当前 k 个
            ListNode* groupPrev = prevGroup->next;
            ListNode* cur = prevGroup->next;
            ListNode* prev = kth->next;
            
            for (int i = 0; i < k; i++) {
                ListNode* tmp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = tmp;
            }
            
            // 连接：prevGroup.next 应该指向反转后的新头
            prevGroup->next = prev;
            prevGroup = groupPrev;
        }
    }
};

子集与回溯

所有子集（LC 78）

模式：标准回溯，每层遍历时处理一个数字

def subsets(self, nums):
    res = []
    
    def dfs(start, path):
        res.append(path[:])  # 当前路径是一个答案
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
    
    dfs(0, [])
    return res

C++ 版本：

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path = {};
        dfs(nums, 0, path);
        return res;
    }
    void dfs(vector<int>& nums, int start, vector<int>& path) {
        res.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1, path);
            path.pop_back();
        }
    } 
};

有重复元素的子集（LC 90）

关键：排序后，在同一层跳过重复元素

def subsetsWithDup(self, nums):
    nums.sort()  # 排序
    res = []
    
    def dfs(start, path):
        res.append(path[:])
        
        for i in range(start, len(nums)):
            # 在同一层，如果当前元素与前一个相同且前一个没被选
            if i > start and nums[i] == nums[i-1]:
                continue
            
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
    
    dfs(0, [])
    return res

C++ 版本：

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path = {};
        dfs(nums, 0, path);
        return res;
    }
    void dfs(vector<int>& nums, int start, vector<int>& path) {
        res.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) continue;
            path.push_back(nums[i]);
            dfs(nums, i + 1, path);
            path.pop_back();
        }
    } 
};

字符串与动态规划

最长公共子串 & 最长公共子序列

区别

  • 子串：必须连续
  • 子序列：可以不连续
# 最长公共子串（连续）
def longestCommonSubstring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    maxLen = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                maxLen = max(maxLen, dp[i][j])
    
    return maxLen
 
# 最长公共子序列（不连续）
def longestCommonSubsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

最小编辑距离（LC 72）

状态转移

if s1[i] == s2[j]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],      # 删除 s1[i]
        dp[i][j-1],      # 插入到 s1
        dp[i-1][j-1]     # 替换
    )

数组与矩阵

接雨水

思路：对于位置 i，能装水量 = min(左边最高, 右边最高) - height[i]

def trap(height):
    if not height:
        return 0
    
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    # 从左往右扫，记录最大值
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    
    # 从右往左扫，记录最大值
    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    
    # 计算能装的水
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    
    return water

岛屿个数（LC 200）

思路：DFS/BFS 遍历，每次遍历一个岛屿

def numIslands(grid):
    if not grid:
        return 0
    
    count = 0
    
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):
            return
        if grid[i][j] == '0':
            return
        
        grid[i][j] = '0'  # 标记已访问
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    
    return count

面试常见坑

坑如何避免
链表反转忘记保存后继总是先 tmp = cur->next
回溯忘记 pop检查是否有 push，就有 pop
层序遍历不保存 size每次循环前保存 layerSize = q.size()
DP 初始化错误画出前两行手工验证
边界条件漏掉单元素、空集、重复元素都试试

快速复习清单

  • 二叉树三种遍历（前、中、后）
  • 链表反转（单个、K 组）
  • 回溯模板（子集、排列、组合）
  • DP 三层关键点：定义、转移、初始化
  • 图（DFS/BFS、拓扑排序、最短路径）

算法面试常见问题总结

常见的容易踩的坑：

  • 急，没理解题目就要开写，看不到本质
  • 边界问题，需要定一个 SOP
  • 数据范围问题：1e6 如果要涉及到加法的话也是可能超 int 的，要习惯开 ll
  • 贪心变化比较多，不好想
  • 难一点的 dp，状态转移要仔细想

Graph View

Backlinks