菜饼同学菜饼同学/🤨AI 整理/
⌚算法面试指南
Search
⌚

算法面试指南

算法面试指南

一、数据结构

1.1 数组

特点： - 连续内存存储 - 随机访问 O(1) - 插入删除 O(n)
常见技巧： - 双指针 - 前缀和 - 差分数组

1.2 链表

单链表结构：
struct ListNode {
    ListNode *next;
    int val;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
常见操作：
// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 判断链表是否有环
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// 找环入口
ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode* p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;
        }
    }
    return nullptr;
}

1.3 栈

特点：后进先出（LIFO）
应用场景： - 括号匹配 - 表达式求值 - 单调栈
// 有效的括号
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

// 最小栈
class MinStack {
    stack<int> dataStack;
    stack<int> minStack;
public:
    void push(int val) {
        dataStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (dataStack.top() == minStack.top()) {
            minStack.pop();
        }
        dataStack.pop();
    }

    int top() { return dataStack.top(); }
    int getMin() { return minStack.top(); }
};

1.4 队列

特点：先进先出（FIFO）
// 用栈实现队列
class MyQueue {
    stack<int> inStack, outStack;

    void transfer() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
public:
    void push(int x) { inStack.push(x); }

    int pop() {
        if (outStack.empty()) transfer();
        int val = outStack.top();
        outStack.pop();
        return val;
    }

    int peek() {
        if (outStack.empty()) transfer();
        return outStack.top();
    }

    bool empty() { return inStack.empty() && outStack.empty(); }
};

1.5 哈希表

特点： - 查找/插入/删除平均 O(1) - 哈希冲突处理：链地址法、开放地址法
应用：
// 两数之和
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

1.6 堆

特点： - 完全二叉树 - 最大堆：父节点 >= 子节点 - 最小堆：父节点 <= 子节点 - 插入/删除 O(log n)，取极值 O(1)
// 前 K 个高频元素
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;

    // 最小堆
    auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
        return a.second > b.second;
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

    for (auto& [num, cnt] : freq) {
        pq.push({num, cnt});
        if (pq.size() > k) pq.pop();
    }

    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().first);
        pq.pop();
    }
    return result;
}

// 数据流中的中位数
class MedianFinder {
    priority_queue<int> maxHeap; // 左半部分
    priority_queue<int, vector<int>, greater<int>> minHeap; // 右半部分
public:
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

1.7 删除链表倒数第 N 个节点

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;

    // fast 先走 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    // 同时移动，直到 fast 到达末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除节点
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;

    return dummy.next;
}

1.8 设计哈希集合/映射

// 设计哈希集合
class MyHashSet {
    vector<list<int>> buckets;
    int size = 1000;

    int hash(int key) { return key % size; }

public:
    MyHashSet() : buckets(size) {}

    void add(int key) {
        int h = hash(key);
        for (int val : buckets[h]) {
            if (val == key) return;
        }
        buckets[h].push_back(key);
    }

    void remove(int key) {
        int h = hash(key);
        buckets[h].remove(key);
    }

    bool contains(int key) {
        int h = hash(key);
        for (int val : buckets[h]) {
            if (val == key) return true;
        }
        return false;
    }
};

// 设计哈希映射
class MyHashMap {
    vector<list<pair<int, int>>> buckets;
    int size = 1000;

    int hash(int key) { return key % size; }

public:
    MyHashMap() : buckets(size) {}

    void put(int key, int value) {
        int h = hash(key);
        for (auto& p : buckets[h]) {
            if (p.first == key) {
                p.second = value;
                return;
            }
        }
        buckets[h].push_back({key, value});
    }

    int get(int key) {
        int h = hash(key);
        for (auto& p : buckets[h]) {
            if (p.first == key) return p.second;
        }
        return -1;
    }

    void remove(int key) {
        int h = hash(key);
        buckets[h].remove_if([key](auto& p) { return p.first == key; });
    }
};

