遞歸題目技巧

1. 什么是遞歸
   函數(shù)自己調(diào)用自己的情況
2. 為什么會用到遞歸
   本質(zhì): 主問題, 可以拆分成相同的子問題
   子問題, 又可以拆分出相同的子問題
3. 如何理解遞歸?
   宏觀的看待遞歸的過程
   1)不要在意遞歸的細(xì)節(jié)展開圖
   2)把遞歸的函數(shù)當(dāng)成一個黑盒
   3)相信這個黑盒一定能夠完成這個任務(wù)
4. 如果寫好一個遞歸?
   1)先找到相同的子問題(變得值)-----函數(shù)頭的設(shè)計
   2)只關(guān)心某個子問題是如何解決的-----函數(shù)體的書寫
   3)注意一下函數(shù)遞歸的出口
5. 循環(huán)(迭代)和遞歸本質(zhì)是可以相互轉(zhuǎn)化的
   循環(huán), 適用于只有一層遞歸的情況, 例如鏈表
   遞歸, 適合多層, 例如二叉樹, 多叉樹…

一. 漢諾塔問題

漢諾塔問題

class Solution {public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {dfs(a, b, c, a.size());// 從a借助b移動到c, 移動n個盤子}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {if (n == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}
}

二. 合并兩個有序鏈表

合并兩個有序鏈表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {//合并兩個有序鏈表if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);//l1小, 合并l1.next 和 l2兩個有序鏈表return l1;}else{l2.next = mergeTwoLists(l1, l2.next);//l2小, 合并l2.next 和 l1兩個有序鏈表return l2;}}
}

三. 反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = reverseList(head.next);//將head結(jié)點后面的逆序, 返回逆序后的頭結(jié)點head.next.next = head;//將head結(jié)點插在逆序鏈表最后head.next = null;//將head.next置為空return newHead;}
}

四. 兩兩交換鏈表中的結(jié)點

兩兩交換鏈表中的結(jié)點

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = swapPairs(head.next.next);//將head.next.next 后面的鏈表兩兩交換, 返回頭結(jié)點ListNode ret = head.next;head.next.next = head;//將前兩個鏈表交換head.next = newHead;return ret;}
}

五. pow(x, n)

算法: 快速冪
實現(xiàn)快速冪: 1. 遞歸 2. 循環(huán)

class Solution {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;//結(jié)果乘在一起}
}