網(wǎng)頁(yè)設(shè)計(jì)素材 旅游seo服務(wù)商
目錄
70:爬樓梯
題目要求:
解題思路:(類似斐波那契數(shù))
遞歸解法:
非遞歸解法:
126:斐波那契數(shù)
題目要求:
解題思路:
遞歸解法:
非遞歸解法:
都看到這了,點(diǎn)個(gè)贊再走唄,謝謝謝謝謝!!!
70:爬樓梯
題目要求:
解題思路:(類似斐波那契數(shù))
遞歸解法:
由題可知,每次可以爬1個(gè)或者2個(gè)臺(tái)階,假如有n個(gè)臺(tái)階,會(huì)有多少種走法?那么我們就想,第一次爬一個(gè)臺(tái)階,那方法數(shù)就是爬這一次臺(tái)階加上剩下n-1個(gè)臺(tái)階的走法,爬兩個(gè)臺(tái)階,那方法數(shù)就是爬完這兩個(gè)臺(tái)階再加上剩下n-2個(gè)臺(tái)階的走法,很容易就想到遞歸的解法了,而使用遞歸我們要找到終止條件,也要寫出遞歸公式
但是這么遞歸的時(shí)間復(fù)雜度很高,LeetCode上通過(guò)不了,會(huì)有很多重復(fù)計(jì)算的斐波那契數(shù),我們可以用HashMap來(lái)解題,每次往下找之前都記錄一下map里面有沒(méi)有n這個(gè)斐波那契數(shù),有就不用繼續(xù)往下找了,直接返回這個(gè)斐波那契數(shù),沒(méi)有就繼續(xù)往下找,有了HashMap的引用,我們時(shí)間復(fù)雜度就變成了O(N),在LeetCode上也就能通過(guò)了。
遞歸公式如下:
代碼如下:
class Solution {HashMap<Integer, Integer> hashmap = new HashMap<>();public int climbStairs(int n) {if(n == 1) {return 1;}if(n == 2) {return 2;}//每次遞歸都判斷map有沒(méi)有n個(gè)臺(tái)階爬樓梯方法數(shù),沒(méi)有算出當(dāng)前n階臺(tái)階的方法數(shù),放進(jìn)map里,放進(jìn)map里后就不用繼續(xù)往下遞歸了,直接返回這個(gè)方法數(shù),因?yàn)閔ashmap已經(jīng)存了n階臺(tái)階的方法數(shù)了;有就不用繼續(xù)遞歸了,直接返回n臺(tái)階的方法數(shù)if(hashmap.get(n) != null) {return hashmap.get(n);} else {int result = climbStairs(n - 1) + climbStairs(n - 2);hashmap.put(n, result);return result;}} }
非遞歸解法:
從此圖我們可以看出,要求n的斐波那契數(shù),必須求前一個(gè)和前兩個(gè)的斐波那契數(shù),也就是上圖的公式,非遞歸的解法,我們就用循環(huán)來(lái)解決,從下至上來(lái)求n的斐波那契數(shù),我們定義一個(gè)pre和prePre變量來(lái)記錄前一個(gè)和前兩個(gè)的斐波那契數(shù),result來(lái)記錄n的斐波那契數(shù),每循環(huán)一次都要更改pre和prePre的下標(biāo),時(shí)間復(fù)雜度為O(N).
代碼如下:
public int climbStairs(int n) {//非遞歸思想if(n == 1) {return 1;}if(n == 2) {return 2;}int result = 0;int pre = 2;int prePre = 1;for(int flg = 3; flg <= n; flg++) {result = pre + prePre;//pre和prePre都要往前推prePre = pre;pre = result;}return result;}
126:斐波那契數(shù)
題目要求:
解題思路:
? ? ? ? 這題和爬樓梯思路一樣,解法也一樣,遞歸和非遞歸也一樣,不過(guò)他的遞歸公式和結(jié)束條件和爬樓梯不一樣,公式如下圖:
遞歸思路:因?yàn)檫f歸會(huì)重復(fù)計(jì)算很多次,所以我們可以用一個(gè)HashMap來(lái)記錄n的斐波那契數(shù),每遞歸一次都判斷map里面有沒(méi)有n的斐波那契數(shù),有就不用繼續(xù)往下遞歸了,直接返回這個(gè)斐波那契數(shù),沒(méi)有就往下遞歸,把1后面的斐波那契數(shù)列都記錄在map中,這樣時(shí)間復(fù)雜度就是O(N)了,LeetCode也能通過(guò)。
非遞歸思路:用循環(huán),從下至上,求得每個(gè)斐波那契數(shù),我們定義result放n的斐波那契數(shù),pre放n的前一個(gè)斐波那契數(shù),prePre放n的前兩個(gè)斐波那契數(shù),每循環(huán)一次都要更新一次pre和prePre的下標(biāo),往上走。
遞歸解法:
代碼如下:
Map<Integer, Integer> map = new HashMap<>();public int fib(int n) {if(n == 0 || n == 1) {return n;}if(map.containsKey(n)) {return map.get(n);}//n的斐波那契數(shù)不在map里int result = (fib(n - 1) + fib(n - 2)) % 1000000007;//int result = (fib(n - 1) + fib(n - 2));map.put(n, result);return result;}
非遞歸解法:
public int fib(int n) {//非遞歸if(n == 0 || n == 1) {return n;}int result = 0;int pre = 1;int prePre = 0;for(int i = 2; i <= n; i++) {result = (pre + prePre) % 1000000007;prePre = pre;pre = result;}return result;}