1.9 LRU 缓存

实现：哈希表 + 双向链表
class LRUCache {
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;

    void addToHead(Node* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }

    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            Node* node = new Node(key, value);
            cache[key] = node;
            addToHead(node);
            if (cache.size() > capacity) {
                Node* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
            }
        }
    }
};

1.10 LFU 缓存

实现：双哈希表 + 频率链表
class LFUCache {
    int capacity, minFreq;
    unordered_map<int, pair<int, int>> keyToValFreq;  // key -> {value, freq}
    unordered_map<int, list<int>> freqToKeys;         // freq -> keys list
    unordered_map<int, list<int>::iterator> keyToIter; // key -> iterator in list

public:
    LFUCache(int capacity) : capacity(capacity), minFreq(0) {}

    int get(int key) {
        if (!keyToValFreq.count(key)) return -1;

        // 更新频率
        int val = keyToValFreq[key].first;
        int freq = keyToValFreq[key].second;

        // 从旧频率列表移除
        freqToKeys[freq].erase(keyToIter[key]);
        if (freqToKeys[freq].empty()) {
            freqToKeys.erase(freq);
            if (minFreq == freq) minFreq++;
        }

        // 加入新频率列表
        freq++;
        keyToValFreq[key].second = freq;
        freqToKeys[freq].push_back(key);
        keyToIter[key] = --freqToKeys[freq].end();

        return val;
    }

    void put(int key, int value) {
        if (capacity == 0) return;

        if (keyToValFreq.count(key)) {
            keyToValFreq[key].first = value;
            get(key);  // 更新频率
            return;
        }

        // 容量满，淘汰最小频率的最久未使用
        if (keyToValFreq.size() >= capacity) {
            int evictKey = freqToKeys[minFreq].front();
            freqToKeys[minFreq].pop_front();
            if (freqToKeys[minFreq].empty()) {
                freqToKeys.erase(minFreq);
            }
            keyToValFreq.erase(evictKey);
            keyToIter.erase(evictKey);
        }

        // 插入新 key
        minFreq = 1;
        keyToValFreq[key] = {value, 1};
        freqToKeys[1].push_back(key);
        keyToIter[key] = --freqToKeys[1].end();
    }
};

二、树

2.1 二叉树遍历

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

// 前序遍历（递归）
void preorder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    result.push_back(root->val);
    preorder(root->left, result);
    preorder(root->right, result);
}

// 前序遍历（迭代）
vector<int> preorderIterative(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

// 中序遍历（迭代）
vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        for (int i = 0; i < size; 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);
        }
        result.push_back(level);
    }
    return result;
}

2.2 二叉树常见问题

// 最大深度
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// 翻转二叉树
TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

// 对称二叉树
bool isSymmetric(TreeNode* root) {
    return isMirror(root, root);
}

bool isMirror(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val &&
           isMirror(p->left, q->right) &&
           isMirror(p->right, q->left);
}

// 最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

// 验证二叉搜索树
bool isValidBST(TreeNode* root, long minVal = LONG_MIN, long maxVal = LONG_MAX) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isValidBST(root->left, minVal, root->val) &&
           isValidBST(root->right, root->val, maxVal);
}

// 从前序与中序遍历构造二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderMap[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.size() - 1,
                 inorder, 0, inorder.size() - 1, inorderMap);
}

TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                vector<int>& inorder, int inStart, int inEnd,
                unordered_map<int, int>& inorderMap) {
    if (preStart > preEnd) return nullptr;
    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = inorderMap[rootVal];
    int leftSize = rootIndex - inStart;
    root->left = build(preorder, preStart + 1, preStart + leftSize,
                       inorder, inStart, rootIndex - 1, inorderMap);
    root->right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, rootIndex + 1, inEnd, inorderMap);
    return root;
}

