做斗圖的網(wǎng)站,網(wǎng)頁設(shè)計作品源代碼下載,中國軟件公司排行,織夢網(wǎng)站維護對前端開發(fā)者而言#xff0c;學(xué)習(xí)算法絕非為了“炫技”。它是你從“頁面構(gòu)建者”邁向“復(fù)雜系統(tǒng)設(shè)計者”的關(guān)鍵階梯。它將你的編碼能力從“實現(xiàn)功能”提升到“設(shè)計優(yōu)雅、高效解決方案”的層面。從現(xiàn)在開始#xff0c;每天投入一小段時間#xff0c;結(jié)合前端場景去理解和練習(xí)…對前端開發(fā)者而言學(xué)習(xí)算法絕非為了“炫技”。它是你從“頁面構(gòu)建者”邁向“復(fù)雜系統(tǒng)設(shè)計者”的關(guān)鍵階梯。它將你的編碼能力從“實現(xiàn)功能”提升到“設(shè)計優(yōu)雅、高效解決方案”的層面。從現(xiàn)在開始每天投入一小段時間結(jié)合前端場景去理解和練習(xí)你將會感受到自身技術(shù)視野和問題解決能力的質(zhì)的飛躍。------ 算法資深前端開發(fā)者的進階引擎LeetCode 148. 排序鏈表分治與指針操作1. 題目描述給你鏈表的頭結(jié)點head請將其按升序排列并返回排序后的鏈表。示例 1輸入head [4,2,1,3] 輸出[1,2,3,4]示例 2輸入head [-1,5,3,4,0] 輸出[-1,0,3,4,5]示例 3輸入head [] 輸出[]進階要求你可以在O(n log n)時間復(fù)雜度和常數(shù)級空間復(fù)雜度下對鏈表進行排序嗎2. 問題分析數(shù)據(jù)結(jié)構(gòu)題目處理的是單鏈表。與數(shù)組不同鏈表在內(nèi)存中非連續(xù)無法像數(shù)組一樣通過下標在O(1)時間內(nèi)進行隨機訪問。這一特性直接影響排序算法的選擇。時間復(fù)雜度要求O(n log n)。這提示我們像冒泡排序、插入排序等O(n^2)的算法不符合要求。符合此要求的經(jīng)典算法有歸并排序、快速排序、堆排序?？臻g復(fù)雜度要求常數(shù)級 O(1)。這是一個關(guān)鍵約束。遞歸實現(xiàn)的歸并排序遞歸調(diào)用棧的深度為O(log n)不滿足常數(shù)空間?？焖倥判蜻f歸實現(xiàn)同樣有O(log n)的?？臻g開銷。堆排序在鏈路上實現(xiàn)較為復(fù)雜。解決方案為了滿足O(n log n)時間和O(1)空間我們必須采用迭代、自底向上的歸并排序。這是本題的最優(yōu)解也是考察的核心。3. 解題思路3.1 核心思想自底向上的歸并排序 (Bottom-Up Merge Sort)為什么是歸并排序歸并排序是分治法的典型應(yīng)用。對于鏈表其合并兩個有序鏈表的操作可以在O(n)時間和O(1)空間內(nèi)完成只需要調(diào)整指針這比數(shù)組歸并需要額外空間更具優(yōu)勢。如何滿足O(1)空間—— 迭代法切分 (Split)我們不再使用遞歸來切分鏈表而是使用一個變量subLength表示當前要歸并的子鏈表長度初始為1。合并 (Merge)將鏈表分成若干段長度為subLength的子鏈表。將相鄰的兩個子鏈表進行合并這是一個標準的“合并兩個有序鏈表”問題。合并完成后將subLength加倍重復(fù)上述過程直到subLength大于或等于整個鏈表的長度。關(guān)鍵步驟模擬假設(shè)鏈表為[4, 2, 1, 3]subLength 1: 鏈表視為[4], [2], [1], [3]- 兩兩合并 -[2,4], [1,3]subLength 2: 鏈表視為[2,4], [1,3]- 兩兩合并 -[1,2,3,4]subLength 4: 已排序完成。3.2 實現(xiàn)細節(jié)虛擬頭結(jié)點 (dummyHead)用于簡化鏈表頭節(jié)點變化的邊界情況處理。切分函數(shù) (cut)從給定鏈表頭開始切下指定長度的子鏈表并返回剩余部分的頭節(jié)點。合并函數(shù) (merge)合并兩個有序鏈表返回新鏈表的頭節(jié)點。這是LeetCode 21. 合并兩個有序鏈表的直接應(yīng)用。主循環(huán)外層循環(huán)控制subLength的增長內(nèi)層循環(huán)遍歷整個鏈表進行切分和合并操作。復(fù)雜度分析時間復(fù)雜度O(n log n)。外層循環(huán)O(log n)次內(nèi)層循環(huán)每次遍歷整個鏈表O(n)。空間復(fù)雜度O(1)。只使用了固定的幾個指針變量。4. 各思路代碼實現(xiàn) (JavaScript)4.1 最優(yōu)解迭代歸并排序 (O(n log n), O(1))/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } *//** * param {ListNode} head * return {ListNode} */varsortListfunction(head){// 邊界條件處理if(!head||!head.next)returnhead;// 1. 計算鏈表總長度letlength0;letnodehead;while(node){length;nodenode.next;}// 2. 創(chuàng)建虛擬頭節(jié)點指向原鏈表constdummyHeadnewListNode(0,head);// 3. 自底向上歸并for(letsubLength1;subLengthlength;subLength1){// subLength 每次翻倍letprevdummyHead;// prev 用于連接合并好的子鏈表letcurrdummyHead.next;// curr 是當前待處理部分的起點while(curr){// 3.1 切分出第一個子鏈表 head1lethead1curr;// 走 subLength - 1 步找到 head1 的尾部for(leti1;isubLengthcurr.next;i){currcurr.next;}// 3.2 切分出第二個子鏈表 head2lethead2curr.next;curr.nextnull;// 切斷 head1 與后面的連接currhead2;// 從 head2 開始再走 subLength - 1 步找到 head2 的尾部for(leti1;isubLengthcurrcurr.next;i){currcurr.next;}// 3.3 記錄剩余部分并切斷 head2 與后面的連接letnextnull;if(curr){nextcurr.next;curr.nextnull;}// 3.4 合并 head1 和 head2并將結(jié)果連接到 prev 后面constmergedmergeTwoLists(head1,head2);prev.nextmerged;// 3.5 將 prev 移動到合并后鏈表的末尾準備連接下一組合并結(jié)果while(prev.next){prevprev.next;}// 3.6 curr 移動到剩余部分繼續(xù)處理下一對子鏈表currnext;}}returndummyHead.next;};/** * 合并兩個有序鏈表 (LeetCode 21) * param {ListNode} l1 * param {ListNode} l2 * return {ListNode} */functionmergeTwoLists(l1,l2){constdummynewListNode(0);letcurdummy;while(l1l2){if(l1.vall2.val){cur.nextl1;l1l1.next;}else{cur.nextl2;l2l2.next;}curcur.next;}// 連接剩余部分cur.nextl1?l1:l2;returndummy.next;}4.2 次優(yōu)解遞歸歸并排序 (O(n log n), O(log n))varsortListfunction(head){// 遞歸終止條件if(!head||!head.next)returnhead;// 1. 使用快慢指針找到鏈表中點letslowhead,fasthead.next;while(fastfast.next){slowslow.next;fastfast.next.next;}// 2. 切斷鏈表分成左右兩部分constmidslow.next;slow.nextnull;// 3. 遞歸排序左右兩部分constleftsortList(head);constrightsortList(mid);// 4. 合并兩個有序鏈表returnmergeTwoLists(left,right);};// mergeTwoLists 函數(shù)同上4.3 簡單解不符合要求轉(zhuǎn)為數(shù)組排序 (O(n log n), O(n))varsortListfunction(head){if(!head)returnnull;// 1. 鏈表轉(zhuǎn)數(shù)組constarr[];letcurrhead;while(curr){arr.push(curr.val);currcurr.next;}// 2. 數(shù)組排序arr.sort((a,b)a-b);// 3. 數(shù)組轉(zhuǎn)回鏈表constdummynewListNode(0);currdummy;for(constvalofarr){curr.nextnewListNode(val);currcurr.next;}returndummy.next;};5. 各實現(xiàn)思路的復(fù)雜度、優(yōu)缺點對比思路時間復(fù)雜度空間復(fù)雜度優(yōu)點缺點是否滿足進階要求迭代歸并排序O(n log n)O(1)滿足所有進階要求純指針操作空間效率極致代碼實現(xiàn)相對復(fù)雜邊界條件需仔細處理是遞歸歸并排序O(n log n)O(log n)代碼清晰易于理解和實現(xiàn)分治思想的經(jīng)典體現(xiàn)遞歸調(diào)用棧消耗額外空間不滿足常數(shù)空間要求否轉(zhuǎn)為數(shù)組排序O(n log n)O(n)實現(xiàn)極其簡單快速利用語言原生API需要額外O(n)空間存儲數(shù)組和新建鏈表破壞了原鏈表節(jié)點否6. 總結(jié)6.1 技術(shù)要點回顧鏈表特性無隨機訪問能力O(1)時間的插入/刪除是其優(yōu)勢。排序算法需要適應(yīng)這一特性。歸并排序的適應(yīng)性對于數(shù)據(jù)結(jié)構(gòu)歸并排序的合并操作可以非常高效地通過改變指針來實現(xiàn)無需像數(shù)組一樣開辟新空間來存儲中間結(jié)果。雙指針技巧快慢指針在遞歸法中用于高效找到鏈表中點。指針操作在迭代法的cut和merge過程中對指針next的精確控制是正確實現(xiàn)的關(guān)鍵也是前端開發(fā)者需要熟練掌握的核心技能之一。虛擬頭節(jié)點一個極其有用的技巧可以統(tǒng)一處理鏈表頭節(jié)點可能發(fā)生變化的情況簡化代碼邏輯。6.2 在前端開發(fā)中的實際應(yīng)用場景雖然前端中直接操作鏈表排序的場景不多但本題所鍛煉的能力具有廣泛的遷移價值復(fù)雜狀態(tài)管理在大型前端應(yīng)用如使用Vuex、Redux中管理一條按時間、優(yōu)先級排序的操作日志流或消息列表其底層優(yōu)化思想與歸并排序類似——將大規(guī)模數(shù)據(jù)分塊處理再合并。高性能列表渲染在實現(xiàn)虛擬滾動或無限加載列表時數(shù)據(jù)可能是分頁/分塊到達的。你需要將新到達的有序數(shù)據(jù)塊與現(xiàn)有的有序列表進行高效合并并更新DOM這個過程就是mergeTwoLists的變體。優(yōu)化此合并過程能極大提升列表滾動的流暢度。構(gòu)建工具與數(shù)據(jù)處理在編寫Webpack插件、Babel插件或進行Node.js流式數(shù)據(jù)處理時經(jīng)常會遇到需要將多個有序序列如源映射片段、日志事件合并成一個有序序列的場景。思維模式提升分治思想是解決復(fù)雜問題的利器。無論是前端的組件設(shè)計將大組件拆分為可復(fù)用的小組件、性能優(yōu)化將長任務(wù)分解為多個微任務(wù)還是工程化中的任務(wù)拆分其核心邏輯與歸并排序一脈相承。