往期文章（希望小伙伴們?cè)诳催@篇文章之前，看一下往期文章）
（1）遞歸、搜索與回溯算法（專題零：解釋回溯算法中涉及到的名詞）【回溯算法入門必看】-CSDN博客
接下來我會(huì)用幾道題，來讓同學(xué)們利用我在專題零中提到的遞歸的宏觀思想來解決這些題目。
目錄
1. 漢諾塔
2.?合并兩個(gè)有序鏈表
3. 反轉(zhuǎn)鏈表
4. 兩兩交換鏈表中的結(jié)點(diǎn)
5. 快速冪
解法一? 暴力循環(huán)
解法二? 不斷拆分
解法三? 利用了二進(jìn)制的特點(diǎn)
1. 漢諾塔
這道題可以說是遞歸最經(jīng)典的題目之一，接下來我們就從這道題入手，重新認(rèn)識(shí)一下遞歸是什么？
力扣題目鏈接
解析：
?文章來源地址http://www.zghlxwxcb.cn/news/detail-824749.html
總結(jié)：我們想知道n個(gè)盤子的次數(shù)，記住了，在求解f(n)的時(shí)候，我們直接默認(rèn)f(n - 1)已經(jīng)完了就可以了！這個(gè)在前面已經(jīng)解釋過了，在此不再鰲述。我們將n-1個(gè)盤子當(dāng)作一個(gè)整體：這就是類似于分治求解子問題的思想
那么當(dāng)由3個(gè)盤子時(shí)，就有公式：f(3,x,y,z) = f(2,x,z,y),x->z,f(2,y,x,z)；當(dāng)有4個(gè)盤子時(shí)，就有公式：f(4,x,y,z) = f(3,x,z,y),x->z,f(3,y,x,z).從而推出f(n,x,y,z) = f(n,x,z,y),x->z,f(n,y,x,z)!
綜上所述：也就是說我們想移動(dòng)n個(gè)盤子，就需要先移動(dòng)n - 1個(gè)盤子；移動(dòng)n - 1個(gè)盤子，就需要先移動(dòng)n - 2個(gè)盤子 ………………；移動(dòng)2個(gè)盤子，就必須先移動(dòng)1個(gè)盤子；
（1）而移動(dòng)1個(gè)盤子就是遞歸的終止條件
（2）而n個(gè)盤子變成n - 1個(gè)盤子就是遞歸的大問題變成小問題的方法
宏觀角度分析遞歸：
再來回顧，宏觀的細(xì)節(jié)
- 一：不要在意遞歸的細(xì)節(jié)展開圖
- 二：把遞歸的函數(shù)當(dāng)成一個(gè)“黑盒”
- 三：我們的無條件的相信“黑盒”可以為我們解決當(dāng)前的子問題（再次強(qiáng)調(diào)，遞歸中的每個(gè)子問題的解題步驟都是一樣）
具體構(gòu)建一個(gè)遞歸算法：
（1）創(chuàng)建函數(shù)頭 ——> 從重復(fù)子問題入手，將x柱子上的盤子，借助y柱子轉(zhuǎn)移到z柱子上。從而有函數(shù)頭為：dfs(int x,int y,int z,int n); x、y和z代表了柱子，n代表現(xiàn)在多少個(gè)盤子需要移動(dòng)。x是開始柱，y是中轉(zhuǎn)柱，z是目的柱。
（2）確定函數(shù)體 ——> 無條件相信他能幫我們解決每一個(gè)子問題的。
重復(fù)的子問題如下：
- 如從 x 號(hào)柱子將n - 1個(gè)盤子借助 z 號(hào)柱子移動(dòng)到 y?號(hào)柱子上
- 將 x 號(hào)柱子將最后一個(gè)盤子移動(dòng)到 z?號(hào)柱子上
- 將 y?號(hào)柱子上的n - 1個(gè)盤子移動(dòng)到 z?號(hào)柱子上
從而有函數(shù)體為：
① dfs(x,z,y,n - 1); ② x.back -> z; ③ dfs(y,x,z,n - 1);
（3）遞歸出口：當(dāng)剩下一個(gè)盤子的時(shí)候，也就是n == 1時(shí)。x.back -> z即可。
//宏觀角度分析遞歸
//1.創(chuàng)建函數(shù)頭
//2.確定函數(shù)體，無條件相信他能幫我們解決每一個(gè)子問題的
//3.遞歸出口
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
dfs(A,B,C,A.size());
}
public void dfs(List<Integer> x,List<Integer> y,List<Integer> z,int size){
//遞歸出口
if(size == 1){
z.add(x.remove(x.size() - 1));
return;
}
//封裝一個(gè)小黑盒
//將x柱上的size - 1個(gè)盤子通過z柱子移動(dòng)到y(tǒng)柱子上
dfs(x,z,y,size - 1);
//將a柱上的最后一個(gè)盤子移動(dòng)到c柱子上
z.add(x.remove(x.size() - 1));
//將b柱上的size - 1個(gè)盤子通過a柱子移動(dòng)到c柱子上
dfs(y,x,z,size - 1);
}
2.?合并兩個(gè)有序鏈表
力扣題目鏈接
解析：
（1）遞歸函數(shù)的含義：交給你兩個(gè)鏈表的頭結(jié)點(diǎn)，你幫我把它們合并起來，并且返回合并后的頭結(jié)點(diǎn)。
（2）函數(shù)體：選擇兩個(gè)頭結(jié)點(diǎn)中較?的結(jié)點(diǎn)作為最終合并后的頭結(jié)點(diǎn)，然后將剩下的鏈表交給遞歸函數(shù)去處理。
（3）遞歸出?：當(dāng)某?個(gè)鏈表為空的時(shí)候，返回另外?個(gè)鏈表。?
// 法一：遞歸法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 遞歸出口：當(dāng)l1或者l2為空，就返回另一個(gè)不為空的鏈表
if (l1 == null)
return l2;
if (l2 == null)
return l1;
//如果l1的值小于l2，那么就讓l1作為頭結(jié)點(diǎn)，剩下的結(jié)點(diǎn)繼續(xù)比較
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
3. 反轉(zhuǎn)鏈表
力扣題目鏈接
?
解析：?
（1）遞歸函數(shù)的含義：交給你?個(gè)鏈表的頭指針，你幫我逆序之后，返回逆序后的頭結(jié)點(diǎn)。
（2）函數(shù)體：先把當(dāng)前結(jié)點(diǎn)之后的鏈表逆序，逆序完之后，把當(dāng)前結(jié)點(diǎn)添加到逆序后的鏈表后?即可。（相同的子問題）
（3）遞歸出?：當(dāng)前結(jié)點(diǎn)為空或者當(dāng)前只有?個(gè)結(jié)點(diǎn)的時(shí)候，不?逆序，直接返回。
public ListNode reverseList(ListNode head) {
return dfs(head);
}
public ListNode dfs(ListNode h){
//遞歸出口：直接到找最后一個(gè)結(jié)點(diǎn)，類似后序遍歷
if(h == null || h.next == null){
return h;
}
//找最后一個(gè)結(jié)點(diǎn)
ListNode newNode = dfs(h.next);
//從倒數(shù)第二個(gè)結(jié)點(diǎn)開始
h.next.next = h;
h.next = null;
return newNode;
}
4. 兩兩交換鏈表中的結(jié)點(diǎn)
力扣題目鏈接
解析：
（1）遞歸函數(shù)的含義：交給你?個(gè)鏈表，將這個(gè)鏈表兩兩交換?下，然后返回交換后的頭結(jié)點(diǎn)。
（2）函數(shù)體：先去處理?下第?個(gè)結(jié)點(diǎn)往后的鏈表，然后再把當(dāng)前的兩個(gè)結(jié)點(diǎn)交換?下，連接上后?處理后的鏈表。（相同的子問題）
（3）遞歸出?：當(dāng)前結(jié)點(diǎn)為空或者當(dāng)前只有?個(gè)結(jié)點(diǎn)的時(shí)候，不?交換，直接返回。?
//后序遍歷
public ListNode swapPairs(ListNode head) {
//鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 100] 內(nèi)
//如果只剩下一個(gè)結(jié)點(diǎn)就沒必要交換了，因?yàn)槭莾蓛山粨Q
if(head == null || head.next == null){
return head;
}
//先去交換在我之后之后的結(jié)點(diǎn)
ListNode newNode = swapPairs(head.next.next);
ListNode ret = head.next;
head.next = newNode;
ret.next = head;
return ret;
}?要先修改后面結(jié)點(diǎn)，再能修改當(dāng)前結(jié)點(diǎn)，很類似后序遍歷的方式。
5. 快速冪
力扣題目鏈接
解法一? 暴力循環(huán)
public double myPow(double x, int n) {
double ret = 1;
int tmp = n;
if(n < 0) n = -n;
for(int i = 1;i <= n;i++){
ret *= x;
}
if(tmp < 0) ret = 1.0 / ret;
return ret;
}
暴力循環(huán)可以解決較小的冪，當(dāng)冪的值比較大就會(huì)報(bào)超時(shí)的錯(cuò)誤?。?！
所以有了如下兩個(gè)改進(jìn)方案：
?
解法二? 不斷拆分
（1）遞歸函數(shù)的含義：求出?x 的 n 次?是多少，然后返回。
（2）函數(shù)體：先求出 x 的?n / 2 次?是多少，然后根據(jù)?n 的奇偶，得出?x 的?n 次?是多少。
（3）遞歸出?：當(dāng)?n 為?0 的時(shí)候，返回?1 即可?。
//第二種方法：
public double myPow(double x, int n) {
return n < 0 ? 1.0 / pow(x,-n) : pow(x,n);
}
public double pow(double x,int n){
if(n == 0)
return 1.0;
double tmp = pow(x,n/2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
解法三? 利用了二進(jìn)制的特點(diǎn)
例如算:
分解：
（1）而、、是倍乘關(guān)系，所以算不用11個(gè)a相乘，而是??得到，，而?得到。
（2）那么問題來了，如何將11分解成 11 = 8 + 2 + 1這樣的倍乘關(guān)系呢？
答：
（3）這里因?yàn)槎M(jìn)制的11中第三位為0，所以沒有?，如果跳過4呢？1011中的0，就是需要跳過的 4。
（4）
推算乘積：從低位往高位處理1011（右移一次，就把剛處理的低位移走了）
- 1011，處理末尾的1：計(jì)算a。 ；
- 1011，處理第2個(gè)1：計(jì)算。?
?；
- 1011，處理0：跳過。
-
1011，處理1：計(jì)算。?
。
//第三種方法：
public double myPow(double x, int n) {
double base = x;
int tmp = n;
double res = 1;
if(n < 0) n = -n;
while(n != 0){
if((n & 1) != 0) //如果n的最后一位是1，表示這個(gè)地方需要乘
res*=base;
base*=base;//推算乘積，在解析有說明
n>>=1;//n右移一位，把剛處理過n的最后一位去掉
}
if(tmp < 0) res = 1.0 / res;
return res;
}
注：解法三的速度比解法一快了許多，但是相比于解法二還是慢了一些，導(dǎo)致超時(shí)錯(cuò)誤。
文章來源：http://www.zghlxwxcb.cn/news/detail-824749.html
?
到了這里，關(guān)于遞歸、搜索與回溯算法（專題一：遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