// 完全二叉树的节点个数（O(log²n)）
int countNodes(TreeNode* root) {
    if (!root) return 0;

    int leftHeight = 0, rightHeight = 0;
    TreeNode* left = root;
    TreeNode* right = root;

    while (left) {
        leftHeight++;
        left = left->left;
    }
    while (right) {
        rightHeight++;
        right = right->right;
    }

    // 如果左右高度相同，说明是满二叉树
    if (leftHeight == rightHeight) {
        return (1 << leftHeight) - 1;
    }

    // 否则递归计算
    return 1 + countNodes(root->left) + countNodes(root->right);
}

2.3 二叉树进阶

// 二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    depth(root, diameter);
    return diameter;
}

int depth(TreeNode* node, int& diameter) {
    if (!node) return 0;
    int left = depth(node->left, diameter);
    int right = depth(node->right, diameter);
    diameter = max(diameter, left + right);
    return 1 + max(left, right);
}

// 二叉树的右视图
vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (i == size - 1) result.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

// 二叉树的序列化与反序列化
class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "null";
        return to_string(root->val) + "," +
               serialize(root->left) + "," +
               serialize(root->right);
    }

    TreeNode* deserialize(string data) {
        queue<string> nodes;
        stringstream ss(data);
        string node;
        while (getline(ss, node, ',')) {
            nodes.push(node);
        }
        return buildTree(nodes);
    }

private:
    TreeNode* buildTree(queue<string>& nodes) {
        string val = nodes.front();
        nodes.pop();
        if (val == "null") return nullptr;
        TreeNode* root = new TreeNode(stoi(val));
        root->left = buildTree(nodes);
        root->right = buildTree(nodes);
        return root;
    }
};

三、排序算法

3.1 排序算法对比

算法
平均时间
最坏时间
空间
稳定性
冒泡排序
O(n²)
O(n²)
O(1)
稳定
选择排序
O(n²)
O(n²)
O(1)
不稳定
插入排序
O(n²)
O(n²)
O(1)
稳定
快速排序
O(n log n)
O(n²)
O(log n)
不稳定
归并排序
O(n log n)
O(n log n)
O(n)
稳定
堆排序
O(n log n)
O(n log n)
O(1)
不稳定
计数排序
O(n + k)
O(n + k)
O(k)
稳定

3.2 快速排序

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

int partition(vector<int>& nums, int left, int right) {
    // 随机选择基准，避免最坏情况
    int randomIndex = left + rand() % (right - left + 1);
    swap(nums[randomIndex], nums[right]);

    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[right]);
    return i;
}

// 三路快排（处理大量重复元素）
void quickSort3Way(vector<int>& nums, int left, int right) {
    if (left >= right) return;

    int pivot = nums[left];
    int lt = left;      // nums[left..lt-1] < pivot
    int gt = right + 1; // nums[gt..right] > pivot
    int i = left + 1;   // nums[lt..i-1] == pivot

    while (i < gt) {
        if (nums[i] < pivot) {
            swap(nums[i++], nums[lt++]);
        } else if (nums[i] > pivot) {
            swap(nums[i], nums[--gt]);
        } else {
            i++;
        }
    }

    quickSort3Way(nums, left, lt - 1);
    quickSort3Way(nums, gt, right);
}

3.3 归并排序

void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    for (int i = 0; i < temp.size(); i++) {
        nums[left + i] = temp[i];
    }
}

// 链表归并排序
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    // 快慢指针找中点
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = nullptr;

    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);
    return mergeLists(left, right);
}

ListNode* mergeLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = l1 ? l1 : l2;
    return dummy.next;
}

3.4 堆排序

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 建堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(nums, n, i);
    }
    // 排序
    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapify(nums, i, 0);
    }
}

void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

3.5 第 K 大元素（快速选择）

int findKthLargest(vector<int>& nums, int k) {
    int target = nums.size() - k; // 第 k 大 = 第 n-k+1 小
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int pivot = partition(nums, left, right);
        if (pivot == target) {
            return nums[pivot];
        } else if (pivot < target) {
            left = pivot + 1;
        } else {
            right = pivot - 1;
        }
    }
    return nums[left];
}

