不會(huì)寫代碼怎樣做網(wǎng)站開發(fā)一個(gè)平臺(tái)需要多少錢
遞歸題目技巧
- 什么是遞歸
函數(shù)自己調(diào)用自己的情況 - 為什么會(huì)用到遞歸
本質(zhì): 主問題, 可以拆分成相同的子問題
子問題, 又可以拆分出相同的子問題 - 如何理解遞歸?
宏觀的看待遞歸的過程
1)不要在意遞歸的細(xì)節(jié)展開圖
2)把遞歸的函數(shù)當(dāng)成一個(gè)黑盒
3)相信這個(gè)黑盒一定能夠完成這個(gè)任務(wù) - 如果寫好一個(gè)遞歸?
1)先找到相同的子問題(變得值)-----函數(shù)頭的設(shè)計(jì)
2)只關(guān)心某個(gè)子問題是如何解決的-----函數(shù)體的書寫
3)注意一下函數(shù)遞歸的出口 - 循環(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移動(dòng)到c, 移動(dòng)n個(gè)盤子}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);}
}
二. 合并兩個(gè)有序鏈表
合并兩個(gè)有序鏈表
/*** 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) {//合并兩個(gè)有序鏈表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兩個(gè)有序鏈表return l1;}else{l2.next = mergeTwoLists(l1, l2.next);//l2小, 合并l2.next 和 l1兩個(gè)有序鏈表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é)點(diǎn)后面的逆序, 返回逆序后的頭結(jié)點(diǎn)head.next.next = head;//將head結(jié)點(diǎn)插在逆序鏈表最后head.next = null;//將head.next置為空return newHead;}
}
四. 兩兩交換鏈表中的結(jié)點(diǎn)
兩兩交換鏈表中的結(jié)點(diǎn)
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é)點(diǎn)ListNode ret = head.next;head.next.next = head;//將前兩個(gè)鏈表交換head.next = newHead;return ret;}
}
五. pow(x, n)
算法: 快速冪
實(shí)現(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é)果乘在一起}
}