獨(dú)行鴨

二叉查找樹(shù)（Binary Search Tree） 支持動(dòng)態(tài)數(shù)據(jù)集合的快速插入刪除查找 要求钩骇？節(jié)點(diǎn)值：左<父<右 【二叉排序樹(shù)】中序遍歷二叉查找樹(shù)可輸出有序的數(shù)據(jù)序列辰妙，時(shí)間復(fù)...

獨(dú)行鴨

樹(shù)：非線性表結(jié)構(gòu)orz 概念直覺(jué)理解（節(jié)點(diǎn)、父子關(guān)系棉浸、兄弟節(jié)點(diǎn)、根節(jié)點(diǎn)、葉節(jié)點(diǎn)）高度（類比樓房，葉節(jié)點(diǎn)為0蟹略，下往上遞增）vs深度（類比水面，根節(jié)點(diǎn)為0遏佣，上往下遞增）vs層數(shù)=...

獨(dú)行鴨

應(yīng)用五：負(fù)載均衡 會(huì)話粘滯（session sticky）的負(fù)載均衡算法要求？在同一個(gè)客戶端上揽浙，在一次會(huì)話中的所有請(qǐng)求都路由到同一個(gè)服務(wù)器上 維護(hù)映射關(guān)系表（客戶端IP地址/...

獨(dú)行鴨

哈希算法=映射規(guī)則状婶，將任意長(zhǎng)度的二進(jìn)制值串映射為固定長(zhǎng)度的二進(jìn)制值串（哈希值） 要求？ 單向：從哈希值不能反推出原始數(shù)據(jù) 對(duì)輸入數(shù)據(jù)敏感 散列沖突的概率小 執(zhí)行高效 應(yīng)用一：...

獨(dú)行鴨

優(yōu)秀的散列函數(shù) 設(shè)計(jì)不能太復(fù)雜避免消耗計(jì)算時(shí)間 生成的值盡可能隨機(jī)且均勻分布 裝載因子過(guò)大馅巷？——?jiǎng)討B(tài)擴(kuò)容（閾值設(shè)置權(quán)衡時(shí)間空間復(fù)雜度） 避免低效擴(kuò)容膛虫？裝載因子達(dá)閾值后，只申請(qǐng)...

獨(dú)行鴨

數(shù)組的一種拓展钓猬，利用數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性稍刀。通過(guò)散列函數(shù)把元素鍵值映射為下標(biāo)，將數(shù)據(jù)存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)的位置。 key --hash function--> t...

獨(dú)行鴨

動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)：支持快速插入刪除查找操作（改造后的鏈表以支持類似二分的查找算法） 理解账月？（跳表=鏈表加多級(jí)索引的結(jié)構(gòu)）對(duì)鏈表建立索引综膀，提高查找效率（每?jī)蓚€(gè)節(jié)點(diǎn)提取一個(gè)到上一級(jí)，...

獨(dú)行鴨