四、二分查找

4.1 基本模板

// 标准二分查找
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 查找左边界（第一个 >= target 的位置）
int lowerBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// 查找右边界（最后一个 <= target 的位置）
int upperBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left - 1;
}

4.2 二分查找变体

// 搜索旋转排序数组
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // 左半部分有序
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 右半部分有序
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

// 寻找峰值
int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// 在排序数组中查找元素的第一个和最后一个位置
vector<int> searchRange(vector<int>& nums, int target) {
    int first = lowerBound(nums, target);
    if (first == nums.size() || nums[first] != target) {
        return {-1, -1};
    }
    int last = upperBound(nums, target);
    return {first, last};
}

// 搜索二维矩阵
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        else if (val < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

五、动态规划

5.1 基础问题

// 爬楼梯
int climbStairs(int n) {
    if (n <= 2) return n;
    int prev1 = 1, prev2 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev1 = prev2;
        prev2 = curr;
    }
    return prev2;
}

// 最小路径和
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

// 不同路径
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

// 最大子数组和
int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0], currSum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }
    return maxSum;
}

5.2 子序列问题

// 最长递增子序列（LIS）
int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

// LIS 优化版 O(n log n)
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

// 最长公共子序列（LCS）
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[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];
}

// 编辑距离
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[m][n];
}

// 最长回文子串
string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLen = 1;

    for (int i = 0; i < n; i++) dp[i][i] = true;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
    }
    return s.substr(start, maxLen);
}

// 回文子串数量
int countSubstrings(string s) {
    int n = s.size(), count = 0;
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j]) {
                if (j - i <= 2 || dp[i+1][j-1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
    }
    return count;
}

// 单词拆分
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

5.3 背包问题

// 0-1 背包
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

// 完全背包
int knapsackComplete(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = weights[i]; w <= capacity; w++) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

// 零钱兑换（最少硬币数）
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// 零钱兑换 II（组合数）
int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

// 分割等和子集
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

5.4 股票问题

// 买卖股票的最佳时机（只能买卖一次）
int maxProfit1(vector<int>& prices) {
    int minPrice = INT_MAX, maxProfit = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

// 买卖股票的最佳时机 II（可以多次买卖）
int maxProfit2(vector<int>& prices) {
    int profit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

// 买卖股票的最佳时机 III（最多两次交易）
int maxProfit3(vector<int>& prices) {
    int buy1 = INT_MIN, sell1 = 0;
    int buy2 = INT_MIN, sell2 = 0;
    for (int price : prices) {
        buy1 = max(buy1, -price);
        sell1 = max(sell1, buy1 + price);
        buy2 = max(buy2, sell1 - price);
        sell2 = max(sell2, buy2 + price);
    }
    return sell2;
}

// 打家劫舍
int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    int prev1 = 0, prev2 = 0;
    for (int num : nums) {
        int curr = max(prev2 + num, prev1);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// 打家劫舍 II（环形）
int robII(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

int robRange(vector<int>& nums, int start, int end) {
    int prev1 = 0, prev2 = 0;
    for (int i = start; i <= end; i++) {
        int curr = max(prev2 + nums[i], prev1);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

六、双指针与滑动窗口

6.1 双指针

// 三数之和
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

// 盛最多水的容器
int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxWater = 0;
    while (left < right) {
        int water = min(height[left], height[right]) * (right - left);
        maxWater = max(maxWater, water);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

// 接雨水
int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
}

6.2 滑动窗口

// 长度最小的子数组
int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, sum = 0, minLen = INT_MAX;
    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

// 无重复字符的最长子串
int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.size(); right++) {
        while (window.count(s[right])) {
            window.erase(s[left]);
            left++;
        }
        window.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

// 最小覆盖子串
string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    int start = 0, minLen = INT_MAX;

    while (right < s.size()) {
        char c = s[right];
        right++;
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }

        while (valid == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s[left];
            left++;
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

// 滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // 存储索引，单调递减
    for (int i = 0; i < nums.size(); i++) {
        // 移除窗口外的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 维护单调性
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

// 找到字符串中所有字母异位词
vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    if (s.size() < p.size()) return result;

    vector<int> pCount(26, 0), sCount(26, 0);
    for (char c : p) pCount[c - 'a']++;

    for (int i = 0; i < s.size(); i++) {
        sCount[s[i] - 'a']++;
        if (i >= p.size()) {
            sCount[s[i - p.size()] - 'a']--;
        }
        if (pCount == sCount) {
            result.push_back(i - p.size() + 1);
        }
    }
    return result;
}

七、回溯算法

7.1 排列组合

// 全排列
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    backtrack(nums, used, path, result);
    return result;
}

void backtrack(vector<int>& nums, vector<bool>& used,
               vector<int>& path, vector<vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, used, path, result);
        path.pop_back();
        used[i] = false;
    }
}

// 全排列 II（有重复元素）
vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    sort(nums.begin(), nums.end());
    backtrackUnique(nums, used, path, result);
    return result;
}

void backtrackUnique(vector<int>& nums, vector<bool>& used,
                     vector<int>& path, vector<vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        // 剪枝：相同元素只在第一个未使用时才选择
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrackUnique(nums, used, path, result);
        path.pop_back();
        used[i] = false;
    }
}

// 子集
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    backtrackSubsets(nums, 0, path, result);
    return result;
}

void backtrackSubsets(vector<int>& nums, int start,
                      vector<int>& path, vector<vector<int>>& result) {
    result.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrackSubsets(nums, i + 1, path, result);
        path.pop_back();
    }
}

// 组合总和
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> path;
    backtrackCombination(candidates, target, 0, path, result);
    return result;
}

