亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

LeetCode 之 JavaScript 解答第23題 —— 合并K個有序鏈表（Merge K S

zhou_you / 2088人閱讀

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(guān)聯(lián)原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動態(tài)規(guī)劃的明顯區(qū)別。

Time：2019/4/10
Title: Merge K Sorted Lists
Difficulty: Difficulty
Author: 小鹿

題目：Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

合并?k?個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
Solve: ▉ 算法思路 
如果我們完成了簡單的基于兩個單鏈表的合并之后，對于這個題來說，考察點(diǎn)是分治算法，我認(rèn)為還有一個考察點(diǎn)就是遞歸調(diào)用，分治的同時經(jīng)常用遞歸來解決。
1、本道題可以借助歸并排序的思想，稍加改造就可以解決。


2、將數(shù)組中的鏈表分治，就是不斷的將數(shù)組中的鏈表中間劃分，分別合并，然后整體合并成一個大鏈表。
▉ 代碼實(shí)現(xiàn) 
/**
  * @param {number[]} nums
  * @return {number[]}
  * 功能：合并 k 個鏈表
  * 邊界條件：
  * 1）判斷數(shù)組是否為空
  * 2）判斷數(shù)組長度為 1 時
  * 3）判斷數(shù)組長度為 2 時
  * 4）判斷數(shù)組長度大于 2 時
  */
var mergeKLists = function(lists) {
    // 當(dāng) lists 中有一個鏈表時
    if(lists.length == 0){
        return null;
    }else if(lists.length == 1){
        // 判斷數(shù)組長度為 1 時
        return lists[0];
    }else if(lists.length == 2){
        // 判斷數(shù)組長度為 2 時
        return mergeTwoLists(lists[0],lists[1]);
    }else{
        // 判斷數(shù)組長度大于 2 時
        // 取數(shù)組的中部坐標(biāo)
        let middle = Math.floor(lists.length/2);
        // 取左右兩邊數(shù)組
        let leftList = lists.slice(0,middle);
        let rightList = lists.slice(middle);
        // 遞歸、分割、合并
        return mergeTwoLists(mergeKLists(leftList),mergeKLists(rightList));
    }       
};
//兩個鏈表合并
var mergeTwoLists = function(l1, l2) {
    let result = null;

    //終止條件
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //判斷數(shù)值大小遞歸
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeTwoLists(l2.next,l1);
    }
    
    //返回結(jié)果
    return result;
};
▉ 擴(kuò)展：分治算法 
分治算法經(jīng)常和遞歸一塊使用，所謂分治算法，顧名思義，分而治之，最基本的分之算法在歸并排序、快速排序都有用到。也就是將原問題劃分成 n 個規(guī)模較小，并且結(jié)構(gòu)與原問題相似的子問題，遞歸地解決這些子問題，然后再合并其結(jié)果，就得到原問題的解。
1、分治算法遞歸每層操作
分解：將原問題分解成一系列的子問題。


解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；


合并：將子問題的結(jié)果合并成原問題。
2、分治算法滿足的條件
可分解：原問題與分解成的小問題具有相同的模式；


無關(guān)聯(lián)：原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動態(tài)規(guī)劃的明顯區(qū)別。


終止條件：具有分解終止條件；


合并不能太復(fù)雜：可以將子問題合并成原問題，而這個合并操作的復(fù)雜度不能太高，否則就起不到減小算法總體復(fù)雜度的效果了。

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/103456.html

相關(guān)文章

  • LeetCode 之 JavaScript 解答第21題 —— 合并兩個有序鏈表（Merge Two

    摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數(shù)的參數(shù)和返回值是什么參數(shù)是兩個合并的鏈表結(jié)點(diǎn)頭結(jié)點(diǎn)。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿 題目：Merge Two Sorted Lists Merge two sorted linked lists and re...

    wdzgege 評論0 收藏0

  • JS算法題之leetcode(1~10)

    摘要：先去空白，去掉空白之后取第一個字符，判斷正負(fù)符號，若是英文直接返回，若數(shù)字則不取?；匚臄?shù)題目描述判斷一個整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

    SoapEye 評論0 收藏0

  • 第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

    馬上就要開始啦這次共組織15個組隊(duì)學(xué)習(xí) 涵蓋了AI領(lǐng)域從理論知識到動手實(shí)踐的內(nèi)容 按照下面給出的最完備學(xué)習(xí)路線分類 難度系數(shù)分為低、中、高三檔 可以按照需要參加 - 學(xué)習(xí)路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

    dinfer 評論0 收藏0

  • PHPer也刷《劍指Offer》之鏈表

    摘要：劍指中鏈表相關(guān)題目俗話說光說不練假把式，既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關(guān)題目。題目分析合并兩個排序的鏈表，需要分別比較兩個鏈表的每個值，然后改變指針。 溫故知新 鏈表由一個一個的作為節(jié)點(diǎn)的對象構(gòu)成的，每一個節(jié)點(diǎn)都有指向下一個節(jié)點(diǎn)的指針，最后一個節(jié)點(diǎn)的指針域指向空。每個節(jié)點(diǎn)可以存儲任何數(shù)據(jù)類型。 根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、...

    daydream 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<