C++ 面试速成代码合集

🧩 1. 反转链表

#include <iostream>
using namespace std;

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

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;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n; // 输入链表长度
    ListNode* head = nullptr, *tail = nullptr;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ListNode* node = new ListNode(x);
        if (!head) head = tail = node;
        else tail->next = node, tail = node;
    }
    ListNode* reversed = reverseList(head);
    printList(reversed);
    return 0;
}

---

🌳 2. 二叉树中序遍历（递归）

#include <iostream>
#include <vector>
using namespace std;

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

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

TreeNode* buildTree() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    TreeNode* root = new TreeNode(val);
    root->left = buildTree();   // 前序输入
    root->right = buildTree();
    return root;
}

int main() {
    TreeNode* root = buildTree(); // 输入如 1 2 -1 -1 3 -1 -1
    vector<int> res;
    inorder(root, res);
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

---

🌐 3. 图的 BFS 遍历

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

void bfs(unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (visited.count(node)) continue;
        visited.insert(node);
        cout << node << " ";
        for (int neighbor : graph[node]) {
            q.push(neighbor);
        }
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n >> m; // n个点，m条边
    unordered_map<int, vector<int>> graph;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 无向图
    }
    int start; cin >> start;
    bfs(graph, start);
    return 0;
}

---

🔠 4. 滑动窗口：最长无重复子串

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left = 0, res = 0;
    for (int right = 0; right < s.length(); ++right) {
        while (window.count(s[right])) {
            window.erase(s[left++]);
        }
        window.insert(s[right]);
        res = max(res, right - left + 1);
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    cout << lengthOfLongestSubstring(s) << endl;
    return 0;
}

---

📦 5. 动态规划：最长上升子序列 LIS

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];
    cout << lengthOfLIS(nums) << endl;
    return 0;
}

6. 并查集（Union-Find）

class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

讲解：

• 数据结构：

  • parent 数组：parent[i] 存储节点 i 的父节点，根节点的父节点是自己。

• 操作逻辑：

  • find(x) 递归寻找并返回根节点，同时做路径压缩（优化），将路径上所有节点直接挂到根节点上。

  • unite(x, y) 合并两个集合，把一个根挂到另一个根下面。

  • connected(x, y) 判断两个节点是否属于同一个集合。

• 应用场景：

  • 判断连通性，解决无向图中连通块个数问题，处理动态合并集合问题。

一、图论类：BFS & DFS

BFS

#include<vector>
#include<queue>
void bfs(int start, vector<vector<int>> &graph, vector<int> &visited){
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while(q.empty()){
		int curr = q.front(); q.pop();
		for(int neighbor: graph[curr]){
			if(!visited[neighbor]){
				visited[neighbor] = true;
				q.push(neighbor);
			}
		}
	
	}
}

DFS

void dfs(int node, vector<vector<int>> &graph, vector<int> &visited){
	visited[node] = true;
	for(int neighbor : graph[node]){
		if(!visited[neighbor]){
			dfs(neighbor, graph, visited);
		}
	}
}

✅ 常用排序算法总览

算法	时间复杂度	空间复杂度	稳定性	是否原地排序	适用场景
冒泡排序	O(n²)	O(1)	✅ 稳定	✅ 原地	教学用，基础
插入排序	O(n²)	O(1)	✅ 稳定	✅ 原地	几乎有序数组
选择排序	O(n²)	O(1)	❌ 不稳定	✅ 原地	数据量小
快速排序	O(n log n)	O(log n)	❌ 不稳定	✅ 原地	实战最常用
归并排序	O(n log n)	O(n)	✅ 稳定	❌ 非原地	数据量大，要求稳定性
堆排序	O(n log n)	O(1)	❌ 不稳定	✅ 原地	Top-K问题
计数排序	O(n + k)	O(k)	✅ 稳定	❌ 非原地	整数值域小
桶排序	O(n) ~ O(n²)	O(n + k)	✅ 稳定	❌ 非原地	数据均匀分布
基数排序	O(nk)	O(n + k)	✅ 稳定	❌ 非原地	字符串、大整数排序

---

🔹 1. 冒泡排序 Bubble Sort

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < n - 1 - i; ++j)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

• 每次把最大的数“冒泡”到最后。

• 简单易懂，但效率很差。

---

🔹 2. 插入排序 Insertion Sort

void insertionSort(vector<int>& arr) {
    for (int i = 1; i < arr.size(); ++i) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

• 把当前元素插入到前面有序部分的正确位置。

---

🔹 3. 选择排序 Selection Sort

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (arr[j] < arr[minIndex])
                minIndex = j;
        swap(arr[i], arr[minIndex]);
    }
}

• 每次选择最小值放到前面。

---

🔹 4. 快速排序 Quick Sort（🔥重点）

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left], i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;
        while (i < j && arr[i] <= pivot) ++i;
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[left], arr[i]);
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

• 分治思想，效率高，实战常用。

• 平均 $O(n\log n)$，最坏 $O(n^2)$。

---

🔹 5. 归并排序 Merge Sort（稳定，适合大数据）

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

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

• 使用辅助数组，时间复杂度始终是 $O(n\log n)$。

• 稳定排序，常用于面试题和外部排序。

---

🔹 6. 堆排序 Heap Sort（使用 priority_queue 实现）

void heapSort(vector<int>& arr) {
    priority_queue<int> pq;
    for (int num : arr) pq.push(num);
    for (int i = arr.size() - 1; i >= 0; --i) {
        arr[i] = pq.top(); pq.pop();
    }
}

• 实现一个大顶堆，每次取最大值。

• 实际更适合处理 top-K 类问题。

---

✅ 总结：面试推荐重点掌握的排序算法

类型	是否必须掌握	说明
快速排序	✅✅✅	面试最常见 + 手写能力考察
归并排序	✅✅	稳定排序，需掌握合并逻辑
插入排序	✅	适合 nearly sorted 情况
堆排序	✅	理解堆结构与 STL 用法

---

✅ STL 排序简写

sort(arr.begin(), arr.end());  // 升序
sort(arr.begin(), arr.end(), greater<int>());  // 降序

// 自定义结构体排序
sort(arr.begin(), arr.end(), [](const Node& a, const Node& b) {
    return a.val < b.val; // 按 val 升序
});