void backtrackCombination(vector<int>& candidates, int target, int start,
                          vector<int>& path, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = start; i < candidates.size(); i++) {
        if (candidates[i] > target) continue;
        path.push_back(candidates[i]);
        backtrackCombination(candidates, target - candidates[i], i, path, result);
        path.pop_back();
    }
}

// 电话号码的字母组合
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};

    vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> result;
    string path;

    function<void(int)> backtrack = [&](int index) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        string letters = mapping[digits[index] - '0'];
        for (char c : letters) {
            path.push_back(c);
            backtrack(index + 1);
            path.pop_back();
        }
    };

    backtrack(0);
    return result;
}

7.2 经典回溯问题

// N 皇后
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    backtrackQueens(board, 0, result);
    return result;
}

void backtrackQueens(vector<string>& board, int row,
                     vector<vector<string>>& result) {
    if (row == board.size()) {
        result.push_back(board);
        return;
    }
    for (int col = 0; col < board.size(); col++) {
        if (!isValid(board, row, col)) continue;
        board[row][col] = 'Q';
        backtrackQueens(board, row + 1, result);
        board[row][col] = '.';
    }
}

bool isValid(vector<string>& board, int row, int col) {
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // 检查左上对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // 检查右上对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

// 括号生成
vector<string> generateParenthesis(int n) {
    vector<string> result;
    backtrackParenthesis("", n, n, result);
    return result;
}

void backtrackParenthesis(string path, int left, int right,
                          vector<string>& result) {
    if (left == 0 && right == 0) {
        result.push_back(path);
        return;
    }
    if (left > 0) {
        backtrackParenthesis(path + "(", left - 1, right, result);
    }
    if (right > left) {
        backtrackParenthesis(path + ")", left, right - 1, result);
    }
}

// 单词搜索
bool exist(vector<vector<char>>& board, string word) {
    int m = board.size(), n = board[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

bool dfs(vector<vector<char>>& board, string& word, int i, int j, int k) {
    if (k == word.size()) return true;
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
    if (board[i][j] != word[k]) return false;

    char temp = board[i][j];
    board[i][j] = '#'; // 标记已访问

    bool found = dfs(board, word, i + 1, j, k + 1) ||
                 dfs(board, word, i - 1, j, k + 1) ||
                 dfs(board, word, i, j + 1, k + 1) ||
                 dfs(board, word, i, j - 1, k + 1);

    board[i][j] = temp; // 恢复
    return found;
}

// 复原 IP 地址
vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    vector<string> path;
    backtrackIP(s, 0, path, result);
    return result;
}

void backtrackIP(string& s, int start, vector<string>& path,
                 vector<string>& result) {
    if (path.size() == 4 && start == s.size()) {
        result.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
        return;
    }
    if (path.size() == 4 || start == s.size()) return;

    for (int len = 1; len <= 3 && start + len <= s.size(); len++) {
        string segment = s.substr(start, len);
        if ((segment.size() > 1 && segment[0] == '0') ||
            (segment.size() == 3 && stoi(segment) > 255)) continue;
        path.push_back(segment);
        backtrackIP(s, start + len, path, result);
        path.pop_back();
    }
}

八、图算法

8.1 BFS/DFS

// 岛屿数量
int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfsIsland(grid, i, j);
            }
        }
    }
    return count;
}

