数据结构(3) acwing
-
- 3.stl
- 3.stl
1.hash表
哈希函数概念:
(1)x mod 10 ^5 即缩小了值域 {模的数最好取成“质数”:这样冲突的概率最小}
(2)解决冲突
- 求大于i的第一个质因子
-
存储结构
-
开放寻址法
(数组开辟长度为2~3倍){涉及到操作:添加、查询、删除(只是做一个标记,并不真正删除)}
-
0x3f3f3f3f是一个大于10^9的数,在memset()函数中,其按照字节进行存储,因为h为int型数组,占用4个字节,因此写一个0x3f就够了(一个字节是0x3f)
-
-
拉链法
-
-
字符串哈希
- 所有的关于字符串匹配问题,不一定利用kmp做,也可以使用字符串哈希方式
- 使用场景:比较两个字符串是否相等
- kmp算法和字符串哈希比较: kmp的特点是可以处理“循环结”
核心是:将一个字符串用k进制的形式,看做是一个数字
3.stl
1.vector
-
size(),元素的个数
-
empty() 返回是否为空
-
clear() 清空
-
front() /back() 第一个元素 /最后一个元素
-
push_back() / pop_back() 向后面插入一个数 / 删除数组最后一个数
-
begin() / end() 第0个数 / 最后一个数的后面一个数
倍增:系统为某程序分配空间时,所需时间与空间大小无关,只与请求次数有关
2.string
- size(),元素的个数
- empty() 返回是否为空
- clear() 清空
- substr():截取字符串
- c_str() :字符串第一个下标
初始下标为0
3.queue
-
empty()
-
size()
-
push(): 向队尾插入一个元素
-
front(): 返回队头元素
-
back(): 返回队尾元素
-
pop(): 弹出队头元素
4.priority_queue(就是堆)
默认是大根堆,转成小根堆的方式
- push() :插入一个元素
- top(): 返回堆顶元素
- pop(): 弹出堆顶元素
5.stack
-
empty()
-
size()
-
push()
-
top()
-
pop()
6.deque(双端队列)–basically not use
相当于加强版 vector
7.set、multiset、map、multimap
size()、empty()、clear()、begin()/end() ++,– 返回前驱和后继,时间复杂度o(logn)
- set/multiset
- map/multimap
-
unordered_set,unordered_map,unordered_multiset,unordered_multimap
和上面类似,但增删改查的时间复杂度为o(1)
不支持 lower_bound() / upper_bound()、迭代器的++、–
-
bitset 压位
需要了解更多c/c++开发分享Acwing Arithmetic Learning:数据结构(3),都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/643578.html