簡(jiǎn)述 快排是排序算法中繞不開的關(guān)鍵一環(huán)，其中涉及到分治算法，二分查找等關(guān)鍵知識(shí)暮胧。 本文內(nèi)容： 快排原理 代碼實(shí)現(xiàn) 分區(qū)過程圖示 <啊哈算法> 中的另一種實(shí)現(xiàn) 復(fù)雜度 優(yōu)化 快...
發(fā)簡(jiǎn)信
IP屬地：浙江
-
-
遞歸時(shí)間復(fù)雜度 推演計(jì)算遞歸的時(shí)間復(fù)雜度計(jì)算較為麻煩间狂。以下我們使用歸并排序的例子，對(duì)遞歸復(fù)雜度進(jìn)行推演火架。 假設(shè)現(xiàn)在有一個(gè)歸并排序鉴象。他的運(yùn)行總時(shí)間是 T（n），我們通過將其分解成 2 個(gè)計(jì)算式何鸡，即 ：...
-
兩個(gè)有序的鏈表合并題目描述： 具體如下圖： 即犹菱，將 L1 和 L2 鏈表進(jìn)行合并。 思路1：遞歸 每次比較 l1 和 val 和 l2 的 val吮炕，誰小腊脱，就繼續(xù)循環(huán)他的 next 節(jié)遞歸進(jìn)行比...
-
鏈表中環(huán)的檢測(cè)
題目描述： 這里考察的也是快慢指針。 當(dāng)然龙亲，如果我們用 HashSet 陕凹，也可以實(shí)現(xiàn)。當(dāng)時(shí)明顯不是這道題的考察目的鳄炉。 我們假設(shè)杜耙，使用 2 個(gè)指針，快指針是慢指針的 2 倍速迎膜。...
-
求鏈表的中間節(jié)點(diǎn)題目描述： 這題考察的也是快慢指針泥技。 我們對(duì)偶數(shù)和奇數(shù)分別進(jìn)行分析： 當(dāng)鏈表是偶數(shù)時(shí)，我們需要判斷他自身是否為 null，如果為 null珊豹，說明到了末尾簸呈。 當(dāng)鏈表是奇數(shù)時(shí)，我...
-
刪除鏈表中倒數(shù)第 n 個(gè)節(jié)點(diǎn)引言 題目描述： 簡(jiǎn)單說店茶，這道題的的公式就是：(length - n + 1).next = (length - n).next;即蜕便，將 n 的 pre 節(jié)點(diǎn)的 next 節(jié)...
-
單鏈表反轉(zhuǎn)
鏈表題中，鏈表反轉(zhuǎn)應(yīng)該是出現(xiàn)頻率最高的一道題贩幻。 如何實(shí)現(xiàn)轿腺？ 我們分析一下，一個(gè)鏈表丛楚，【1族壳， 2，3趣些，4仿荆，5】，反轉(zhuǎn)成 【5坏平，4拢操，3，2舶替，1】令境，我們可以適應(yīng)循環(huán)。 循環(huán)的過程中...
-
隊(duì)列的 2 種實(shí)現(xiàn)方式
引言 隊(duì)列顾瞪，是一個(gè)線性表舔庶，和數(shù)組，棧陈醒，鏈表類似栖茉。隊(duì)列和棧類似，戲稱“邊吃邊拉”孵延。即 FIFO。 隊(duì)列和棧還有一個(gè)不同亲配，棧只需維護(hù)一個(gè)棧頂指針尘应，而隊(duì)列需要維護(hù) 2 個(gè)指針，隊(duì)首...
-
棧的應(yīng)用前述 棧吼虎，戲稱“邊吃邊拉”犬钢。 棧是一種“操作受限” 的數(shù)據(jù)結(jié)構(gòu)，只有 push 和 pop 兩種操作思灰。先進(jìn)先出玷犹，后勁后出。 可以由數(shù)組實(shí)現(xiàn)洒疚，也可以是鏈表實(shí)現(xiàn)歹颓，前者稱之為 順序...
-
如何寫好鏈表代碼坯屿？
前述 鏈表代碼不好寫，初學(xué)者經(jīng)常容易出錯(cuò)巍扛。掌握以下幾個(gè)規(guī)則领跛，可能可以提高編寫鏈表的技術(shù)。一共 6 個(gè)技巧： 1. 理解指針或引用的含義 對(duì)一個(gè)引用進(jìn)行賦值撤奸，其實(shí)就是將這個(gè)變量...
-
平均時(shí)間復(fù)雜度簡(jiǎn)述 在數(shù)據(jù)結(jié)構(gòu)與算法中吠昭，“時(shí)間復(fù)雜度”表示“隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，他的增長(zhǎng)趨勢(shì)”胧瓜，而時(shí)間復(fù)雜度矢棚，通過細(xì)化，可以分為：最好時(shí)間復(fù)雜度府喳，最壞時(shí)間復(fù)雜度蒲肋，平均時(shí)間復(fù)雜度，均攤時(shí)間復(fù)...