void dfsIsland(vector<vector<char>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return;
    if (grid[i][j] != '1') return;
    grid[i][j] = '0';
    dfsIsland(grid, i + 1, j);
    dfsIsland(grid, i - 1, j);
    dfsIsland(grid, i, j + 1);
    dfsIsland(grid, i, j - 1);
}

// 岛屿的最大面积
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int maxArea = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
                maxArea = max(maxArea, dfsArea(grid, i, j));
            }
        }
    }
    return maxArea;
}

int dfsArea(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return 0;
    if (grid[i][j] != 1) return 0;
    grid[i][j] = 0;
    return 1 + dfsArea(grid, i + 1, j) + dfsArea(grid, i - 1, j) +
               dfsArea(grid, i, j + 1) + dfsArea(grid, i, j - 1);
}

// 腐烂的橘子（BFS）
int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;
    int fresh = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    }

    if (fresh == 0) return 0;

    int minutes = 0;
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    fresh--;
                    q.push({nx, ny});
                }
            }
        }
        minutes++;
    }

    return fresh == 0 ? minutes - 1 : -1;
}

// 克隆图
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int _val = 0) : val(_val) {}
};

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;

    unordered_map<Node*, Node*> visited;
    queue<Node*> q;
    q.push(node);
    visited[node] = new Node(node->val);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        for (Node* neighbor : curr->neighbors) {
            if (!visited.count(neighbor)) {
                visited[neighbor] = new Node(neighbor->val);
                q.push(neighbor);
            }
            visited[curr]->neighbors.push_back(visited[neighbor]);
        }
    }
    return visited[node];
}

// 单词接龙（最短转换序列长度）
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (!wordSet.count(endWord)) return 0;

    queue<string> q;
    q.push(beginWord);
    int level = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            string word = q.front();
            q.pop();

            for (int j = 0; j < word.size(); j++) {
                char original = word[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    word[j] = c;
                    if (word == endWord) return level + 1;
                    if (wordSet.count(word)) {
                        q.push(word);
                        wordSet.erase(word);
                    }
                }
                word[j] = original;
            }
        }
        level++;
    }
    return 0;
}

// 被围绕的区域
void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();

    // 从边界开始 DFS，标记不被围绕的 'O'
    function<void(int, int)> dfs = [&](int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
        board[i][j] = '#';  // 临时标记
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };

    // 处理边界
    for (int i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        dfs(0, j);
        dfs(m - 1, j);
    }

    // 恢复和翻转
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
    }
}

8.2 拓扑排序

