資料結構(3) acwing
目錄- 資料結構(3) acwing
- 1.hash表
- 存盤結構
- 字串哈希
- 3.STL
- 1.vector
- 2.string
- 3.queue
- 4.priority_queue(就是堆)
- 5.stack
- 6.deque（雙端佇列）--basically not use
- 7.set、multiset、map、multimap
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 壓位
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288659.html
標籤：C++