電商網(wǎng)站怎么做支付廣州專門做seo的公司
算法沉淀——遞歸
- 01.漢諾塔問題
- 02.合并兩個有序鏈表
- 03.反轉(zhuǎn)鏈表
- 04.兩兩交換鏈表中的節(jié)點(diǎn)
- 05.Pow(x, n)
遞歸是一種通過調(diào)用自身的方式來解決問題的算法。在遞歸算法中，問題被分解為更小的相似子問題，然后通過對這些子問題的解進(jìn)行組合來解決原始問題。遞歸算法通常包含兩個主要部分：
- 基本情況（Base Case）： 定義問題的最小規(guī)模，直接解答而不再進(jìn)行遞歸?；厩闆r是遞歸算法的出口，防止算法陷入無限遞歸。
- 遞歸步驟： 在問題規(guī)模較大時，將問題劃分為相似但規(guī)模較小的子問題，并通過遞歸調(diào)用解決這些子問題。遞歸調(diào)用自身是遞歸算法的核心。
遞歸算法在解決許多問題上非常強(qiáng)大，尤其是對于那些可以通過分解為子問題并且存在重疊子問題的情況。遞歸通常使算法更加簡潔、清晰，但需要謹(jǐn)慎處理基本情況，以避免無限遞歸。
經(jīng)典的遞歸問題包括漢諾塔問題、階乘計(jì)算、斐波那契數(shù)列等。遞歸也在許多算法和數(shù)據(jù)結(jié)構(gòu)中發(fā)揮著重要的作用，例如樹的遍歷、圖的深度優(yōu)先搜索等。
如何理解遞歸？
1.遞歸展開的細(xì)節(jié)圖
2.二叉樹中的題目
3.宏觀看待遞歸的過程
1.不要在意遞歸的細(xì)節(jié)展開圖
2.把遞歸的函數(shù)當(dāng)成一個黑盒
3.相信這個黑盒一定能完成這個任務(wù)
如何寫好遞歸？
1.先找到相同的子問題!!!->函數(shù)頭的設(shè)計(jì)
2.只關(guān)心某一個子問題是如何解決的 ->函數(shù)體的書寫
3.注意一下遞歸函數(shù)的出口即可
01.漢諾塔問題
題目鏈接：https://leetcode.cn/problems/hanota-lcci/
在經(jīng)典漢諾塔問題中，有 3 根柱子及 N 個不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個盤子只能放在更大的盤子上面)。移動圓盤時受到以下限制:
(1) 每次只能移動一個盤子;
(2) 盤子只能從柱子頂端滑出移到下一根柱子;
(3) 盤子只能疊在比它大的盤子上。
請編寫程序，用棧將所有盤子從第一根柱子移到最后一根柱子。
你需要原地修改棧。
示例1:
輸入：A = [2, 1, 0], B = [], C = []輸出：C = [2, 1, 0]
示例2:
輸入：A = [1, 0], B = [], C = []輸出：C = [1, 0]
提示:
- A中盤子的數(shù)目不大于14個。
思路
對于這類問題我們可以使用數(shù)學(xué)中的歸結(jié)思想，先畫圖分析由1到n的情況，我們可以總結(jié)出下面這三個步驟
代碼
class Solution {void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n){if(n==1){C.push_back(A.back());A.pop_back();return;}dfs(A,C,B,n-1);C.push_back(A.back());A.pop_back();dfs(B,A,C,n-1);}
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A,B,C,A.size());}
};
- 定義一個私有的遞歸函數(shù)
dfs，該函數(shù)將 A 柱上的 n 個盤子通過 B 柱移動到 C 柱。參數(shù)A、B和C分別表示三個柱子的盤子狀態(tài)，n表示要移動的盤子數(shù)量。 - 在遞歸函數(shù)中，當(dāng)只有一個盤子時，直接將 A 柱的盤子移到 C 柱上，然后返回。
- 在遞歸函數(shù)中，先將 A 柱上的 n-1 個盤子通過 C 柱移動到 B 柱上，然后將 A 柱上的最后一個盤子移動到 C 柱上，最后將 B 柱上的 n-1 個盤子通過 A 柱移動到 C 柱上。
- 在公有函數(shù)
hanota中，調(diào)用遞歸函數(shù)dfs，傳入 A、B、C 三個柱子的狀態(tài)和盤子數(shù)量。
02.合并兩個有序鏈表
題目鏈接：https://leetcode.cn/problems/merge-two-sorted-lists/
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
提示：
- 兩個鏈表的節(jié)點(diǎn)數(shù)目范圍是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非遞減順序 排列
思路
這里我們?nèi)绻麆澐譃樽訂栴}，每次就拿出最小的那個節(jié)點(diǎn)當(dāng)做頭節(jié)點(diǎn)，拼接剩下的當(dāng)前節(jié)點(diǎn)尾部的節(jié)點(diǎn)和另一個鏈表的頭節(jié)點(diǎn)相比較的更小的點(diǎn)，最后誰被拼接完了，就直接拼接另一條鏈表剩下的，這樣不難看出，每次的步驟都是重復(fù)的，于是我們可以使用遞歸的思想來解決這道問題。
代碼
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1) return list2;if(!list2) return list1;if(list1->val<=list2->val){list1->next=mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list2->next,list1);return list2;}}
};
- 如果
list1為空，說明第一個鏈表為空，直接返回list2。 - 如果
list2為空，說明第二個鏈表為空，直接返回list1。 - 接下來比較
list1和list2的頭節(jié)點(diǎn)的值，選擇較小的節(jié)點(diǎn)作為新鏈表的頭節(jié)點(diǎn)。 - 如果
list1的頭節(jié)點(diǎn)值小于等于list2的頭節(jié)點(diǎn)值，將list1的下一個節(jié)點(diǎn)與list2合并，并返回list1作為新鏈表的頭節(jié)點(diǎn)。 - 如果
list2的頭節(jié)點(diǎn)值小于list1的頭節(jié)點(diǎn)值，將list2的下一個節(jié)點(diǎn)與list1合并，并返回list2作為新鏈表的頭節(jié)點(diǎn)。
03.反轉(zhuǎn)鏈表
題目鏈接：https://leetcode.cn/problems/reverse-linked-list/
給你單鏈表的頭節(jié)點(diǎn) head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
提示：
- 鏈表中節(jié)點(diǎn)的數(shù)目范圍是
[0, 5000] -5000 <= Node.val <= 5000
**進(jìn)階：**鏈表可以選用迭代或遞歸方式完成反轉(zhuǎn)。你能否用兩種方法解決這道題？
思路
若我們直接遍歷到最后的節(jié)點(diǎn)再逐個向前改變指向，在每次接入前一個節(jié)點(diǎn)時，將它的next指向空，最終返回頭節(jié)點(diǎn)即可。
- 遞歸函數(shù)的含義：交給你?個鏈表的頭指針，你幫我逆序之后，返回逆序后的頭結(jié)點(diǎn)；
- 函數(shù)體：先把當(dāng)前結(jié)點(diǎn)之后的鏈表逆序，逆序完之后，把當(dāng)前結(jié)點(diǎn)添加到逆序后的鏈表后面即可；
- 遞歸出口：當(dāng)前結(jié)點(diǎn)為空或者當(dāng)前只有?個結(jié)點(diǎn)的時候，不用逆序，直接返回
代碼
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head->next) return head;ListNode* newhead = reverseList(head->next);head->next->next=head;head->next=nullptr;return newhead;}
};
04.兩兩交換鏈表中的節(jié)點(diǎn)
題目鏈接：https://leetcode.cn/problems/swap-nodes-in-pairs/
給你一個鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：
輸入：head = []
輸出：[]
示例 3：
輸入：head = [1]
輸出：[1]
提示：
- 鏈表中節(jié)點(diǎn)的數(shù)目在范圍
[0, 100]內(nèi) 0 <= Node.val <= 100
思路
我們將問題劃分為子問題，先交換當(dāng)前節(jié)點(diǎn)的下兩個節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向遞歸操作的結(jié)果，返回新的頭節(jié)點(diǎn)。
代碼
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 如果鏈表為空或者只有一個節(jié)點(diǎn)，無需交換，直接返回原鏈表頭指針if (!head || !head->next)return head;// 遞歸調(diào)用，交換當(dāng)前節(jié)點(diǎn)的下兩個節(jié)點(diǎn)ListNode* tmp = swapPairs(head->next->next);// 將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)ListNode* ret = head->next;// 將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，實(shí)現(xiàn)交換head->next->next = head;// 將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向遞歸操作的結(jié)果head->next = tmp;// 返回新的頭節(jié)點(diǎn)return ret;}
};
if (!head || !head->next)：檢查鏈表是否為空或者只有一個節(jié)點(diǎn)。如果是，直接返回原鏈表頭指針，因?yàn)椴恍枰M(jìn)行交換。ListNode* tmp = swapPairs(head->next->next);：遞歸調(diào)用swapPairs函數(shù)，傳入當(dāng)前節(jié)點(diǎn)的下兩個節(jié)點(diǎn)。這樣就會從鏈表的末尾開始，每次交換兩個相鄰的節(jié)點(diǎn)，然后返回新的頭節(jié)點(diǎn)。ListNode* ret = head->next;：將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)，因?yàn)樵诮粨Q過程中，它會變成新的頭節(jié)點(diǎn)。head->next->next = head;：將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，實(shí)現(xiàn)交換操作。head->next = tmp;：將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向遞歸操作的結(jié)果，即當(dāng)前節(jié)點(diǎn)的下兩個節(jié)點(diǎn)交換后的頭節(jié)點(diǎn)。return ret;：返回新的頭節(jié)點(diǎn)，作為上層遞歸調(diào)用的結(jié)果。
05.Pow(x, n)
題目鏈接：https://leetcode.cn/problems/powx-n/
實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的整數(shù) n 次冪函數(shù)（即，xn ）。
示例 1：
輸入：x = 2.00000, n = 10
輸出：1024.00000
示例 2：
輸入：x = 2.10000, n = 3
輸出：9.26100
示例 3：
輸入：x = 2.00000, n = -2
輸出：0.25000
解釋：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一個整數(shù)- 要么
x不為零，要么n > 0。 -104 <= xn <= 104
思路
這里我們可以使用二分的思想，可以快速提高效率，例如將3的32次方分為兩個3的16次方相乘，不斷向下遞歸，最終返回相乘結(jié)果，只不過這里需要注意負(fù)數(shù)和奇偶次方問題需要單獨(dú)判斷。
代碼
class Solution {
public:double myPow(double x, int n) {// 如果指數(shù)n為負(fù)數(shù)，將問題轉(zhuǎn)化為計(jì)算 x^(-n)，即取倒數(shù)return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);}double Pow(double x, long long n) {// 遞歸終止條件：n為0時，任何數(shù)的0次方都為1if (n == 0) return 1.0;// 遞歸調(diào)用，計(jì)算 x^(n/2)double tmp = Pow(x, n / 2);// 如果n為奇數(shù)，返回 tmp * tmp * xif (n % 2)return tmp * tmp * x;else // 如果n為偶數(shù)，返回 tmp * tmpreturn tmp * tmp;}
};
return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);：根據(jù)指數(shù)n的正負(fù)情況，決定調(diào)用正指數(shù)或者取倒數(shù)的遞歸函數(shù)。當(dāng)n為負(fù)數(shù)時，將其轉(zhuǎn)化為正數(shù)計(jì)算，并返回結(jié)果的倒數(shù)。double Pow(double x, long long n)：遞歸函數(shù)，用于計(jì)算 x^n。if (n == 0) return 1.0;：遞歸終止條件。當(dāng)指數(shù)n為0時，任何數(shù)的0次方都為1。double tmp = Pow(x, n / 2);：遞歸調(diào)用，計(jì)算 x^(n/2)。這里利用了指數(shù)冪的性質(zhì)，將問題規(guī)模減半，減少了計(jì)算量。if (n % 2)：判斷n是否為奇數(shù)。return tmp * tmp * x;：如果n為奇數(shù)，返回 tmp * tmp * x，這是因?yàn)?x^n = (x(n/2))2 * x。
n) : Pow(x, n);`：根據(jù)指數(shù)n的正負(fù)情況，決定調(diào)用正指數(shù)或者取倒數(shù)的遞歸函數(shù)。當(dāng)n為負(fù)數(shù)時，將其轉(zhuǎn)化為正數(shù)計(jì)算，并返回結(jié)果的倒數(shù)。double Pow(double x, long long n)：遞歸函數(shù)，用于計(jì)算 x^n。if (n == 0) return 1.0;：遞歸終止條件。當(dāng)指數(shù)n為0時，任何數(shù)的0次方都為1。double tmp = Pow(x, n / 2);：遞歸調(diào)用，計(jì)算 x^(n/2)。這里利用了指數(shù)冪的性質(zhì)，將問題規(guī)模減半，減少了計(jì)算量。if (n % 2)：判斷n是否為奇數(shù)。return tmp * tmp * x;：如果n為奇數(shù)，返回 tmp * tmp * x，這是因?yàn)?x^n = (x(n/2))2 * x。return tmp * tmp;：如果n為偶數(shù)，返回 tmp * tmp，這是因?yàn)?x^n = (x(n/2))2。