- 📢前言
- 🌲原題樣例
- 🌻C#方法一：遞回
- 🌻Java 方法一：遞回
- 🐢 遞回 問題
- 💬總結
📢前言
- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
- 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
- 🌲 今天是力扣演算法題持續打卡第12天🎈！
- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲原題樣例
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
提示：
- 兩個
鏈表的節點數目范圍是 [0, 50] - -100 <= Node.val <= 100
- l1 和 l2 均按
非遞減順序排列
🌻C#方法一：遞回
思路決議
我們可以如下遞回地定義兩個鏈表里的 merge 操作（忽略邊界情況，比如空鏈表等）：
也就是說，兩個鏈表頭部值較小的一個節點與剩下元素的 merge 操作結果合并，
我們直接將以上遞回程序建模，同時需要考慮邊界情況，
如果 l1 或者 l2 一開始就是空鏈表 ，那么沒有任何操作需要合并，所以我們只需要回傳非空鏈表，
否則，我們要判斷 l1 和 l2 哪一個鏈表的頭節點的值更小，然后遞回地決定下一個添加到結果里的節點，
如果兩個鏈表有一個為空，遞回結束，
代碼：
public class Solution {
public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = MergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = MergeTwoLists(l1, l2.next);
return l2;
}
}
}
執行結果
通過
執行用時：80 ms，在所有 C# 提交中擊敗了97.08%的用戶
記憶體消耗：25.7 MB，在所有 C# 提交中擊敗了81.30%的用戶
復雜度分析
時間復雜度：O(n+m)
空間復雜度：O((n+m)
🌻Java 方法一：遞回
思路決議
該解題方法與C#思路一致，代碼有所不同
代碼
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
執行結果
通過
執行用時：0 ms，在所有 Java 提交中擊敗了100%的用戶
記憶體消耗：37.6 MB，在所有 Java 提交中擊敗了89.42%的用戶
復雜度分析
時間復雜度：O(n+m)
空間復雜度：O((n+m)
🐢 遞回 問題
但是使用遞回有個問題很頭疼~
遞回解法總是給人一種“只可意會不可言傳”的感覺，代碼一看就懂，自己動手一寫就呆住了，很難受，
追溯原因的話，一是我們練習不夠，二是理解不夠，還是要多多練習加油才行呀！
函式在運行時呼叫自己，這個函式就叫遞回函式，呼叫的程序叫做遞回，
比如定義函式f(x)=x+f(x?1)
💬總結
- 今天是力扣演算法題打卡的第十二天！
- 文章采用 C# 和 Java 兩種編程語言進行解題
- 有時候一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
- 那今天的演算法題分享到此結束啦，明天再見！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294938.html
標籤：其他