1. 并查集(Union Find) (1) 定義 并查集:也叫作 不相交集合(Disjoint Set)并查集:適合解決 “連接” 相關(guān)的問題:村莊道路連接等并查集:是可以...
1. 優(yōu)先級(jí)隊(duì)列(Priority Queue) (1) 定義 普通隊(duì)列:FIFO原則,也就是先進(jìn)先出優(yōu)先級(jí)隊(duì)列(Priority Queue):按照 優(yōu)先級(jí)高低 進(jìn)行出隊(duì) ...
Q:Top K問題:從海量數(shù)據(jù)n中找出前K個(gè)數(shù)據(jù)? 使用 排序算法 進(jìn)行全排序,時(shí)間復(fù)雜度 使用 數(shù)據(jù)結(jié)構(gòu) 二叉堆 來(lái)解決,時(shí)間復(fù)雜度1.使用小頂堆2.將前個(gè)數(shù)放入堆中,然后...
1. 哈希表(Hash Table) (1) 定義 哈希表(Hash Table):一種不允許值重復(fù)的順序數(shù)據(jù)結(jié)構(gòu)。(散列表)利用 哈希函數(shù)(散列函數(shù)) 生成 key 對(duì)應(yīng)的...
1. 集合(Set) (1) 定義 集合(Set):一種不允許值重復(fù)的順序數(shù)據(jù)結(jié)構(gòu)不存放重復(fù)的元素常用于去重存放新增IP,統(tǒng)計(jì)新增IP量存放詞匯,統(tǒng)計(jì)詞匯量...... (2...
1. 紅黑樹(Red Black Tree) (1) 定義 紅黑樹(Red Black Tree):是一種自平衡的二叉搜索樹,也叫平衡二叉B樹。紅黑樹必須滿足一下5條性質(zhì):節(jié)...
1. B樹(B-tree) (1) 定義 B樹(B-tree):一種平衡的 多路搜索樹,多用于文件系統(tǒng)、數(shù)據(jù)庫(kù)的實(shí)現(xiàn)。其特點(diǎn):1個(gè)節(jié)點(diǎn)可以存儲(chǔ)超過2個(gè)元素,可以擁有超過2個(gè)子...
1. AVL樹 (1) 定義 平衡因子(Balance Factor):某節(jié)點(diǎn)的 左右子樹 的高度差A(yù)VL樹的特點(diǎn):每個(gè)節(jié)點(diǎn)的 平衡因子 只可能是1、0、-1(絕對(duì)值<=1,...
1. 二叉搜索樹(Binary Search Tree) (1) 定義 二叉搜索樹BST,又稱 二叉查找樹、二叉排序樹任意一個(gè)節(jié)點(diǎn)的值都 大于 其左子樹 所有節(jié)點(diǎn)的值任意一個(gè)...
1. 遍歷 線性數(shù)據(jù)結(jié)構(gòu)的遍歷方式:正序遍歷逆序遍歷二叉樹的遍歷方式:前序遍歷(Preorder Traversal)中序遍歷(Inorder Traversal)后序遍歷(...
1. 樹(Tree) (1) 基礎(chǔ)概念 1> 節(jié)點(diǎn) 節(jié)點(diǎn)、根節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn) 2> 樹、子樹 一棵樹可以沒有任何節(jié)點(diǎn),稱為 空樹一棵樹可以只有1個(gè)節(jié)點(diǎn),也就是只...
0. 簡(jiǎn)介 線性表是具有 n個(gè) 相同類型元素 的有限序列 (n>=0)常見的線性表有:數(shù)組、鏈表、棧、隊(duì)列、哈希表(散列表) 1. 數(shù)組(Array) 數(shù)組(Array):是...
1. 簡(jiǎn)介 (0) 學(xué)習(xí)框架 分為至少3個(gè)階段(預(yù)計(jì)共100小時(shí)左右): 第1階段:常用的 經(jīng)典數(shù)據(jù)結(jié)構(gòu)(比如二叉樹、哈希表、Trie 等) 第2階段:更高級(jí)的 數(shù)據(jù)結(jié)構(gòu)(比...
1. 結(jié)構(gòu)體struct 和 類class (1) 結(jié)構(gòu)體和類區(qū)別? (2) 為什么使用結(jié)構(gòu)體? 在多線程環(huán)境中,多個(gè)線程會(huì)共享堆上的內(nèi)存,為了確保 線程安全,需要在堆上進(jìn)行...