CSP-J 基础知识详细扩展版
本文档是CSP-J（信息学奥赛入门组）知识点的详细扩展版本，涵盖所有核心知识点的深度讲解、代码示例、应用场景和常见陷阱。
目录
第一章：C++ 基础与 STL第二章：算法基础第三章：数据结构进阶第四章：算法进阶第五章：计算机基础第六章：操作系统第七章：网络与数据库第八章：软件工程
第一章：C++ 基础与 STL
1.1 C++ 基础语法
1.1.1 数据类型详解
基本数据类型
| 类型 | 字节数 | 取值范围 | 用途 |
|---|---|---|---|
|
1 | true/false | 布尔值 |
|
1 | -128 ~ 127 | 字符 |
|
1 | 0 ~ 255 | 无符号字符 |
|
2 | -32,768 ~ 32,767 | 短整型 |
|
2 | 0 ~ 65,535 | 无符号短整型 |
|
4 | -2,147,483,648 ~ 2,147,483,647 | 整型（约-2×10⁹ ~ 2×10⁹） |
|
4 | 0 ~ 4,294,967,295 | 无符号整型（约4×10⁹） |
|
8 | -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 | 长整型（约-9×10¹⁸ ~ 9×10¹⁸） |
|
4 | ±3.4×10⁻³⁸ ~ ±3.4×10³⁸ | 单精度浮点数（6-7位有效数字） |
|
8 | ±1.7×10⁻³⁰⁸ ~ ±1.7×10³⁰⁸ | 双精度浮点数（15-16位有效数字） |
常见陷阱
// 1. 整型溢出
int a = 2000000000;
int b = 2000000000;
int c = a + b; // 溢出！结果为负数
long long d = (long long)a + b; // 正确做法
// 2. 浮点数精度问题
double x = 0.1 + 0.2;
if (x == 0.3) { // 错误！可能不相等
// ...
}
// 正确做法：使用 epsilon 比较
const double eps = 1e-9;
if (fabs(x - 0.3) < eps) {
// ...
}
// 3. 除法陷阱
int a = 5, b = 2;
double c = a / b; // 结果是 2.0，不是 2.5！
double d = (double)a / b; // 正确：2.5
1.1.2 运算符详解
位运算符
| 运算符 | 含义 | 示例 | 结果 |
|---|---|---|---|
|
按位与 | |
|
| ` | ` | 按位或 | `5 |
|
按位异或 | |
|
|
按位取反 | |
|
|
左移 | |
|
|
右移 | |
|
位运算技巧
// 1. 判断奇偶
bool isOdd(int n) {
return n & 1; // 等价于 n % 2 == 1，但更快
}
// 2. 快速乘除2的幂
int multiplyBy4(int n) {
return n << 2; // 相当于 n * 4
}
int divideBy8(int n) {
return n >> 3; // 相当于 n / 8
}
// 3. 交换两个数（不用临时变量）
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
// 4. 获取第k位（从右往左，从0开始）
bool getBit(int n, int k) {
return (n >> k) & 1;
}
// 5. 将第k位置为1
int setBit(int n, int k) {
return n | (1 << k);
}
// 6. 将第k位置为0
int clearBit(int n, int k) {
return n & ~(1 << k);
}
// 7. 统计二进制中1的个数
int countOnes(int n) {
int count = 0;
while (n) {
count++;
n &= (n - 1); // 清除最右边的1
}
return count;
}
// 8. 判断是否为2的幂
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
1.1.3 控制结构
循环优化技巧
// 1. 避免重复计算
// 不好的写法
for (int i = 0; i < vec.size(); i++) {
// 每次循环都调用 size()
}
// 好的写法
int n = vec.size();
for (int i = 0; i < n; i++) {
// ...
}
// 2. 循环展开（适用于小规模固定次数）
// 原始
for (int i = 0; i < 4; i++) {
sum += arr[i];
}
// 展开
sum += arr[0] + arr[1] + arr[2] + arr[3];
// 3. 双指针技巧
// 查找和为target的两个数
vector<int> twoSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {nums[left], nums[right]};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
1.2 STL 容器详解
1.2.1 vector（动态数组）
基本特性
动态大小的数组连续内存存储随机访问 O(1)尾部插入/删除 O(1)（均摊）中间插入/删除 O(n)
完整API
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void vectorDemo() {
// 1. 初始化方式
vector<int> v1; // 空vector
vector<int> v2(10); // 10个元素，默认值为0
vector<int> v3(10, 5); // 10个元素，值都是5
vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表
vector<int> v5(v4); // 拷贝构造
vector<int> v6(v4.begin(), v4.end()); // 范围构造
// 2. 容量相关
cout << v4.size() << endl; // 元素个数：5
cout << v4.capacity() << endl; // 容量（可能>5）
cout << v4.empty() << endl; // 是否为空：false
v4.reserve(100); // 预留空间（避免多次扩容）
v4.resize(10); // 调整大小为10
v4.resize(15, 0); // 调整为15，新元素值为0
v4.shrink_to_fit(); // 释放多余容量
// 3. 元素访问
cout << v4[0] << endl; // 下标访问（不检查越界）
cout << v4.at(0) << endl; // at访问（检查越界，安全）
cout << v4.front() << endl; // 第一个元素
cout << v4.back() << endl; // 最后一个元素
int* ptr = v4.data(); // 获取底层数组指针
// 4. 修改操作
v4.push_back(6); // 尾部添加
v4.pop_back(); // 尾部删除
v4.insert(v4.begin() + 2, 99); // 在位置2插入99
v4.insert(v4.begin(), 3, 88); // 在开头插入3个88
v4.erase(v4.begin() + 1); // 删除位置1的元素
v4.erase(v4.begin(), v4.begin()+3); // 删除范围
v4.clear(); // 清空
v4.assign(5, 10); // 重新赋值：5个10
// 5. 迭代器
for (vector<int>::iterator it = v4.begin(); it != v4.end(); ++it) {
cout << *it << " ";
}
// C++11 范围for循环
for (int x : v4) {
cout << x << " ";
}
// 反向迭代
for (auto it = v4.rbegin(); it != v4.rend(); ++it) {
cout << *it << " ";
}
}
// 6. 常用算法
void vectorAlgorithms() {
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
// 排序
sort(v.begin(), v.end()); // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序
// 自定义排序
sort(v.begin(), v.end(), [](int a, int b) {
return a > b; // 降序
});
// 查找
auto it = find(v.begin(), v.end(), 5); // 查找值为5的元素
if (it != v.end()) {
cout << "找到了，位置：" << (it - v.begin()) << endl;
}
// 二分查找（前提：已排序）
bool found = binary_search(v.begin(), v.end(), 5);
auto pos = lower_bound(v.begin(), v.end(), 5); // 第一个>=5的位置
auto pos2 = upper_bound(v.begin(), v.end(), 5); // 第一个>5的位置
// 去重（前提：已排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// 反转
reverse(v.begin(), v.end());
// 统计
int cnt = count(v.begin(), v.end(), 1); // 统计1的个数
// 求和
int sum = accumulate(v.begin(), v.end(), 0);
// 最大最小值
int maxVal = *max_element(v.begin(), v.end());
int minVal = *min_element(v.begin(), v.end());
}
二维vector
// 初始化
vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3行4列，全为0
// 访问
matrix[0][1] = 5;
// 注意：避免 >> 识别为右移
vector<vector<int> > v; // 添加空格（C++11之前）
// C++11及以后不需要空格
性能陷阱
// 陷阱1：频繁在中间插入
vector<int> v;
for (int i = 0; i < 10000; i++) {
v.insert(v.begin(), i); // 每次都O(n)，总共O(n²)
}
// 解决：使用deque或先收集后reverse
// 陷阱2：没有预留空间
vector<int> v;
for (int i = 0; i < 1000000; i++) {
v.push_back(i); // 可能多次扩容
}
// 解决：
vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; i++) {
v.push_back(i);
}
1.2.2 stack（栈）
基本特性
LIFO（后进先出）只能访问栈顶元素所有操作 O(1)
完整API与应用
#include <stack>
#include <iostream>
using namespace std;
void stackDemo() {
stack<int> s;
// 基本操作
s.push(1); // 入栈
s.push(2);
s.push(3);
cout << s.top() << endl; // 访问栈顶：3
s.pop(); // 出栈（无返回值！）
cout << s.size() << endl; // 大小：2
cout << s.empty() << endl; // 是否为空：false
}
// 应用1：括号匹配
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();
}
// 应用2：单调栈 - 找下一个更大元素
vector<int> nextGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st; // 存储下标
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[st.top()] < nums[i]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
// 应用3：表达式求值（后缀表达式）
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (token == "+") st.push(a + b);
else if (token == "-") st.push(a - b);
else if (token == "*") st.push(a * b);
else st.push(a / b);
} else {
st.push(stoi(token));
}
}
return st.top();
}
1.2.3 queue（队列）
基本特性
FIFO（先进先出）只能访问队首和队尾所有操作 O(1)
完整API与应用
#include <queue>
#include <iostream>
using namespace std;
void queueDemo() {
queue<int> q;
// 基本操作
q.push(1); // 入队
q.push(2);
q.push(3);
cout << q.front() << endl; // 队首：1
cout << q.back() << endl; // 队尾：3
q.pop(); // 出队（无返回值）
cout << q.size() << endl; // 大小：2
cout << q.empty() << endl; // 是否为空：false
}
// 应用1：BFS（广度优先搜索）
void bfs(vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
// 应用2：滑动窗口最大值（单调队列）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // 存储下标，保持递减
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
// 移除窗口外的元素
if (!dq.empty() && dq.front() < i - k + 1) {
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;
}
1.2.4 deque（双端队列）
基本特性
两端都可以插入/删除随机访问 O(1)两端插入/删除 O(1)比vector更灵活，比list更快
完整API
#include <deque>
using namespace std;
void dequeDemo() {
deque<int> dq;
// 两端操作
dq.push_back(1); // 尾部插入
dq.push_front(0); // 头部插入
dq.pop_back(); // 尾部删除
dq.pop_front(); // 头部删除
// 随机访问
dq[0] = 10;
cout << dq.at(0) << endl;
// 其他操作与vector类似
dq.insert(dq.begin() + 1, 5);
dq.erase(dq.begin());
dq.size();
dq.empty();
dq.clear();
}
1.2.5 priority_queue（优先队列/堆）
基本特性
默认大顶堆（最大元素在顶部）插入 O(log n)删除顶部 O(log n)访问顶部 O(1)
完整API与应用
#include <queue>
#include <vector>
#include <functional>
using namespace std;
void priorityQueueDemo() {
// 1. 默认大顶堆
priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
cout << maxHeap.top() << endl; // 4
maxHeap.pop();
// 2. 小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
cout << minHeap.top() << endl; // 1
// 3. 自定义比较
auto cmp = [](int a, int b) { return a > b; }; // 小顶堆
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
// 4. 自定义结构体
struct Node {
int val, priority;
bool operator<(const Node& other) const {
return priority < other.priority; // 按priority降序
}
};
priority_queue<Node> nodeHeap;
}
// 应用1：Top K问题 - 找最大的K个元素
vector<int> topKLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}
// 应用2：合并K个有序链表
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (ListNode* list : lists) {
if (list) pq.push(list);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) {
pq.push(node->next);
}
}
return dummy.next;
}
// 应用3：Dijkstra最短路径
void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start}); // {距离, 节点}
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});
}
}
}
}
1.2.6 set 和 multiset（集合）
基本特性
set：元素唯一，自动排序multiset：允许重复元素基于红黑树实现插入/删除/查找 O(log n)
完整API
#include <set>
#include <iostream>
using namespace std;
void setDemo() {
set<int> s;
// 插入
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(1); // 重复，不会插入
// 查找
auto it = s.find(3);
if (it != s.end()) {
cout << "找到了：" << *it << endl;
}
// 统计
cout << s.count(1) << endl; // 返回0或1
// 删除
s.erase(3); // 删除值为3的元素
s.erase(s.begin()); // 删除迭代器指向的元素
// 遍历（自动有序）
for (int x : s) {
cout << x << " "; // 1 4
}
// 区间操作
auto lower = s.lower_bound(2); // 第一个>=2的元素
auto upper = s.upper_bound(2); // 第一个>2的元素
// 大小
cout << s.size() << endl;
cout << s.empty() << endl;
s.clear();
}
void multisetDemo() {
multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(2);
cout << ms.count(1) << endl; // 2
// 删除所有值为1的元素
ms.erase(1);
// 只删除一个
multiset<int> ms2 = {1, 1, 2};
auto it = ms2.find(1);
if (it != ms2.end()) {
ms2.erase(it); // 只删除一个1
}
}
// 应用：区间问题
struct Interval {
int start, end;
bool operator<(const Interval& other) const {
return start < other.start;
}
};
int minMeetingRooms(vector<Interval>& intervals) {
set<Interval> s(intervals.begin(), intervals.end());
multiset<int> endTimes;
int maxRooms = 0;
for (const auto& interval : s) {
// 移除已结束的会议
auto it = endTimes.begin();
while (it != endTimes.end() && *it <= interval.start) {
it = endTimes.erase(it);
}
endTimes.insert(interval.end);
maxRooms = max(maxRooms, (int)endTimes.size());
}
return maxRooms;
}
1.2.7 map 和 multimap（映射）
基本特性
map：键唯一，自动按键排序multimap：允许键重复基于红黑树实现插入/删除/查找 O(log n)
完整API
#include <map>
#include <iostream>
#include <string>
using namespace std;
void mapDemo() {
map<string, int> m;
// 插入
m["apple"] = 3;
m["banana"] = 2;
m.insert({"orange", 5});
m.insert(make_pair("grape", 4));
// 访问
cout << m["apple"] << endl; // 3
cout << m.at("banana") << endl; // 2（会检查键是否存在）
// cout << m.at("xxx") << endl; // 抛出异常
cout << m["xxx"] << endl; // 不存在则插入，值为0
// 查找
auto it = m.find("apple");
if (it != m.end()) {
cout << it->first << ": " << it->second << endl;
}
// 判断键是否存在
if (m.count("apple")) {
cout << "apple存在" << endl;
}
// 删除
m.erase("apple");
m.erase(m.begin());
// 遍历（按键排序）
for (auto& [key, value] : m) { // C++17
cout << key << ": " << value << endl;
}
// C++11 写法
for (auto& p : m) {
cout << p.first << ": " << p.second << endl;
}
// 区间操作
auto lower = m.lower_bound("b");
auto upper = m.upper_bound("m");
// 大小
cout << m.size() << endl;
m.clear();
}
// 应用1：字符串中每个字符出现次数
map<char, int> charCount(const string& s) {
map<char, int> cnt;
for (char c : s) {
cnt[c]++;
}
return cnt;
}
// 应用2：两数之和
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> m; // 值 -> 下标
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (m.count(complement)) {
return {m[complement], i};
}
m[nums[i]] = i;
}
return {};
}
// 应用3：离散化
vector<int> discretize(vector<int>& nums) {
set<int> s(nums.begin(), nums.end());
map<int, int> m;
int id = 0;
for (int x : s) {
m[x] = id++;
}
vector<int> result;
for (int x : nums) {
result.push_back(m[x]);
}
return result;
}
1.2.8 unordered_set 和 unordered_map（哈希表）
基本特性
基于哈希表实现元素无序插入/删除/查找 平均O(1)，最坏O(n)比set/map快，但不支持有序操作
完整API
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std;
void unorderedDemo() {
// unordered_set
unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(4);
if (us.count(3)) {
cout << "3存在" << endl;
}
us.erase(3);
// unordered_map
unordered_map<string, int> um;
um["apple"] = 3;
um["banana"] = 2;
if (um.count("apple")) {
cout << "apple: " << um["apple"] << endl;
}
// 遍历（无序）
for (auto& [key, value] : um) {
cout << key << ": " << value << endl;
}
}
// 性能对比
void performanceComparison() {
const int N = 1000000;
// set vs unordered_set
set<int> s;
unordered_set<int> us;
// 插入
// set: O(n log n)
// unordered_set: O(n)
// 查找
// set: O(log n)
// unordered_set: O(1)
// 何时用set：需要有序、需要lower_bound/upper_bound
// 何时用unordered_set：只需要快速查找、不需要有序
}
1.3 STL 算法库
1.3.1 排序相关
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
void sortingAlgorithms() {
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
// 1. 完全排序
sort(v.begin(), v.end()); // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序
// 自定义比较
sort(v.begin(), v.end(), [](int a, int b) {
return a % 10 < b % 10; // 按个位数排序
});
// 2. 部分排序
partial_sort(v.begin(), v.begin() + 3, v.end()); // 只排前3个
// 3. nth_element - 找第n大
nth_element(v.begin(), v.begin() + 3, v.end()); // 第4大的元素在v[3]
// 4. 稳定排序
stable_sort(v.begin(), v.end()); // 保持相等元素的相对顺序
// 5. 判断是否有序
bool sorted = is_sorted(v.begin(), v.end());
// 6. 结构体排序
struct Student {
string name;
int score;
};
vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 90}};
// 按分数降序，分数相同按名字升序
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
if (a.score != b.score) {
return a.score > b.score;
}
return a.name < b.name;
});
}
1.3.2 查找相关
void searchingAlgorithms() {
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 1. 线性查找
auto it = find(v.begin(), v.end(), 5);
if (it != v.end()) {
cout << "找到了，位置：" << (it - v.begin()) << endl;
}
// 2. 条件查找
auto it2 = find_if(v.begin(), v.end(), [](int x) {
return x > 5 && x % 2 == 0; // 找第一个>5的偶数
});
// 3. 二分查找（前提：已排序）
bool found = binary_search(v.begin(), v.end(), 5);
// 4. lower_bound 和 upper_bound
auto lower = lower_bound(v.begin(), v.end(), 5); // 第一个>=5
auto upper = upper_bound(v.begin(), v.end(), 5); // 第一个>5
// 统计5的个数
int count5 = upper - lower;
// 5. equal_range - 同时获取
auto range = equal_range(v.begin(), v.end(), 5);
// range.first == lower_bound
// range.second == upper_bound
// 6. 最大最小值
int maxVal = *max_element(v.begin(), v.end());
int minVal = *min_element(v.begin(), v.end());
auto minmax = minmax_element(v.begin(), v.end());
cout << "Min: " << *minmax.first << ", Max: " << *minmax.second << endl;
}
1.3.3 修改相关
void modifyingAlgorithms() {
vector<int> v = {1, 2, 3, 4, 5};
// 1. 填充
fill(v.begin(), v.end(), 0); // 全部填充为0
fill_n(v.begin(), 3, 1); // 前3个填充为1
// 2. 生成
generate(v.begin(), v.end(), []() {
return rand() % 100;
});
// 3. 变换
transform(v.begin(), v.end(), v.begin(), [](int x) {
return x * 2; // 每个元素乘2
});
// 两个序列变换
vector<int> v2 = {1, 2, 3};
vector<int> result(3);
transform(v.begin(), v.begin() + 3, v2.begin(), result.begin(),
[](int a, int b) { return a + b; });
// 4. 替换
replace(v.begin(), v.end(), 0, 999); // 将0替换为999
replace_if(v.begin(), v.end(),
[](int x) { return x < 0; }, 0); // 负数替换为0
// 5. 移除
auto newEnd = remove(v.begin(), v.end(), 0); // 移除0（不改变大小）
v.erase(newEnd, v.end()); // 真正删除
// 一步到位
v.erase(remove(v.begin(), v.end(), 0), v.end());
// 条件移除
v.erase(remove_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0; // 移除偶数
}), v.end());
// 6. 去重（前提：已排序）
sort(v.begin(), v.end());
auto last = unique(v.begin(), v.end());
v.erase(last, v.end());
// 7. 反转
reverse(v.begin(), v.end());
// 8. 旋转
rotate(v.begin(), v.begin() + 2, v.end()); // 前2个移到后面
// 9. 随机打乱
random_shuffle(v.begin(), v.end()); // C++11已弃用
// shuffle(v.begin(), v.end(), rng); // C++11推荐
// 10. 划分
partition(v.begin(), v.end(), [](int x) {
return x % 2 == 0; // 偶数在前，奇数在后
});
}
1.3.4 数值算法
#include <numeric>
void numericAlgorithms() {
vector<int> v = {1, 2, 3, 4, 5};
// 1. 求和
int sum = accumulate(v.begin(), v.end(), 0);
// 初始值类型很重要
double avg = accumulate(v.begin(), v.end(), 0.0) / v.size();
// 2. 内积
vector<int> v2 = {1, 2, 3, 4, 5};
int dotProduct = inner_product(v.begin(), v.end(), v2.begin(), 0);
// = 1*1 + 2*2 + 3*3 + 4*4 + 5*5
// 3. 部分和
vector<int> partialSum(5);
partial_sum(v.begin(), v.end(), partialSum.begin());
// partialSum = {1, 3, 6, 10, 15}
// 4. 相邻差
vector<int> diff(5);
adjacent_difference(v.begin(), v.end(), diff.begin());
// diff = {1, 1, 1, 1, 1}
// 5. 最大公约数和最小公倍数（C++17）
int g = __gcd(12, 18); // 6
// int l = lcm(12, 18); // 36 (C++17)
}
1.4 字符串处理
1.4.1 string 基础
#include <string>
#include <sstream>
#include <cctype>
using namespace std;
void stringBasics() {
// 1. 初始化
string s1;
string s2 = "Hello";
string s3("World");
string s4(5, 'a'); // "aaaaa"
string s5 = s2;
// 2. 拼接
string s = s2 + " " + s3;
s += "!";
s.append(" Nice");
// 3. 访问
char c = s[0];
char c2 = s.at(0);
// 4. 修改
s[0] = 'h';
// 5. 子串
string sub = s.substr(0, 5); // 从位置0开始，长度5
string sub2 = s.substr(6); // 从位置6到末尾
// 6. 查找
size_t pos = s.find("World");
if (pos != string::npos) {
cout << "找到了，位置：" << pos << endl;
}
size_t pos2 = s.rfind("o"); // 从后往前找
size_t pos3 = s.find_first_of("aeiou"); // 找第一个元音
size_t pos4 = s.find_last_of("aeiou"); // 找最后一个元音
// 7. 替换
s.replace(0, 5, "Hi"); // 替换[0, 5)为"Hi"
// 8. 插入和删除
s.insert(2, "XXX");
s.erase(2, 3); // 删除位置2开始的3个字符
// 9. 比较
if (s1 == s2) {}
int cmp = s1.compare(s2); // <0: s1<s2, =0: 相等, >0: s1>s2
// 10. 大小
size_t len = s.length(); // 或 s.size()
bool empty = s.empty();
s.clear();
// 11. 转换
string num = "123";
int n = stoi(num);
long long ll = stoll(num);
double d = stod("3.14");
string str = to_string(123);
}
// 字符串分割
vector<string> split(const string& s, char delimiter) {
vector<string> tokens;
stringstream ss(s);
string token;
while (getline(ss, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}
// 字符串处理常用函数
void charFunctions() {
char c = 'a';
isalpha(c); // 是否是字母
isdigit(c); // 是否是数字
isalnum(c); // 是否是字母或数字
isspace(c); // 是否是空白字符
isupper(c); // 是否是大写
islower(c); // 是否是小写
toupper(c); // 转大写
tolower(c); // 转小写
}
// KMP字符串匹配
vector<int> getNext(const string& pattern) {
int m = pattern.length();
vector<int> next(m);
next[0] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
int kmp(const string& text, const string& pattern) {
vector<int> next = getNext(pattern);
int n = text.length(), m = pattern.length();
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
return i - m + 1; // 找到了
}
}
return -1; // 未找到
}
第二章：算法基础
2.1 时间复杂度详解
2.1.1 理论基础
大O记号规则
// O(1) - 常数时间
int getFirst(vector<int>& arr) {
return arr[0]; // 无论数组多大，只需一次操作
}
// O(log n) - 对数时间
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 每次减半，n -> n/2 -> n/4 -> ... -> 1
// 需要 log₂(n) 次
// O(n) - 线性时间
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) return i;
}
return -1;
}
// O(n log n) - 线性对数时间
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // T(n/2)
mergeSort(arr, mid + 1, right); // T(n/2)
merge(arr, left, mid, right); // O(n)
}
// T(n) = 2T(n/2) + O(n) = O(n log n)
// O(n²) - 平方时间
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) { // n次
for (int j = 0; j < n - i - 1; j++) { // 平均n/2次
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
// n * n/2 = n²/2 = O(n²)
// O(2^n) - 指数时间
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// T(n) = T(n-1) + T(n-2) ≈ O(2^n)
复杂度计算规则
// 规则1：忽略常数
void f1(int n) {
for (int i = 0; i < n; i++) {} // O(n)
for (int i = 0; i < n; i++) {} // O(n)
for (int i = 0; i < n; i++) {} // O(n)
}
// 总共 3n，但记为 O(n)
// 规则2：忽略低阶项
void f2(int n) {
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n²)
}
}
for (int i = 0; i < n; i++) {} // O(n)
}
// n² + n，但记为 O(n²)
// 规则3：相乘而非相加
void f3(int n, int m) {
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < m; j++) { // O(m)
}
}
}
// O(n * m)，不能简化
// 规则4：递归复杂度 = 递归深度 × 每次操作
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
// 深度 n，每次 O(1)，总共 O(n)
2.1.2 常见算法复杂度
| 复杂度 | n的范围 | 算法示例 |
|---|---|---|
| O(1) | 无限制 | 哈希表查找、数组索引访问 |
| O(log n) | n ≤ 10¹⁸ | 二分查找、平衡树操作 |
| O(√n) | n ≤ 10¹⁴ | 质数判定、分解因数 |
| O(n) | n ≤ 10⁸ | 线性查找、一次遍历 |
| O(n log n) | n ≤ 5×10⁶ | 归并排序、快速排序、堆排序 |
| O(n²) | n ≤ 10⁴ | 冒泡排序、插入排序、两层循环 |
| O(n³) | n ≤ 500 | Floyd算法、三层循环 |
| O(2^n) | n ≤ 25 | 枚举所有子集、暴力搜索 |
| O(n!) | n ≤ 11 | 全排列、旅行商问题（暴力） |
实战技巧
// 根据数据范围选择算法
void solveByConstraint(int n) {
if (n <= 11) {
// 可以用 O(n!) 的算法，如全排列
nextPermutation();
} else if (n <= 25) {
// 可以用 O(2^n) 的算法，如枚举子集
enumerateSubsets();
} else if (n <= 10000) {
// 可以用 O(n²) 的算法
bubbleSort();
} else if (n <= 5000000) {
// 需要 O(n log n) 的算法
sort();
} else {
// 需要 O(n) 或更优的算法
linearScan();
}
}
2.2 排序算法详解
2.2.1 冒泡排序（Bubble Sort）
原理：重复遍历数组，比较相邻元素，如果顺序错误就交换
template<typename T>
void bubbleSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 优化：记录是否发生交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 没有交换说明已排序
}
}
复杂度分析
时间复杂度：最好O(n)，平均O(n²)，最坏O(n²)空间复杂度：O(1)稳定性：稳定
优缺点
✅ 简单易懂✅ 稳定排序❌ 效率低，不适合大数据
2.2.2 选择排序（Selection Sort）
原理：每次从未排序部分选择最小元素，放到已排序部分末尾
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}
}
复杂度分析
时间复杂度：O(n²)（无论什么情况）空间复杂度：O(1)稳定性：不稳定
2.2.3 插入排序（Insertion Sort）
原理：将元素插入到已排序部分的正确位置
template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
T key = arr[i];
int j = i - 1;
// 将比key大的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 二分插入排序（优化查找位置）
template<typename T>
void binaryInsertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
T key = arr[i];
// 二分查找插入位置
int left = 0, right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 移动元素
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
复杂度分析
时间复杂度：最好O(n)，平均O(n²)，最坏O(n²)空间复杂度：O(1)稳定性：稳定
特点
对于小规模数据或基本有序的数据，效率很高STL的sort在小数据时会切换到插入排序
2.2.4 归并排序（Merge Sort）
原理：分治法，分为两半分别排序，然后合并
template<typename T>
void merge(T arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
T* L = new T[n1];
T* R = new T[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
// 合并
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
delete[] L;
delete[] R;
}
template<typename T>
void mergeSort(T arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
复杂度分析
时间复杂度：O(n log n)（所有情况）空间复杂度：O(n)稳定性：稳定
应用：求逆序对数量
long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
long long count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i++]);
} else {
temp.push_back(arr[j++]);
count += (mid - i + 1); // 逆序对数量
}
}
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
for (int i = 0; i < temp.size(); i++) {
arr[left + i] = temp[i];
}
return count;
}
long long countInversions(vector<int>& arr, int left, int right) {
long long count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += countInversions(arr, left, mid);
count += countInversions(arr, mid + 1, right);
count += mergeAndCount(arr, left, mid, right);
}
return count;
}
2.2.5 快速排序（Quick Sort）
原理：选择基准元素，将小于基准的放左边，大于的放右边，递归处理
template<typename T>
int partition(T arr[], int low, int high) {
T pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
template<typename T>
void quickSort(T arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 优化版本1：随机选择基准
template<typename T>
int randomizedPartition(T arr[], int low, int high) {
int random = low + rand() % (high - low + 1);
swap(arr[random], arr[high]);
return partition(arr, low, high);
}
// 优化版本2：三数取中
template<typename T>
int medianOfThree(T arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
if (arr[low] > arr[high]) swap(arr[low], arr[high]);
if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
swap(arr[mid], arr[high]);
return partition(arr, low, high);
}
// 优化版本3：三路快排（处理大量重复元素）
template<typename T>
void quickSort3Way(T arr[], int low, int high) {
if (low >= high) return;
int lt = low, gt = high;
T pivot = arr[low];
int i = low + 1;
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr[i++], arr[lt++]);
} else if (arr[i] > pivot) {
swap(arr[i], arr[gt--]);
} else {
i++;
}
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
复杂度分析
时间复杂度：最好O(n log n)，平均O(n log n)，最坏O(n²)空间复杂度：O(log n)（递归栈）稳定性：不稳定
注意：实际比赛中建议直接使用STL的sort函数
2.2.6 堆排序（Heap Sort）
原理：利用堆的性质进行排序
template<typename T>
void heapify(T arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
template<typename T>
void heapSort(T arr[], int n) {
// 建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
复杂度分析
时间复杂度：O(n log n)（所有情况）空间复杂度：O(1)稳定性：不稳定
2.2.7 计数排序（Counting Sort）
原理：统计每个值出现的次数，适用于范围小的整数
void countingSort(vector<int>& arr) {
if (arr.empty()) return;
int maxVal = *max_element(arr.begin(), arr.end());
int minVal = *min_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;
vector<int> count(range, 0);
vector<int> output(arr.size());
// 统计
for (int num : arr) {
count[num - minVal]++;
}
// 累加
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 输出
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - minVal] - 1] = arr[i];
count[arr[i] - minVal]--;
}
arr = output;
}
复杂度分析
时间复杂度：O(n + k)，k为数值范围空间复杂度：O(k)稳定性：稳定
适用场景：数值范围不大（如0-100）的整数排序
2.2.8 基数排序（Radix Sort）
原理：按位数排序，从低位到高位
void countingSortForRadix(vector<int>& arr, int exp) {
vector<int> output(arr.size());
vector<int> count(10, 0);
for (int num : arr) {
count[(num / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
arr = output;
}
void radixSort(vector<int>& arr) {
if (arr.empty()) return;
int maxVal = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
countingSortForRadix(arr, exp);
}
}
复杂度分析
时间复杂度：O(d(n + k))，d为位数，k为基数空间复杂度：O(n + k)稳定性：稳定
2.3 查找算法详解
2.3.1 线性查找
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
2.3.2 二分查找详解
基础二分
// 查找target的位置
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
左边界二分（第一个>=target的位置）
int lowerBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
右边界二分（第一个>target的位置）
int upperBound(vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
二分答案模板
// 最大化最小值
int maxMinValue(/* 参数 */) {
int left = minPossible, right = maxPossible;
int ans = left;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) { // mid可行
ans = mid;
left = mid + 1; // 尝试更大的
} else {
right = mid - 1;
}
}
return ans;
}
// 最小化最大值
int minMaxValue(/* 参数 */) {
int left = minPossible, right = maxPossible;
int ans = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) { // mid可行
ans = mid;
right = mid - 1; // 尝试更小的
} else {
left = mid + 1;
}
}
return ans;
}
应用示例
// 1. 在旋转数组中查找
int searchRotated(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;
}
// 2. 找峰值
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]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// 3. 平方根（整数部分）
int mySqrt(int x) {
if (x == 0) return 0;
int left = 1, right = x;
int ans = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) { // 避免溢出
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
2.4 递归与分治
2.4.1 递归基础
递归三要素
基本情况（Base Case）：递归终止条件递归关系（Recursive Relation）：问题如何分解递归前进（Progress）：每次递归都向基本情况靠近
// 示例1：阶乘
int factorial(int n) {
// 基本情况
if (n == 0 || n == 1) {
return 1;
}
// 递归关系
return n * factorial(n - 1);
}
// 示例2：斐波那契
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 优化：记忆化
map<int, int> memo;
int fibMemo(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}
// 示例3：汉诺塔
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
hanoi(n - 1, from, aux, to);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, aux, to, from);
}
第三章：数据结构进阶
3.1 链表（Linked List）
3.1.1 单链表
基本结构
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
基本操作
class LinkedList {
private:
ListNode* head;
public:
LinkedList() : head(nullptr) {}
// 在头部插入
void insertAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
}
// 在尾部插入
void insertAtTail(int val) {
ListNode* newNode = new ListNode(val);
if (!head) {
head = newNode;
return;
}
ListNode* curr = head;
while (curr->next) {
curr = curr->next;
}
curr->next = newNode;
}
// 在指定位置插入
void insertAt(int index, int val) {
if (index == 0) {
insertAtHead(val);
return;
}
ListNode* curr = head;
for (int i = 0; i < index - 1 && curr; i++) {
curr = curr->next;
}
if (!curr) return;
ListNode* newNode = new ListNode(val);
newNode->next = curr->next;
curr->next = newNode;
}
// 删除节点
void deleteNode(int val) {
if (!head) return;
if (head->val == val) {
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
ListNode* curr = head;
while (curr->next && curr->next->val != val) {
curr = curr->next;
}
if (curr->next) {
ListNode* temp = curr->next;
curr->next = curr->next->next;
delete temp;
}
}
// 查找节点
bool search(int val) {
ListNode* curr = head;
while (curr) {
if (curr->val == val) return true;
curr = curr->next;
}
return false;
}
// 反转链表
void reverse() {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
// 打印链表
void print() {
ListNode* curr = head;
while (curr) {
cout << curr->val << " -> ";
curr = curr->next;
}
cout << "nullptr" << endl;
}
};
经典问题
// 1. 检测环
bool hasCycle(ListNode* head) {
if (!head || !head->next) return false;
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
// 2. 找环的入口
ListNode* detectCycle(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
// 判断是否有环
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return nullptr;
// 找入口
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
// 3. 找中间节点
ListNode* findMiddle(ListNode* head) {
if (!head) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 4. 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
// 5. 删除倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* first = &dummy;
ListNode* second = &dummy;
// first先走n+1步
for (int i = 0; i <= n; i++) {
first = first->next;
}
// 一起走到底
while (first) {
first = first->next;
second = second->next;
}
// 删除节点
ListNode* temp = second->next;
second->next = second->next->next;
delete temp;
return dummy.next;
}
3.2 树（Tree）
3.2.1 二叉树基础
基本结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
三种遍历方式
// 1. 前序遍历（根-左-右）
void preorderTraversal(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 非递归版本
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;
}
// 2. 中序遍历（左-根-右）
void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 非递归版本
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;
}
// 3. 后序遍历（左-右-根）
void postorderTraversal(TreeNode* root) {
if (!root) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
// 4. 层序遍历（BFS）
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;
}
常见问题
// 1. 树的深度
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
// 2. 判断是否对称
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return (t1->val == t2->val) &&
isMirror(t1->left, t2->right) &&
isMirror(t1->right, t2->left);
}
// 3. 路径总和
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
if (!root->left && !root->right) {
return targetSum == root->val;
}
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}
// 4. 最近公共祖先（LCA）
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;
}
// 5. 二叉树直径
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
height(root, diameter);
return diameter;
}
int height(TreeNode* node, int& diameter) {
if (!node) return 0;
int left = height(node->left, diameter);
int right = height(node->right, diameter);
diameter = max(diameter, left + right);
return 1 + max(left, right);
}
3.2.2 二叉搜索树（BST）
性质
左子树所有节点值 < 根节点值右子树所有节点值 > 根节点值中序遍历结果为升序
基本操作
class BST {
private:
TreeNode* root;
TreeNode* insertHelper(TreeNode* node, int val) {
if (!node) return new TreeNode(val);
if (val < node->val) {
node->left = insertHelper(node->left, val);
} else if (val > node->val) {
node->right = insertHelper(node->right, val);
}
return node;
}
TreeNode* searchHelper(TreeNode* node, int val) {
if (!node || node->val == val) return node;
if (val < node->val) {
return searchHelper(node->left, val);
}
return searchHelper(node->right, val);
}
TreeNode* deleteHelper(TreeNode* node, int val) {
if (!node) return nullptr;
if (val < node->val) {
node->left = deleteHelper(node->left, val);
} else if (val > node->val) {
node->right = deleteHelper(node->right, val);
} else {
// 找到要删除的节点
if (!node->left) {
TreeNode* temp = node->right;
delete node;
return temp;
} else if (!node->right) {
TreeNode* temp = node->left;
delete node;
return temp;
}
// 两个子节点都存在：找右子树最小值
TreeNode* temp = findMin(node->right);
node->val = temp->val;
node->right = deleteHelper(node->right, temp->val);
}
return node;
}
TreeNode* findMin(TreeNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
public:
BST() : root(nullptr) {}
void insert(int val) {
root = insertHelper(root, val);
}
bool search(int val) {
return searchHelper(root, val) != nullptr;
}
void remove(int val) {
root = deleteHelper(root, val);
}
};
// 验证BST
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
bool validate(TreeNode* node, long minVal, long maxVal) {
if (!node) return true;
if (node->val <= minVal || node->val >= maxVal) {
return false;
}
return validate(node->left, minVal, node->val) &&
validate(node->right, node->val, maxVal);
}
3.3 并查集（Union-Find）
基本思想：管理一系列不相交的集合，支持合并和查询操作
实现
class UnionFind {
private:
vector<int> parent;
vector<int> rank; // 秩（树的高度）
int count; // 连通分量个数
public:
UnionFind(int n) : count(n) {
parent.resize(n);
rank.resize(n, 0);
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) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
}
}
// 判断是否连通
bool connected(int x, int y) {
return find(x) == find(y);
}
// 获取连通分量个数
int getCount() {
return count;
}
};
// 应用：朋友圈问题
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
UnionFind uf(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j]) {
uf.unite(i, j);
}
}
}
return uf.getCount();
}
3.4 图（Graph）
3.4.1 图的表示
邻接矩阵
class GraphMatrix {
private:
vector<vector<int>> adj;
int V; // 顶点数
public:
GraphMatrix(int vertices) : V(vertices) {
adj.resize(V, vector<int>(V, 0));
}
void addEdge(int u, int v, int weight = 1) {
adj[u][v] = weight;
adj[v][u] = weight; // 无向图
}
void print() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adj[i][j] << " ";
}
cout << endl;
}
}
};
邻接表
class GraphList {
private:
vector<vector<int>> adj;
int V;
public:
GraphList(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 无向图
}
void print() {
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (int v : adj[i]) {
cout << v << " ";
}
cout << endl;
}
}
};
// 带权重的邻接表
class WeightedGraph {
private:
vector<vector<pair<int, int>>> adj; // {邻接点, 权重}
int V;
public:
WeightedGraph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v, int weight) {
adj[u].push_back({v, weight});
adj[v].push_back({u, weight});
}
};
3.4.2 图的遍历
深度优先搜索（DFS）
class Graph {
private:
vector<vector<int>> adj;
int V;
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
DFSUtil(u, visited);
}
}
}
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void DFS(int start) {
vector<bool> visited(V, false);
DFSUtil(start, visited);
}
// DFS遍历所有连通分量
void DFSAll() {
vector<bool> visited(V, false);
for (int i = 0; i < V; i++) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
};
// 非递归DFS
void DFSIterative(vector<vector<int>>& adj, int start) {
int V = adj.size();
vector<bool> visited(V, false);
stack<int> st;
st.push(start);
while (!st.empty()) {
int v = st.top();
st.pop();
if (!visited[v]) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
st.push(u);
}
}
}
}
}
广度优先搜索（BFS）
void BFS(vector<vector<int>>& adj, int start) {
int V = adj.size();
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
}
// BFS求最短路径
int shortestPath(vector<vector<int>>& adj, int start, int end) {
int V = adj.size();
vector<int> dist(V, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
if (v == end) return dist[end];
for (int u : adj[v]) {
if (dist[u] == -1) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
return -1;
}
第四章：算法进阶
4.1 动态规划（Dynamic Programming）
4.1.1 动态规划基础
基本思想
将问题分解为子问题存储子问题的解（避免重复计算）从子问题的解构建原问题的解
解题步骤
定义状态找状态转移方程确定初始状态和边界确定计算顺序
4.1.2 线性DP
1. 斐波那契数列
// 方法1：记忆化搜索
int fib(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
// 方法2：自底向上DP
int fib(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// 方法3：空间优化
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
2. 爬楼梯
// 每次可以爬1或2个台阶，n个台阶有多少种方法
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
3. 最大子数组和
// Kadane算法
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
// DP版本
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(nums[i], dp[i-1] + nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
4. 最长递增子序列（LIS）
// O(n²) 解法
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
// O(n log n) 解法（贪心+二分）
int lengthOfLIS(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();
}
4.1.3 背包问题
1. 0/1背包
// 物品只能选一次
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i-1] <= w) {
dp[i][w] = max(dp[i-1][w],
dp[i-1][w - weights[i-1]] + values[i-1]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][capacity];
}
// 空间优化版本
int knapsack01Optimized(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];
}
2. 完全背包
// 物品可以选无限次
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];
}
3. 多重背包
// 每个物品有数量限制
int knapsackMultiple(vector<int>& weights, vector<int>& values,
vector<int>& counts, int capacity) {
int n = weights.size();
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
for (int k = 0; k < counts[i]; k++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
}
return dp[capacity];
}
// 二进制优化
int knapsackMultipleOptimized(vector<int>& weights, vector<int>& values,
vector<int>& counts, int capacity) {
vector<int> newWeights, newValues;
// 二进制拆分
for (int i = 0; i < weights.size(); i++) {
int num = counts[i];
for (int k = 1; k <= num; k *= 2) {
newWeights.push_back(k * weights[i]);
newValues.push_back(k * values[i]);
num -= k;
}
if (num > 0) {
newWeights.push_back(num * weights[i]);
newValues.push_back(num * values[i]);
}
}
// 转化为0/1背包
return knapsack01Optimized(newWeights, newValues, capacity);
}
4.1.4 区间DP
1. 最长回文子串
string longestPalindrome(string s) {
int n = s.length();
if (n < 2) return s;
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;
}
// 长度为2的子串
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i+1]) {
dp[i][i+1] = true;
start = i;
maxLen = 2;
}
}
// 长度>=3的子串
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = true;
start = i;
maxLen = len;
}
}
}
return s.substr(start, maxLen);
}
2. 矩阵链乘法
// 求最少乘法次数
int matrixChainOrder(vector<int>& dims) {
int n = dims.size() - 1;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] +
dims[i] * dims[k+1] * dims[j+1];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}
4.2 贪心算法（Greedy Algorithm）
4.2.1 基本思想
贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。
特点
局部最优 → 全局最优不回溯效率高
适用条件
最优子结构贪心选择性质
4.2.2 经典问题
1. 活动选择问题
// 选择最多的不重叠活动
int activitySelection(vector<pair<int, int>>& activities) {
// 按结束时间排序
sort(activities.begin(), activities.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
});
int count = 1;
int lastEnd = activities[0].second;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].first >= lastEnd) {
count++;
lastEnd = activities[i].second;
}
}
return count;
}
2. 找零钱问题
// 使用最少的硬币数
int coinChange(vector<int>& coins, int amount) {
sort(coins.rbegin(), coins.rend()); // 降序
int count = 0;
for (int coin : coins) {
while (amount >= coin) {
amount -= coin;
count++;
}
}
return amount == 0 ? count : -1;
}
3. 区间覆盖问题
// 最少区间覆盖
int minIntervalsToCover(vector<pair<int, int>>& intervals, int target) {
sort(intervals.begin(), intervals.end());
int count = 0;
int currentEnd = 0;
int i = 0;
while (currentEnd < target) {
int maxEnd = currentEnd;
while (i < intervals.size() && intervals[i].first <= currentEnd) {
maxEnd = max(maxEnd, intervals[i].second);
i++;
}
if (maxEnd == currentEnd) return -1; // 无法覆盖
count++;
currentEnd = maxEnd;
}
return count;
}
4. 跳跃游戏
// 判断能否到达最后一个位置
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]);
if (maxReach >= nums.size() - 1) return true;
}
return false;
}
// 最少跳跃次数
int jump(vector<int>& nums) {
int jumps = 0;
int currentEnd = 0;
int maxReach = 0;
for (int i = 0; i < nums.size() - 1; i++) {
maxReach = max(maxReach, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = maxReach;
}
}
return jumps;
}
4.3 搜索算法
4.3.1 深度优先搜索（DFS）
全排列
void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); i++) {
swap(nums[start], nums[i]);
permute(nums, start + 1, result);
swap(nums[start], nums[i]); // 回溯
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
permute(nums, 0, result);
return result;
}
子集生成
void subsets(vector<int>& nums, int start,
vector<int>& current, vector<vector<int>>& result) {
result.push_back(current);
for (int i = start; i < nums.size(); i++) {
current.push_back(nums[i]);
subsets(nums, i + 1, current, result);
current.pop_back(); // 回溯
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
subsets(nums, 0, current, result);
return result;
}
N皇后问题
bool isSafe(vector<string>& board, int row, int col, int n) {
// 检查列
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 < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
void solveNQueens(int n, int row, vector<string>& board,
vector<vector<string>>& result) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q';
solveNQueens(n, row + 1, board, result);
board[row][col] = '.'; // 回溯
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<string> board(n, string(n, '.'));
solveNQueens(n, 0, board, result);
return result;
}
4.3.2 广度优先搜索（BFS）
单词接龙
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (wordSet.find(endWord) == wordSet.end()) return 0;
queue<pair<string, int>> q;
q.push({beginWord, 1});
while (!q.empty()) {
auto [word, level] = q.front();
q.pop();
if (word == endWord) return level;
for (int i = 0; i < word.length(); i++) {
string temp = word;
for (char c = 'a'; c <= 'z'; c++) {
temp[i] = c;
if (wordSet.count(temp)) {
q.push({temp, level + 1});
wordSet.erase(temp);
}
}
}
}
return 0;
}
4.4 最短路径算法
4.4.1 Dijkstra算法（单源最短路）
vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
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});
}
}
}
return dist;
}
4.4.2 Floyd算法（多源最短路）
void floyd(vector<vector<int>>& dist) {
int n = dist.size();
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
第五章：计算机基础
5.1 计算机组成
5.1.1 冯·诺依曼体系结构
五大组成部分
运算器（ALU）：执行算术和逻辑运算控制器：指挥各部件协调工作存储器：存储程序和数据输入设备：接收外部信息输出设备：输出处理结果
工作原理
程序和数据存储在内存中指令按顺序执行采用二进制编码
5.2 数制与编码
5.2.1 进制转换
// 十进制转其他进制
string decimalToBase(int num, int base) {
if (num == 0) return "0";
string result;
string digits = "0123456789ABCDEF";
while (num > 0) {
result = digits[num % base] + result;
num /= base;
}
return result;
}
// 其他进制转十进制
int baseToDecimal(string num, int base) {
int result = 0;
int power = 1;
for (int i = num.length() - 1; i >= 0; i--) {
int digit;
if (num[i] >= '0' && num[i] <= '9') {
digit = num[i] - '0';
} else {
digit = num[i] - 'A' + 10;
}
result += digit * power;
power *= base;
}
return result;
}
5.2.2 原码、反码、补码
// 获取一个数的补码表示
string getComplement(int num, int bits = 32) {
unsigned int un = num; // 按位模式
string result;
for (int i = bits - 1; i >= 0; i--) {
result += ((un >> i) & 1) ? '1' : '0';
}
return result;
}
5.3 历史与人物
重要里程碑
1946年：ENIAC，世界第一台电子计算机1947年：晶体管发明1958年：集成电路发明1971年：第一个微处理器Intel 4004
重要人物
冯·诺依曼（匈牙利）：计算机之父，提出冯·诺依曼体系结构图灵（英国）：人工智能之父，提出图灵机模型Ada Lovelace（英国）：世界上第一位程序员
第六章：操作系统
6.1 操作系统基础
6.1.1 主要功能
进程管理
进程创建、调度、同步进程间通信
内存管理
内存分配与回收虚拟内存分页、分段
文件系统
文件组织文件读写权限管理
设备管理
设备驱动I/O调度
6.2 进程与线程
6.2.1 区别
| 特性 | 进程 | 线程 |
|---|---|---|
| 定义 | 资源分配的基本单位 | CPU调度的基本单位 |
| 资源 | 独立的地址空间 | 共享进程资源 |
| 开销 | 创建、切换开销大 | 开销小 |
| 通信 | 需要IPC机制 | 直接访问共享内存 |
6.3 内存管理
6.3.1 虚拟内存
优点
逻辑地址空间可以大于物理内存多个程序可以并发运行提高内存利用率
页面置换算法
FIFO：先进先出LRU：最近最少使用Clock：时钟算法
第七章：网络与数据库
7.1 网络基础
7.1.1 TCP/IP协议
四层模型
应用层：HTTP、FTP、SMTP等传输层：TCP、UDP网络层：IP、ICMP链路层：以太网、WiFi
TCP vs UDP
| 特性 | TCP | UDP |
|---|---|---|
| 连接 | 面向连接 | 无连接 |
| 可靠性 | 可靠传输 | 不可靠 |
| 速度 | 较慢 | 快 |
| 应用 | HTTP、FTP | DNS、视频流 |
7.2 数据库基础
7.2.1 SQL基本操作
-- 创建表
CREATE TABLE students (
id INT PRIMARY KEY,
name VARCHAR(50),
score INT
);
-- 插入数据
INSERT INTO students VALUES (1, 'Alice', 90);
-- 查询数据
SELECT * FROM students WHERE score > 80;
-- 更新数据
UPDATE students SET score = 95 WHERE id = 1;
-- 删除数据
DELETE FROM students WHERE id = 1;
第八章：软件工程
8.1 软件开发模型
8.1.1 瀑布模型
阶段
需求分析系统设计编码实现系统测试部署运维
特点
线性顺序文档驱动适合需求明确的项目
8.1.2 敏捷开发
核心价值观
个体和互动 > 流程和工具工作的软件 > 详尽的文档客户合作 > 合同谈判响应变化 > 遵循计划
常见方法
ScrumXP（极限编程）Kanban
8.2 设计模式
8.2.1 单例模式
class Singleton {
private:
static Singleton* instance;
Singleton() {} // 私有构造函数
public:
static Singleton* getInstance() {
if (instance == nullptr) {
instance = new Singleton();
}
return instance;
}
};
Singleton* Singleton::instance = nullptr;
8.2.2 工厂模式
class Product {
public:
virtual void use() = 0;
};
class ConcreteProductA : public Product {
public:
void use() override {
cout << "Using Product A" << endl;
}
};
class Factory {
public:
static Product* createProduct(string type) {
if (type == "A") {
return new ConcreteProductA();
}
return nullptr;
}
};
8.3 测试方法
8.3.1 测试类型
单元测试：测试最小可测试单元集成测试：测试模块间的接口系统测试：测试整个系统验收测试：用户验收
总结
本文档详细介绍了CSP-J涉及的所有核心知识点：
编程基础
C++语法、STL容器和算法数据类型、运算符、控制结构
算法
排序、查找、递归动态规划、贪心、搜索图论算法
数据结构
线性结构：数组、链表、栈、队列树形结构：二叉树、BST图和并查集
计算机基础
计算机组成、数制转换操作系统、网络、数据库软件工程
学习建议
循序渐进：先掌握基础，再学习进阶多做题目：理论结合实践总结归纳：整理常见模板和技巧时间管理：根据数据范围选择合适算法
推荐学习路径
基础语法 → STL → 基础算法（排序、查找）
↓
数据结构（栈、队列、树）→ 图论基础
↓
动态规划 → 贪心 → 搜索算法
↓
综合应用 → 模拟练习
祝你在CSP-J考试中取得好成绩！
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
暂无评论...