// 课程表（判断是否有环）
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> inDegree(numCourses, 0);
    vector<vector<int>> graph(numCourses);

    for (auto& pre : prerequisites) {
        graph[pre[1]].push_back(pre[0]);
        inDegree[pre[0]]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) q.push(i);
    }

    int count = 0;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        count++;
        for (int next : graph[course]) {
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

    return count == numCourses;
}

// 课程表 II（返回拓扑排序）
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> inDegree(numCourses, 0);
    vector<vector<int>> graph(numCourses);

    for (auto& pre : prerequisites) {
        graph[pre[1]].push_back(pre[0]);
        inDegree[pre[0]]++;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) q.push(i);
    }

    vector<int> result;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        result.push_back(course);
        for (int next : graph[course]) {
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

    return result.size() == numCourses ? result : vector<int>();
}

8.3 最短路径

// 网络延迟时间（Dijkstra）
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> graph(n + 1);
    for (auto& t : times) {
        graph[t[0]].push_back({t[1], t[2]});
    }

    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, k});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    int maxDist = *max_element(dist.begin() + 1, dist.end());
    return maxDist == INT_MAX ? -1 : maxDist;
}

九、单调栈

// 每日温度
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> result(n, 0);
    stack<int> st; // 存储索引

    for (int i = 0; i < n; i++) {
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int idx = st.top();
            st.pop();
            result[idx] = i - idx;
        }
        st.push(i);
    }
    return result;
}

// 柱状图中最大的矩形
int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;
    heights.push_back(0); // 哨兵

    for (int i = 0; i < heights.size(); i++) {
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()];
            st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    return maxArea;
}

// 最大矩形（二维矩阵中只包含 1 的最大矩形面积）
int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n, 0);
    int maxArea = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
        }
        maxArea = max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

// 下一个更大元素
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> nextGreater;
    stack<int> st;

    for (int num : nums2) {
        while (!st.empty() && num > st.top()) {
            nextGreater[st.top()] = num;
            st.pop();
        }
        st.push(num);
    }

    vector<int> result;
    for (int num : nums1) {
        result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
    }
    return result;
}

十、其他高频题

10.1 区间问题

// 合并区间
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;

    for (auto& interval : intervals) {
        if (result.empty() || result.back()[1] < interval[0]) {
            result.push_back(interval);
        } else {
            result.back()[1] = max(result.back()[1], interval[1]);
        }
    }
    return result;
}

// 会议室 II（最少需要多少会议室）
int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<pair<int, int>> events;
    for (auto& interval : intervals) {
        events.push_back({interval[0], 1});  // 开始
        events.push_back({interval[1], -1}); // 结束
    }
    sort(events.begin(), events.end());

    int rooms = 0, maxRooms = 0;
    for (auto& [time, delta] : events) {
        rooms += delta;
        maxRooms = max(maxRooms, rooms);
    }
    return maxRooms;
}

10.2 贪心算法

// 跳跃游戏
bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxReach) return false;
        maxReach = max(maxReach, i + nums[i]);
    }
    return true;
}

// 跳跃游戏 II（最少跳跃次数）
int jump(vector<int>& nums) {
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == end) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

// 加油站
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalGas = 0, currGas = 0, start = 0;
    for (int i = 0; i < gas.size(); i++) {
        totalGas += gas[i] - cost[i];
        currGas += gas[i] - cost[i];
        if (currGas < 0) {
            start = i + 1;
            currGas = 0;
        }
    }
    return totalGas >= 0 ? start : -1;
}

10.3 矩阵操作

// 螺旋矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) result.push_back(matrix[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) result.push_back(matrix[bottom][j]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
            left++;
        }
    }
    return result;
}

// 旋转图像（顺时针 90 度）
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // 转置
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    // 水平翻转
    for (int i = 0; i < n; i++) {
        reverse(matrix[i].begin(), matrix[i].end());
    }
}

10.4 字符串

