成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

wdzgege / 1122人閱讀

摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數(shù)的參數(shù)和返回值是什么參數(shù)是兩個(gè)合并的鏈表結(jié)點(diǎn)頭結(jié)點(diǎn)。返回值是合并后的鏈表。

Time：2019/4/9
Title: Merge Two Sorted Lists
Difficulty: Easy
Author: 小鹿

題目：Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Solve:
▉ 算法思路
1、正常思路，循環(huán)遍歷迭代比較大小，每取出一個(gè)數(shù)據(jù)，將小數(shù)據(jù)加入到額外的數(shù)組中去，直到比較完畢，將其中一個(gè)剩余的數(shù)組追加到額外的數(shù)組尾部。


2、遞歸思路，滿足遞歸的三個(gè)條件：



將問題能不能化為子問題去解決？


子問題的解決方式是否和總問題相似？


是否有終止條件？
▉ 遞歸實(shí)現(xiàn)
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;
};
▉ 怎么理解遞歸？
其實(shí)遞歸最難的就是我們應(yīng)該怎么去理解它，當(dāng)我們完全理解了遞歸之后，就會(huì)發(fā)現(xiàn)遞歸非常方便，代碼簡潔。
我們經(jīng)常理解遞歸會(huì)陷入到遞歸的細(xì)節(jié)上去，往往只遞，歸的時(shí)候就完全模糊了，我也試著找了網(wǎng)上的關(guān)于遞歸解釋的，這么說吧，關(guān)于遞歸理解和使用，只有總結(jié)出自己的一套理解方法，才能真正的掌握遞歸，下面總結(jié)一下我自己理解的遞歸。

1、明確遞歸可以解決什么問題，也就是上邊所講到的解決的問題應(yīng)該滿足遞歸的三個(gè)條件。詳細(xì)分開講解：

將問題劃分為子問題：如果我們判斷該問題可以用遞歸解決了，比如合并兩個(gè)鏈表中比較結(jié)點(diǎn)大小，然后加入到新鏈表，然后在比較下一個(gè)結(jié)點(diǎn)大小，這個(gè)過程就是一個(gè)將問題化為子問題的過程，比較當(dāng)前結(jié)點(diǎn)大小先要比較后一個(gè)節(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)的大小，可以理解成“遞”的過程。（就好比一扇扇包含關(guān)系的大門，問一共有幾所大門，你拿著要是去打開，發(fā)現(xiàn)里邊還有一扇，然后再打開，發(fā)現(xiàn)還有一扇，直到最后一扇。通常我們使用迭代循環(huán)來解決這個(gè)問題，就好比打開一扇大門就 加一；而遞歸要做的就是當(dāng)大門全部打開的時(shí)候，從里往外走關(guān)閉大門的時(shí)候統(tǒng)計(jì)大門的數(shù)量）

尋找終止條件：遞歸必須有個(gè)終止條件，也就是子問題的解決方案，如果沒有終止條件，問題就不會(huì)得到解答。如上方合并鏈表的時(shí)候，經(jīng)過遞歸不斷的比較下一結(jié)點(diǎn)，知道其中一個(gè)鏈表比較完畢為空了，結(jié)果返回第二個(gè)鏈表，也就是達(dá)到了終止的條件，開始“歸”的過程。

遞推公式：你會(huì)問了，怎么寫出遞推公式呢？既然終止條件有了，那我們開始找出遞歸公式，下面是我自己總結(jié)出來的經(jīng)驗(yàn)。

① 一看參數(shù)和 return。什么意思呢？比如上方合并鏈表的代碼，分別明確函數(shù)的參數(shù)和返回值是什么？參數(shù)是兩個(gè)合并的鏈表結(jié)點(diǎn)頭結(jié)點(diǎn)。返回值是合并后的鏈表。

② 二湊參數(shù)和return。就是說我們要去按照參數(shù)和返回值去用遞歸偽造它，比較完成第一個(gè)結(jié)點(diǎn)，當(dāng)然傳入第二個(gè)節(jié)點(diǎn)，返回第一個(gè)結(jié)點(diǎn)到新鏈表尾部，那么遞歸就會(huì)返回新鏈表的下一結(jié)點(diǎn)。要屏蔽掉遞歸的細(xì)節(jié)，只看參數(shù)和返回值。

▉ 遞歸缺點(diǎn)
有時(shí)候問題可以使用遞歸，但是由于遞歸的缺點(diǎn)會(huì)放棄使用。
1、遞歸警惕堆棧溢出。


2、警惕遞歸重復(fù)元素計(jì)算。


3、遞歸的高空間復(fù)雜度。
▉ 怎么正確寫出遞歸代碼？
1、將問題化為子問題。
2、解決子問題。


3、尋找終止條件。


4、寫出遞歸公式。


5、將遞推公式轉(zhuǎn)化為代碼。

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

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

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

相關(guān)文章

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

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

    zhou_you 評論0 收藏0

  • LeetCode 21：合并兩個(gè)有序鏈表 Merge Two Sorted Lists

    摘要：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。無非是依次將兩個(gè)鏈表每個(gè)節(jié)點(diǎn)的值對比，取出值較小的節(jié)點(diǎn)，添加到新鏈表末尾。將剩余鏈表傳回遞歸函數(shù)。 將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。 Merge two sorted linked lists and return it as a n...

    LeviDing 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評論0 收藏0

  • leetcode21 Merge Two Sorted Lists 將兩個(gè)有序鏈表組合成一個(gè)新的有

    摘要：題目要求翻譯過來就是將兩個(gè)有序的鏈表組合成一個(gè)新的有序的鏈表思路一循環(huán)在當(dāng)前兩個(gè)鏈表的節(jié)點(diǎn)都是非空的情況下比較大小，較小的添入結(jié)果鏈表中并且獲得較小節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。 題目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...

    BothEyes1993 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<