建设一个网站需要用到几个语言,优化关键词首页排行榜,北京网站搭建哪家好,专业品牌商标设计公司文章目录哈希表存储结构拉链法#xff1a;插入查询题目注意开放寻址法查找质数代码字符串哈希方式STL相关知识哈希表存储结构
整体结构 0~109-0~105
方法#xff1a;
x mod 105处理冲突 开放寻址法拉链法
拉链法#xff1a;
思想#xff1a;每个槽上拉一条链插入查询题目注意开放寻址法查找质数代码字符串哈希方式STL相关知识哈希表存储结构
整体结构 0~109-0~105
方法
x mod 105处理冲突 开放寻址法拉链法
拉链法
思想每个槽上拉一条链用于储存该槽上所有数 插入
确定插槽确定插槽链表 插入至头节点
查询
确定插槽遍历插槽链表
题目
维护一个集合支持如下几种操作1. I x插入一个数 xx
2. Q x询问数 xx 是否在集合中出现过现在要进行 N 次操作对于每个询问操作输出对应的结果。输入格式第一行包含整数 N表示操作数量。接下来 N 行每行包含一个操作指令操作指令为 I xQ x 中的一种。输出格式对于每个询问指令 Q x输出一个询问结果如果 xx 在集合中出现过则输出 Yes否则输出 No。每个结果占一行。数据范围1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109输入样例
5
I 1
I 2
I 3
Q 2
Q 5
输出样例
Yes
No#include iostream
#include cstring
using namespace std;
const int N 100003;//e被拆成了很多链
int h[N],e[N],ne[N],idx;
//插入到链表头部
void insert(int x)
{//将k映射至题目范围int k (x % N N)%N;//插入单链表插入//h[k]代表k链的头部节点节点值为xe[idx] x,ne[idx] h[k],h[k] idx;
}
bool find(int x)
{int k (x%NN)%N;/*遍历从头指针开始头指针存储第一个结点的下标e[i]表示当前节点的值是多少ne[i]下一个节点的下标空指针的下标为-1*/for(int i h[k];i!-1;i ne[i])if(e[i] x)return true;return false;
}int main()
{/*寻找大于100000的最小质数//1.确定范围for(int i 100000;;i){//2. 设置标志位bool flag true;//3. 从2开始查找条件为平方小于ifor(int j 2;j*ji;j){if( i % j 0 ){//4. 设置标志flag false;break;}}//5. 判断标志if(flag){cout iendl;//6. 结束break;}}return 0;*/int n;scanf(%d,n);//槽清空memset(h,-1,sizeof(h));while(n--){//注意此处为数组输入%schar op[2];int x;scanf(%s%d,op,x);if(*op I) insert(x);else{if(find(x)) puts(Yes);elseputs(No);}}
}
注意
取模计算
负数模一个值等于该绝对值模值结果添加负号
-10 %3 -1 需要先模再加再模才可以使得负数取模为正数。
开放寻址法
只开了一个一维数组没有开辟链表形式更为简单。
一维数组的长度经验来说开到题目的两到三倍 如何处理冲突从第k个坑位开始找如果第k个坑位有人的话就查找下一个坑位 一般题目只会用到查找与添加
添加
查找从前向后找
删除找到x后打个标记表示x删除
维护一个集合支持如下几种操作1. I x插入一个数 xx
2. Q x询问数 xx 是否在集合中出现过现在要进行 N 次操作对于每个询问操作输出对应的结果。输入格式第一行包含整数 N表示操作数量。接下来 N 行每行包含一个操作指令操作指令为 I xQ x 中的一种。输出格式对于每个询问指令 Q x输出一个询问结果如果 xx 在集合中出现过则输出 Yes否则输出 No。每个结果占一行。数据范围1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109输入样例
5
I 1
I 2
I 3
Q 2
Q 5
输出样例
Yes
No查找质数
#include iostreamusing namespace std;
//开两倍
const int N 200003;int main()
{//首先找到大于200000的质数for(int i 200000;;i){bool flag true;for(int j 2; j*ji ;j)if(i%j 0){flag false;break;}if(flag){coutiendl;break;}}return 0;
}得到结果为 200003
代码
#include iostream
#include cstring
using namespace std;
//N为大于2倍的最小质数null为大于区间的一个值用于表示空
//一般设置最大值也设置0x3f3f3f3f
const int N 200003,null 0x3f3f3f3f;
int h[N];//find--寻找下一个坑位
int find(int x)
{//映射int k (x % N N) % N;//坑位有人并且不等于x//循环退出条件找到值或者找到新的坑位//一定可以停止因为数组大小较大while(h[k] ! null h[k] ! x ){//向后查找下一个坑位k;//如果已经到达结尾循环看第一个坑位if(k N) k 0;}//如果x在哈希表中k返回为下标//如果不在哈希表中k表示应该存储的位置return k;
}int main()
{int n;int x;char op[2];/*为什么memset 0x3f因为memset按字节进行不是按数字初始化的,h是int型数组一共有4个字节每个字节都是0x3f因此每个数是0x3f3f3f3f.一个字节是八位。memset(h,0,sizeof(h)); 每个字节是0整体为0memset(h,-1,sizeof(h)); 每个字节是-11111 1111整体为-1*/memset(h,0x3f,sizeof(h));scanf(%d,n);while(n--){scanf(%s%d,op,x);int k find(x);if(op[0] I) h[k] x;else {if(h[k] ! null) puts(Yes);else puts(No);}}return 0;
}
字符串哈希方式
字符串前缀哈希法
步骤 预处理所有前缀的哈希 如何定义某个前缀的哈希值 把字符串看成P进制的数。 假定映射关系如下表 字母值A1B2C3D4字符串“ABCD”对应的数值如下图所示 预处理方式 将P进制的数转化为10进制的数数字可能很大通过取模进行映射到0,Q-1
注意 不能把字母映射为0。不然不同的字符串均映射为0导致出错与冲突 Rp【P进制】足够好不存在冲突。经验值131或13331
好处可以利用前缀哈希求得所有子串 的哈希值 已知h[R]、h[L-1] h[L-1]左移至与R对齐 然后相减: h[R]-h[L-1]PR-L1 Q:264 用unsigned long long存储h当数值溢出相当于取模因此不需要取模
给定一个长度为 n 的字符串再给定 m 个询问每个询问包含四个整数 l1,r1,l2,r2请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式
第一行包含整数 n 和 m表示字符串长度和询问次数。第二行包含一个长度为 n 的字符串字符串中只包含大小写英文字母和数字。接下来 m 行每行包含四个整数 l1,r1,l2,r2表示一次询问所涉及的两个区间。注意字符串的位置从 1 开始编号。输出格式
对于每个询问输出一个结果如果两个字符串子串完全相同则输出 Yes否则输出 No。每个结果占一行。数据范围
1≤n,m≤105
输入样例
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例
Yes
No
Yes#include iostream
#include stringtypedef unsigned long long ULL;const int N 100010,P 131;int n,m;
char str[N];
/*
p数组用来存储p的多少次方的数值p的0次方等于1
h数组表示某个前缀的哈希值h[R]表示前R个字母的哈希值
*/
ULL h[N],p[N];
ULL get(int l,int r)
{return h[r] - h[l-1] * p[r-l1]; //部分区间长度计算公式
}
int main()
{scanf(%d%d%s,n,m,str 1);p[0] 1;for(int i 1;i n ;i){p[i] p[i-1] * P; //填充进制 P的一次方 P的二次方h[i] h[i-1] * P str[i]; //填充前缀和}while(m--){int l1,r1,l2,r2;scanf(%d%d%d%d,l1,r1,l2,r2);if(get(l1,r1) get(l2,r2)) puts(Yes);else puts(No);}return 0;
}STL相关知识
/*
vector:变长数组数组长度动态变化倍增的思想
string字符串substr(),c_str()
queue:push(),front(),pop()
priority queue,优先队列push(),top(),pop()
stack,栈push(),top(),pop()
deque,双端队列
set,map, multiset,multimap基于平衡树二叉树红黑树实现动态维护有序序列
unordered_set,unordered_map,unordered_multiset,unordered_multimap哈希表
bitset压位
*/一开始学习的时候现用现查就可以了 vector的倍增思想
系统为某一个程序分配空间时所需的时间基本上与空间大小无关与申请次数有关 vector数组长度不够时新建一个二倍长度的数组然后把之前的数据copy过来
/*知道存在该操作用的时候现用现查
vector:变长数组数组长度动态变化倍增的思想size(); //返回元素个数empty(); //返回a是否为空clear():清空这个函数不是所有容器都有front()/back()push_back()/pop_back()begin()/end()[] 随机取址支持比较运算
pairint,int 用于存储二元组first,第一个元素second, 第二个元素支持比较运算以first为第一个关键字以second为第二个关键字字典序pair与结构体相比有什么好处pair可以看作帮我们实现了一个结构体自带一个比较函数比一般结构体省代码可以存储任意多个可以随便嵌套
string字符串substr(),c_str()size()/length() 返回字符串长度empty()clear()
queue:队列队尾插入队头弹出先入先出的关系size()empty()push() 向队尾插入一个元素front() 返回队头元素back() 返回队尾元素pop() 弹出队头元素没有clear函数如果需要清空一个queue直接构造一个queue就可以定义时小根堆多加两个参数priority_queueint,vectorint,greaterint heap;
priority queue,优先队列默认时大根堆push(),插入一个元素top(),返回堆顶元素pop()弹出堆顶元素
stack,栈size()empty()push(),向栈顶插入一个元素top(),返回栈顶元素pop()弹出栈顶元素
deque,双端队列size()empty()clear()front()back()push_back() / pop_back()push_front() / push_front()begin() / end()[]deque用的比较少以为deque的效率低的令人发指比一般的慢好几倍
set,multiset,map, multimap基于平衡树二叉树红黑树实现动态维护有序序列size()empty()clear()begin()/end() -- 返回前驱和后继 时间复杂度 O(logn)set/multisetset不支持插入重复元素multiset 支持插入重复元素insert() 插入一个数find() 查找一个数count() 返回某个数的个数erase()(1)输入是一个数删除所有x O(k log(n))//k为数的个数(2)输入一个迭代器删除这个迭代器lower_bound()/upper_bound()lower_bound(x) 返回大于等于x的最小的数的迭代器upper_bound(x) 返回大于x的最小的数的迭代器map/multimapinsert() 插入的数是一个pairerase() 插入的参数是pair或者迭代器find()[] 时间复杂度是O(logn)lower_bound()/upper_bound()unordered_set,unordered_map,unordered_multiset,unordered_multimap哈希表和上面类似增删改查的时间复杂度是O(1)不支持lower_bound()/upper_bound(),及迭代器的 --
bitset压位一个整数4个字节32位很多题目压位计算bitset1024 bool数组 C中一个bool是一个字节1024B 1KB移到位中去只需要开128B比正常数组省8倍内存bitset10000 s; 中为个数~s,,|,^,,![]count() 返回多少个1any/none()any() 判断是否至少有一个1none() 判断是否全为0set() 把所有位置置为1set(k,v) 将第k位变为vreset() 把所有位变为0flip() 等价于~flip(k) 把k位取反C Reference C最权威语法
*/#include cstdio
#include string
#include iostream
#include algorithm
#include vector
#include queue
#include deque
#include set
#include map
#include unordered_map
using namespace std;int main()
{/*vectorint a;vectorint b(10);vectorint c(10,-3);for(auto x :c )coutxendl;vectorint a[10];//size与empty是所有元素都有的函数所有容器都有//时间复杂度是O(1)的不会说求size的时候遍历而是有一个变量来存储sizea.size(); //返回元素个数a.empty(); //返回a是不是空的*//*vector遍历vectorint a;for(int i 0 ;i 10;i) a.push_back(i);for(int i 0;ia.size();i) couta[i] ;coutendl;//迭代器可以看做是指针使用*解引用//for(vectorint::iterator i a.begin();i ! a.end();i) cout*i ;//auto关键字系统自动推断类型当类型特别长时,用auto很省事for(auto i a.begin();i ! a.end();i) cout*i ;coutendl;//a.begina[0] a.end()a.[a.size()]//C中范围遍历for(auto x : a) coutx ;coutendl;return 0;//比较运算。按照字典序进行比较vectorint a(4,3),b(3,4);if(a b) puts(ab);*//** pairint,string p;* 某个东西有两个不同的属性就可以用pair存储可能需要按照某一个属性排序p.firstp.second有三个属性也可以用pair存储pairint,pairint,int ppairint,string p;p make_pair(10,jgy);p {20,abc};* *//** string a yxc;a def;a c;// cout a endl;//含义下标从1开始返回n个字母当n大于数组长度时输出到字符串最后一个字符为止// 把第二个参数省略返回从1开始的整个子串// couta.substr(1,10)endl;printf(%s\n,a.c_str());* *//*queue清空* queueint a;a queueint();* *//* heap默认大根堆* priority_queueint heap;* 如果要使用小根堆* 1. 直接插入-x* 2. 定义时直接定义为小根堆多加两个参数* //小根堆priority_queueint,vectorint,greaterint heap;* *//*集合* setint s;multisetint ms;* *//*map* mapstring ,int a;a[yxc] 1;couta[yxc]endl;* *//*unordered_mapstring,int a;unordered_multimapstring,int b;return 0;* *//*bitset* 10000*10000 bool* 10的8次方 100MB空间 题目限制64M* bitset 12M足够了* */}bitset
1024 bool数组 C中一个bool是一个字节
1024B 1KB
移到位中去只需要开128B