// 字符串相加
string addStrings(string num1, string num2) {
    string result;
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;

    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        result += (sum % 10) + '0';
        carry = sum / 10;
    }

    reverse(result.begin(), result.end());
    return result;
}

// 字符串相乘
string multiply(string num1, string num2) {
    int m = num1.size(), n = num2.size();
    vector<int> result(m + n, 0);

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + result[p2];
            result[p2] = sum % 10;
            result[p1] += sum / 10;
        }
    }

    string str;
    for (int num : result) {
        if (!(str.empty() && num == 0)) {
            str += to_string(num);
        }
    }
    return str.empty() ? "0" : str;
}

// KMP 算法
int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;

    // 构建 next 数组
    int n = needle.size();
    vector<int> next(n, 0);
    for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];
        }
        if (needle[i] == needle[j]) j++;
        next[i] = j;
    }

    // 匹配
    for (int i = 0, j = 0; i < haystack.size(); i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) j++;
        if (j == n) return i - n + 1;
    }
    return -1;
}

// 最长公共前缀
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];

    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

// 字符串转换整数 (atoi)
int myAtoi(string s) {
    int i = 0, n = s.size();

    // 跳过前导空格
    while (i < n && s[i] == ' ') i++;
    if (i == n) return 0;

    // 处理符号
    int sign = 1;
    if (s[i] == '-' || s[i] == '+') {
        sign = s[i] == '-' ? -1 : 1;
        i++;
    }

    // 转换数字
    long result = 0;
    while (i < n && isdigit(s[i])) {
        result = result * 10 + (s[i] - '0');
        if (result * sign > INT_MAX) return INT_MAX;
        if (result * sign < INT_MIN) return INT_MIN;
        i++;
    }

    return result * sign;
}

// 缺失的第一个正数
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();

    // 原地哈希：将每个正数 x 放到索引 x-1 的位置
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }

    // 找第一个不在正确位置的正数
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }

    return n + 1;
}

// 任务调度器
int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26, 0);
    for (char task : tasks) freq[task - 'A']++;

    int maxFreq = *max_element(freq.begin(), freq.end());
    int maxCount = count(freq.begin(), freq.end(), maxFreq);

    // 公式：(maxFreq - 1) * (n + 1) + maxCount
    // 但至少需要 tasks.size() 个时间槽
    int result = (maxFreq - 1) * (n + 1) + maxCount;
    return max(result, (int)tasks.size());
}

十一、高频面试题汇总

题目
难度
类型
核心思路
LRU 缓存
⭐⭐⭐
设计
哈希表 + 双向链表
反转链表
⭐⭐
链表
迭代/递归
合并 K 个有序链表
⭐⭐⭐
链表
最小堆/分治
二叉树遍历
⭐⭐
树
递归/迭代
最近公共祖先
⭐⭐
树
递归
快速排序
⭐⭐⭐
排序
分治 + 随机化
第 K 大元素
⭐⭐
排序
快速选择/堆
二分查找变体
⭐⭐⭐
查找
边界处理
最长递增子序列
⭐⭐⭐
DP
二分优化
编辑距离
⭐⭐⭐
DP
二维 DP
零钱兑换
⭐⭐
DP
完全背包
接雨水
⭐⭐⭐
双指针
左右指针
最小覆盖子串
⭐⭐⭐
滑动窗口
双指针 + 哈希
全排列
⭐⭐
回溯
标记数组
N 皇后
⭐⭐⭐
回溯
剪枝
岛屿数量
⭐⭐
图
DFS/BFS
课程表
⭐⭐⭐
图
拓扑排序
柱状图最大矩形
⭐⭐⭐
单调栈
单调递增栈
合并区间
⭐⭐
贪心
排序 + 合并
跳跃游戏
⭐⭐
贪心
最远可达
最后更新：2026-01-09
你觉得这篇文章怎么样？
YYDS
比心
酷
加油
菜狗
… views

Loading Comments...