針對(duì)有序的數(shù)據(jù)集合局齿。每次都通過(guò)與區(qū)間的中間元素對(duì)比剧劝，將待查找區(qū)間縮小為原來(lái)一半，直到找到所需元素或區(qū)間縮小為0 時(shí)間復(fù)雜度O（logn） 易錯(cuò)點(diǎn)(low抓歼、high讥此、mid指數(shù)...

獨(dú)行鴨

快速排序 理想的分區(qū)點(diǎn)——被分區(qū)點(diǎn)分開(kāi)的兩個(gè)分區(qū)中數(shù)據(jù)的數(shù)量差不多 分區(qū)算法 三數(shù)取中法（每間隔某個(gè)固定的長(zhǎng)度，取數(shù)據(jù)出來(lái)比較谣妻，將中間值作為分區(qū)點(diǎn)） 隨機(jī)法（每次從要排序的區(qū)...

獨(dú)行鴨

桶排序（Bucket sort） 核心思想——將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里萄喳，每個(gè)桶里的數(shù)據(jù)單獨(dú)進(jìn)行排序，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出 較適合用在外部排序（數(shù)據(jù)存儲(chǔ)在...

獨(dú)行鴨

歸并排序（Merge Sort） 核心思想——把數(shù)組從中間分成前后兩部分蹋半，分別排序后再合并在一起 分治思想——分治就是分而治之他巨，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決 分治是一種...

獨(dú)行鴨

原地排序（Sorted in place）特指空間復(fù)雜度是 O(1) 的排序算法 穩(wěn)定性——排序后值相等的元素間前后順序不變 冒泡排序（Bubble Sort） 核心思想 只...

獨(dú)行鴨

使用條件 一個(gè)問(wèn)題的解可以分解為幾個(gè)子問(wèn)題（數(shù)據(jù)規(guī)模更小的問(wèn)題）的解 這個(gè)問(wèn)題與分解之后的子問(wèn)題，除數(shù)據(jù)規(guī)模不同湃窍，求解思路一樣 存在遞歸終止條件 關(guān)鍵 找到將大問(wèn)題分解為小問(wèn)...

獨(dú)行鴨

先進(jìn)先出（類比排隊(duì)買(mǎi)票&不允許插隊(duì)） 操作受限的線性表數(shù)據(jù)結(jié)構(gòu) 順序隊(duì)列——用數(shù)組實(shí)現(xiàn)的隊(duì)列（有界隊(duì)列（bounded queue）的大小有限） 鏈?zhǔn)疥?duì)列——用鏈表實(shí)現(xiàn)的隊(duì)列...

獨(dú)行鴨

特點(diǎn) 后進(jìn)先出闻蛀，先進(jìn)后出（類比往桶里放東西） 操作受限的線性表，只允許在一端插入和刪除數(shù)據(jù) 順序椖校——用數(shù)組實(shí)現(xiàn)鏈?zhǔn)綏觉痛！面湵韺?shí)現(xiàn) 應(yīng)用 函數(shù)調(diào)用棧 表達(dá)式求值 括號(hào)匹配

獨(dú)行鴨

指針/引用含義 存儲(chǔ)所指對(duì)象的內(nèi)存地址 將某個(gè)變量賦值給指針=將這個(gè)變量的地址賦值給指針指針中存儲(chǔ)了變量的內(nèi)存地址指向這個(gè)變量，通過(guò)指針就能找到這個(gè)變量 警惕指針丟失和內(nèi)存泄...

獨(dú)行鴨

通過(guò)“指針”將一組零散的內(nèi)存塊串聯(lián)使用茵休，支持動(dòng)態(tài)擴(kuò)容 單鏈表 鏈表的結(jié)點(diǎn)——內(nèi)存塊 后繼指針next——記錄下個(gè)節(jié)點(diǎn)地址的指針 頭結(jié)點(diǎn)記錄鏈表的基地址 尾結(jié)點(diǎn)指向空地址NUL...

獨(dú)行鴨

數(shù)組=線性表數(shù)據(jù)結(jié)構(gòu)=用一組連續(xù)的內(nèi)存空間存儲(chǔ)一組具有相同類型的數(shù)據(jù) 線性表=數(shù)據(jù)間只有前后關(guān)系薪棒，排成一條線 連續(xù)的內(nèi)存空間&相同類型的數(shù)據(jù)=> 隨機(jī)訪問(wèn)（尋址公式計(jì)算元素存...

獨(dú)行鴨

事后統(tǒng)計(jì)法(跑一遍）局限性：測(cè)試結(jié)果依賴測(cè)試環(huán)境、受數(shù)據(jù)規(guī)模影響 大O復(fù)雜度表示法粗略估計(jì)=>假設(shè)每行代碼執(zhí)行時(shí)間相等執(zhí)行時(shí)間T(n）與每行代碼實(shí)行次數(shù)n成正比 時(shí)間/空間復(fù)...

獨(dú)行鴨

1.為什么要學(xué)習(xí)榕莺？ 助于閱讀框架源碼俐芯、理解設(shè)計(jì)思想 優(yōu)化細(xì)節(jié)：數(shù)據(jù)存取效率、節(jié)省內(nèi)存等 改變看待問(wèn)題深度钉鸯、解決問(wèn)題角度吧史，高效解決實(shí)際問(wèn)題 2.如何抓住學(xué)習(xí)重點(diǎn)？ 理解概念 唠雕！...