C++算法之旅、05 基础篇 | 第二章 数据结构
常用代码模板2——数据结构 - AcWing笔试用数组模拟而不是结构体
使用结构体指针，new Node() 非常慢，创建10万个节点就超时了，做笔试题不会用这种方式（优化是提前初始化好数组，但这样跟数组模拟没区别了，而且代码量很长）
单链表（数组）
使用两个数组，e存储val，ne存储next。空节点next用-1表示
https://linxiaoxu.oss-cn-hangzhou.aliyuncs.com/static/pic/2023/09/20230902031557_image-20230902031545710.png826 ⭐
826. 单链表 - AcWing题库
第1个插入的点下标为0，第5个插入点下标为4，第k个插入点下标为k-1；
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// head指向头结点，e表示节点值，ne表示节点next
// idx指向可用空间（当前可以用的最新点下标）
// 算法题不用考虑浪费的空间
int head, e, ne, idx;
void init() {
head = -1;
idx = 0;
}
// x 插到头结点后面
void add_to_head(int x) {
e = x;
ne = head;
head = idx++;
}
// x 插到下标k的点后面
void add(int k, int x) {
e = x;
ne = ne;
ne = idx++;
}
// 将下标 k 后面点删掉
void remove(int k) {
// if (ne == -1) return; 题目保证合法不考虑边界情况
ne = ne];
}
int main() {
int m;
cin >> m;
init();
while (m--) {
char c;
int k, x;
cin >> c;
if (c == 'H') {
cin >> x;
add_to_head(x);
} else if (c == 'D') {
cin >> k;
if (!k)
head = ne;// 特判删除头结点(链表第一个有效元素)
else
remove(k - 1);
} else if (c == 'I') {
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne) {
cout << e << " ";
}
return 0;
}
837 ⭐⭐
837. 连通块中点的数量 - AcWing题库
保证根节点的nums有意义
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e, l, r, idx;
void init() {
r = 1;
l = 0;
idx = 2;
}
// 在下标k点的右边插入x（可以转化成左边）
void add(int k, int x) {
e = x;
r = r;
l = k;
r = idx;
l] = idx;
idx++;
}
// 删除下标k的点
void remove(int k) {
l] = l;
r] = r;
}
int main() {
int m;
cin >> m;
init();
while (m--) {
string s;
int k, x;
cin >> s;
if (s == "L") {
cin >> x;
add(0, x);
} else if (s == "R") {
cin >> x;
add(l, x);
} else if (s == "D") {
cin >> k;
remove(k - 1 + 2);
} else if (s == "IL") {
cin >> k >> x;
add(l, x);
} else if (s == "IR") {
cin >> k >> x;
add(k - 1 + 2, x);
}
}
for (int i = r; i != 1; i = r) {
cout << e << " ";
}
return 0;
}
哈希表
情景
[*]把 1e5 个值域 -1e9~1e9 的数（值域大，个数少）映射到 1e5 的范围的哈希函数
[*]\(h(x) \in (0,1e5) = x\ mod\ 1e5\)模数一般要取质数，离2的整数幂尽可能远
[*]发生冲突：两个不同值域的数映射成了同一个数
存储结构-解决冲突的方式 ⭐
算法题99%一般只有添加、查找，若要实现删除不会真删掉，开一个bool数组标记删除
[*]开放寻址法（常用）
[*]开一个一维数组，范围是题目数据范围的2~3倍，即 2e5 ~ 3e5 区间的质数，该数组存储实际的 x 值
[*]计算哈希值，如果哈希值已被占用，则移动到下一个位置，从前往后找
[*]h(11) = 3 在 数组 存入 11，h(4) = 3 在数组 存入 4
[*]与拉链法不同，查询函数返回 x 所在的位置，如果 x 不存在返回应该存储的位置
[*]需要约定一个标志，不在 x 的值域范围内，表示当前位置为空，如 0x3f3f3f3f
[*]拉链法
[*]开一个一维数组 \(\) 存储所有哈希值对应的链表
[*]h(11) = 3 在 数组 开一条链，插入 11
[*]若 h(4) = 3 在 数组 已开的链插入 4
[*]期望情况下，每条链长度 1，时间复杂度 \(O(1)\)
字符串哈希-字符串前缀哈希法（特殊）
应用：可以快速判断一个字符串某两段是否相同。KMP望而却步（KMP擅长循环节），极困难题可用这种方法
[*]先预处理所有前缀的哈希，h = 0, h = "A" 的hash，h = "AB" 的hash...
[*]把字符串看成 P 进制的数，然后模 Q
https://linxiaoxu.oss-cn-hangzhou.aliyuncs.com/static/pic/2023/09/20230903101720_image-20230903101708987.png
[*]**某个字符不能映射成 0，否则 AA 跟 A 两个哈希都是 0 **
[*]该哈希法假定人品足够好，不考虑冲突
[*]经验值：当 p = 131 或 13331，Q 取 \(2^{64}\) (用 unsinged long long可以不取模，溢出相当于取模)
⭐ 我们可以利用前缀哈希算出任意子段的哈希值
[*]预处理前缀 h(i) = h(i-1) * p + str
https://linxiaoxu.oss-cn-hangzhou.aliyuncs.com/static/pic/2023/09/20230903110155_image-20230903110147424.png
与整数离散化的区别
整数离散化需要保序，而且不会发生冲突，每一个元素都有唯一确定的位置（1 ~ n）
840 ⭐拉链法
840. 模拟散列表 - AcWing题库
h 数组维护 N 条链，空节点表示-1，e 数组与 ne 数组维护链上的每一个节点，idx为每个节点分配唯一标识符；插入操作从链表头结点插入
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int stk, tt;
int main() {
int m;
cin >> m;
while (m--) {
string s;
int x;
cin >> s;
if (s == "push") {
cin >> x;
stk[++tt] = x;
} else if (s == "pop") {
tt--;
} else if (s == "empty") {
if (tt > 0)
puts("NO");
else
puts("YES");
} else if (s == "query") {
cout << stk << endl;
}
}
return 0;
}
840 ⭐开放寻址法
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
int op, num, opt = -1, numt = -1;
unordered_map<char, int> priority;
// 计算后缀表达式
void eval() {
auto b = num;
auto a = num;
auto c = op;
int res;
if (c == '-')
res = a - b;
else if (c == '+')
res = a + b;
else if (c == '*')
res = a * b;
else if (c == '/')
res = a / b;
num[++numt] = res;
}
int main() {
priority = {{'-', 1}, {'+', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (isdigit(str)) {
int j = i, res = 0;
while (isdigit(str)) res = res * 10 + str - '0';
num[++numt] = res;
i = j - 1;
} else if (str == '(')
op[++opt] = str;
else if (str == ')') {
while (op != '(') eval();
opt--;
} else {
while (opt >= 0 && priority] <= priority]) eval();
op[++opt] = str;
}
}
while (opt >= 0) eval();
cout << num;
return 0;
}
841 ⭐⭐ 字符串哈希
841. 字符串哈希 - AcWing题库
如下的朴素算法会超时
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void eval() {
auto b = num.top();
num.pop();
auto a = num.top();
num.pop();
auto c = op.top();
op.pop();
int x;
if (c == '+')
x = a + b;
else if (c == '-')
x = a - b;
else if (c == '*')
x = a * b;
else
x = a / b;
num.push(x);
}
int main() {
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; i < str.size(); i++) {
auto c = str;
if (isdigit(c)) {
// 第一类双指针
int x = 0, j = i;
while (j < str.size() && isdigit(str))
x = x * 10 + str - '0';
i = j - 1;// 考虑i++
num.push(x);
} else if (c == '(')
op.push(c);
else if (c == ')') {
while (op.top() != '(') eval();
op.pop();
} else {
while (op.size() && pr >= pr) eval();
op.push(c);
}
}
while (op.size()) eval();
cout << num.top() << endl;
return 0;
}
p 数组提前存储预处理的 p 次方的值，减少计算量
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int que, st = -1, ed = -1;
int main() {
int m;
cin >> m;
while (m--) {
string str;
int x;
cin >> str;
if (str == "push") {
cin >> x;
que[++ed] = x;
} else if (str == "pop") {
st++;
} else if (str == "empty") {
if (st == ed)
puts("YES");
else
puts("NO");
} else if (str == "query") {
cout << que << endl;
}
}
return 0;
}
STL
size()、empty() 所有容器都有，时间复杂度 \(O(1)\)
clear() 并不是所有容器都有，队列、优先队列、栈；范围遍历可以遍历所有容器
⭐ 系统为某一个程序分配空间时，所需的时间与空间大小无关，与申请次数有关
vector
变长数组，倍增，支持比较运算（字典序（4个3小于3个4））。有erase但用得不多
插入操作\(O(1)\)：插入1e6次，申请空间的次数 \(log_21e6\) ，拷贝的次数均摊是 1 （数组大小从1到1e6，总共拷贝次数是1e6（1+2+4+8+...））
#include #include using namespace std;int main() { // ^ 定义一个长度为10的vector，每个数都是3 vector a(10, 3); vector b; a.push_back(1); cout
页:
[1]