ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++算法之旅、05 基础篇 | 第二章数据结构 [打印本页]

作者: 羊蹓狼 时间: 2023-9-3 23:57
标题: C++算法之旅、05 基础篇 | 第二章数据结构
常用代码模板2——数据结构 - AcWing
笔试用数组模拟而不是结构体

使用结构体指针，new Node() 非常慢，创建10万个节点就超时了，做笔试题不会用这种方式（优化是提前初始化好数组，但这样跟数组模拟没区别了，而且代码量很长）

单链表（数组）

使用两个数组，e存储val，ne存储next。空节点next用-1表示

826 ⭐

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[i]表示节点值，ne[i]表示节点next
// idx指向可用空间（当前可以用的最新点下标）
// 算法题不用考虑浪费的空间
int head, e[N], ne[N], idx;
void init() {
head = -1;
idx = 0;
}
// x 插到头结点后面
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx++;
}
// x 插到下标k的点后面
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
// 将下标 k 后面点删掉
void remove(int k) {
// if (ne[k] == -1) return; 题目保证合法不考虑边界情况
ne[k] = ne[ne[k]];
}
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[head]; // 特判删除头结点(链表第一个有效元素)
else
remove(k - 1);
} else if (c == 'I') {
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) {
cout << e[i] << " ";
}
return 0;
}

复制代码

837 ⭐⭐

837. 连通块中点的数量 - AcWing题库
保证根节点的nums有意义

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx;
void init() {
r[0] = 1;
l[1] = 0;
idx = 2;
}
// 在下标k点的右边插入x（可以转化成左边）
void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
r[k] = idx;
l[r[idx]] = idx;
idx++;
}
// 删除下标k的点
void remove(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
}
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[1], x);
} else if (s == "D") {
cin >> k;
remove(k - 1 + 2);
} else if (s == "IL") {
cin >> k >> x;
add(l[k - 1 + 2], x);
} else if (s == "IR") {
cin >> k >> x;
add(k - 1 + 2, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) {
cout << e[i] << " ";
}
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 在数组[3] 存入 11，h(4) = 3 在数组[4] 存入 4
- 与拉链法不同，查询函数返回 x 所在的位置，如果 x 不存在返回应该存储的位置
- 需要约定一个标志，不在 x 的值域范围内，表示当前位置为空，如 0x3f3f3f3f
拉链法
- 开一个一维数组 \([0,大于1e5的最小质数]\) 存储所有哈希值对应的链表
- h(11) = 3 在数组[3] 开一条链，插入 11
- 若 h(4) = 3 在数组[3] 已开的链插入 4
- 期望情况下，每条链长度 1，时间复杂度 \(O(1)\)

字符串哈希-字符串前缀哈希法（特殊）
应用：可以快速判断一个字符串某两段是否相同。KMP望而却步（KMP擅长循环节），极困难题可用这种方法

先预处理所有前缀的哈希，h[0] = 0, h[1] = "A" 的hash，h[2] = "AB" 的hash...
- 把字符串看成 P 进制的数，然后模 Q
**某个字符不能映射成 0，否则 AA 跟 A 两个哈希都是 0 **
该哈希法假定人品足够好，不考虑冲突
经验值：当 p = 131 或 13331，Q 取 \(2^{64}\) (用 unsinged long long可以不取模，溢出相当于取模)

⭐ 我们可以利用前缀哈希算出任意子段的哈希值

预处理前缀 h(i) = h(i-1) * p + str

与整数离散化的区别
整数离散化需要保序，而且不会发生冲突，每一个元素都有唯一确定的位置（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[N], 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[tt] << endl;
      }
}
return 0;
}
复制代码
840 ⭐开放寻址法

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
int op[N], num[N], opt = -1, numt = -1;
unordered_map<char, int> priority;
// 计算后缀表达式
void eval() {
auto b = num[numt--];
auto a = num[numt--];
auto c = op[opt--];
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[i])) {
         int j = i, res = 0;
         while (isdigit(str[j])) res = res * 10 + str[j++] - '0';
         num[++numt] = res;
         i = j - 1;
      } else if (str[i] == '(')
         op[++opt] = str[i];
      else if (str[i] == ')') {
         while (op[opt] != '(') eval();
         opt--;
      } else {
         while (opt >= 0 && priority[str[i]] <= priority[op[opt]]) eval();
         op[++opt] = str[i];
      }
}
while (opt >= 0) eval();
cout << num[numt];
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[i];
      if (isdigit(c)) {
         // 第一类双指针
         int x = 0, j = i;
         while (j < str.size() && isdigit(str[j]))
            x = x * 10 + str[j++] - '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[op.top()] >= pr[c]) 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[N], 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[st + 1] << 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+...））
[code]#include #include using namespace std;int main() { // ^ 定义一个长度为10的vector，每个数都是3 vector a(10, 3); vector b[10]; a.push_back(1); cout

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4