【算法】基础数据结构的使用
单调栈
通过维护一个单调递增或者单调递减的栈, 来求解元素左右大小边界的问题.
尝试思考下面这个问题, 对于第 1 个元素, 他往右边看, 除了比他高的, 都会被挡住(如第 3 个和第 4 个元素), 而这个就是单调栈的核心思想, 在这里被挡住的元素对当前节点来说是没用的信息, 所以单调栈维护的是当前节点往右边看, 不会被挡住的元素.
来看一道例题
这道例题中, 需要我们找到第一个大于当前元素的元素的下标, 那就是一个大小边界的问题, 我们直接从这个序列的最右边开始遍历, 然后为每一个节点维护一个单调栈. 即当前栈中如果存在比他小的, 就直接 pop 出去即可, 因为对于当前元素后面的元素, 这些都是被挡住的元素.
代码为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<stack>
using namespace std;
const int MAXN = 3e6+2;
int n, num[MAXN], ans[MAXN];
stack<int> sta;
int main(){
cin>>n;
for(int i=1; i<=n; i++){
cin>>num[i];
}
for(int i=n; i>=1; i--){
while(!sta.empty() && num[i]>num[sta.top()]){
sta.pop();
}
ans[i] = sta.empty() ? 0:sta.top();
sta.push(i);
}
for(int i=1; i<=n; i++){
cout<<ans[i]<<" ";
}
}
|
优先级队列
优先级队列(priority queue)是由二叉堆实现的, push 和 pop 的复杂度是 O(logn) ,当用优先队列去处理 pair 元素时, 他会按照 pair 中大的那个进行优先级排序, 优先级队列也是队列, 队列中如果 pop 了一个元素, 他不会释放分配过的内存, 只有析构的时候才会一起分配, 所以如果你 pop 一个元素后马上使用 back 去读取他还是能读到之前的元素的.
例题:
优先队列模板题, 维护一个大端序的优先队列, 每次遇到 IN 事件就加入到队列中, 遇到 OUT 事件就从队列中取出, 如果队列为空就输出 EMPTY, 需要注意的是这里如果优先权一样, 就要选择最早来排队的病人, 所以要重构 operator, 然后把这个 operator 应用到优先队列中.
代码为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<queue>
using namespace std;
struct node{
int level, pos;
friend bool operator < (const int x, const int y){
if(x.level != y.level)
return x.level < y.level;
else
return x.pos > y.pos;
}
}
int main(){
int n,a,b;
string opt;
int cnt=0;
while(cin>>n){
priority_queue<node> que[4];
while(n--){
cin>>opt;
if(opt == 'IN'){
cin>>a>>b;
cnt++;
que[a].push(b)
}
if(opt == 'OUT'){
cin>>a;
if(que[a].empty())
cout<<"EMPTY"<<endl;
else{
cout<<que[a].top.pos<<endl;
que[a].pop();
}
}
}
}
}
|
哈希表
哈希表就是通过映射将字符串通过一些加密函数转换后进行存储, 可以进行状态压缩, 将大集合映射成小集合.
一般的哈希函数很容易发生值冲突, 这里给一个字符串哈希的模板代码:
根据公式:
$$ Hash(S) = (\sum_{i=1}^nc_i * base^n-1) \mod p $$
1
2
3
4
5
6
7
8
9
| int getHash(string s){
int res=0;
int base=31;
int mod = 1222827239;
for(int i=0;i<s.size();i++){
res = (res*base+(s[i]-'a')) % mod;
}
return res;
}
|
哈希状态压缩例题:
需要注意的是, 这道题的范围 $N \leq 10000, M_{max} \leq 1500$, 如果使用 vector 存储数据, 需要花费的最大空间计算如下:
$$ \frac{10000 \times 1500}{1 \times 1024 \times 1024} \approx 15 \text{ MB} $$
这里的 $1$ 是因为对于每个字符是 char 格式, 占一个字节. 最大需要消耗 15mb 的内存空间, 所以会爆掉, 这里要用哈希去状态压缩, 然后使用 set 去重, 最后返回 size 就是答案, 代码为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<string>
using namespace std;
int getHash(string s){
int res=0;
int base=31;
int mod = 1222827239;
for(int i=0;i<s.size();i++){
res = (res*base+(s[i]-'a')) % mod;
}
return res;
}
int main(){
int n;
cin>>n;
set<int> res;
for(int i=0; i<n;i++){
string str;
cin>>str;
res.insert(getHash(str));
}
cout<<res.size()<<endl;
return 0;
}
|
双重哈希状态压缩, 例题:
这里内存和时间都卡的很死, 思路是使用双重哈希, 具体做法是用一个 vector 数组顺序保存词典索引和词典内容, 然后用 map 去记录对应 hash 的下标. 因为 map 里面是红黑树, 如果直接存映射会爆内存的.
代码为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
#include<map>
#include<string>
#include<utility>
using namespace std;
int getHash(string s){
long long res=0;
int base=65337;
int mod = 1e9+7;
for(int i=0;i<s.size();i++){
res = (res*base+(s[i]-'a')) % mod;
}
return res;
}
int main(){
map<int, int>hash2pos;
vector<string> dicts;
string str;
while(getline(cin,str)&& str!="@END@"){
int pos = str.find("]");
string dict = str.substr(0,pos+1);
string fun = str.substr(pos+2,str.length()-1);
int dict_hash = getHash(dict);
int fun_hash = getHash(fun);
dicts.push_back(dict);
dicts.push_back(fun);
hash2pos[dict_hash] = dicts.size()-1;
hash2pos[fun_hash] = dicts.size()-2;
}
int n;
cin>>n;
while(n--){
cin>>str;
int hashvalue = getHash(str);
if(str[0]='['){
if(hash2pos.count[hashvalue]>0){
cout<<dict[hash2pos[hashvalue]]<<endl;
}
else{
cout<<"what?"<<endl;
}
}
else{
if(hash2pos.count[hashvalue]>0){
string res = dicts[hash2pos[hashvalue]];
res = res.substr(1,res.size()-2);
cout<<res<<endl;
}
else{
cout<<"what?"<<endl;
}
}
}
return 0;
}
|
