努力學(xué)習(xí)中
一几于、基礎(chǔ)算法
-
二叉查找——在
的時間內(nèi)尋找某一個具體值
-
計數(shù)排序——這是一種犧牲內(nèi)存空間來換取低時間復(fù)雜度的排序算法,可以達(dá)到
時間復(fù)雜度
-
快速排序——對冒泡排序的一種改進(jìn)罚渐，可以在最好和平均時間復(fù)雜度為
久橙，最壞時間復(fù)雜度
-
桶排序——當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值平局分配的時候拴竹，桶排序使用線性時間（
）
- 置換環(huán)——得到數(shù)組排序（可以指定排序方式）所需交換的最小次數(shù)
二、線性表
- 并查集——適用于解決一些元素的分組問題
三揽思、棧和隊列
- 單調(diào)隊列——解決滑動窗口類問題
- 單調(diào)棧——解決Next Greater Element(NGE)問題
四岭皂、樹
- 二叉搜索樹——維護(hù)一個有序的數(shù)組，搜索前綴簿透、后綴移袍、最大值、最小值
- 平衡二叉搜索樹——使每個結(jié)點的左右兩顆子樹的高度差都不超過一
-
線段樹——用于維護(hù)區(qū)間信息老充，可以實現(xiàn)
的區(qū)間修改
- 二叉堆——適用于按大小取數(shù)的情況
五葡盗、圖
- 單源最短路徑-Dijkstra——解決正權(quán)圖的單源最短路徑問題
六、字符串
-
字典樹——用來存儲和查詢字符串啡浊，利用字符串的公共前綴來減少查詢時間觅够，同時可以利用字符串的
'后綴'+'$'+'前綴'形式完成前綴后綴的搜索 -
KMP字符串匹配算法——在
的時間復(fù)雜度內(nèi)在文本串中快速查找模式串
- 最長公共子序列——利用動態(tài)規(guī)劃查找兩個字符串的最長公共子序列
-
確定有限狀態(tài)自動機(jī)——求解給定的輸入字符串
S是否滿足條件P的問題
七、動態(tài)規(guī)劃
- 前綴和——數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和巷嚣，在單位時間內(nèi)求出單位和
- 線性動態(tài)規(guī)劃——具有線性階段劃分的動態(tài)規(guī)劃算法
- 區(qū)間動態(tài)規(guī)劃——一個狀態(tài)通常由被它包含且比它更小的區(qū)間狀態(tài)轉(zhuǎn)移而來
- 樹形動態(tài)規(guī)劃——根據(jù)樹形結(jié)構(gòu)進(jìn)行動態(tài)規(guī)劃的算法
八喘先、數(shù)學(xué)
- 最大公約數(shù)和最小公倍數(shù)——求解最大公約數(shù)和最小公倍數(shù)簡潔版
- 同余及其性質(zhì)——數(shù)論中的一種等價關(guān)系
-
組合數(shù)的計算方法——從
個不同元素中取出個
元素的所有組合的個數(shù)
九、高頻面試題
參考文獻(xiàn)：
