資訊專欄INFORMATION COLUMN
摘要：題目題目描述大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)，請(qǐng)你輸出斐波那契數(shù)列的第項(xiàng)從開始，第項(xiàng)為。基本思路這道題在劍指中實(shí)際是當(dāng)作遞歸的反例來說的。明顯也符合斐波那契數(shù)列的規(guī)律矩形覆蓋我們可以用的小矩形橫著或者豎著去覆蓋更大的矩形。
題目
題目描述
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）。
這道題在劍指offer中實(shí)際是當(dāng)作遞歸的反例來說的。
遞歸的本質(zhì)是吧一個(gè)問題分解成兩個(gè)或者多個(gè)小問題，如果多個(gè)小問題存在互相重疊的情況，那么就存在重復(fù)計(jì)算。
f(n) = f(n-1) + f(n-2) 這種拆分使用遞歸是典型的存在重疊的情況，所以會(huì)造成非常多的重復(fù)計(jì)算。
另外，每一次函數(shù)調(diào)用愛內(nèi)存中都需要分配空間，每個(gè)進(jìn)程的棧的容量是有限的，遞歸層次過多，就會(huì)造成棧溢出。
遞歸是從最大數(shù)開始，不斷拆解成小的數(shù)計(jì)算，如果不去考慮遞歸，我們只需要從小數(shù)開始算起，從底層不斷往上累加就可以了，其實(shí)思路也很簡單。
代碼function Fibonacci(n)
{
if(n<=1){
return n;
}
let i = 1;
let pre = 0;
let current = 1;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
擴(kuò)展
1.跳臺(tái)階：
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
找規(guī)律：
跳三級(jí)臺(tái)階等于跳兩級(jí)臺(tái)階的跳法+跳一級(jí)臺(tái)階的跳法。
跳四級(jí)臺(tái)階等于跳三級(jí)臺(tái)階的跳法+跳二級(jí)臺(tái)階的跳法。
明顯也符合斐波那契數(shù)列的規(guī)律
function jumpFloor(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3.矩形覆蓋
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
跟上面跳臺(tái)階那個(gè)題很像。
假設(shè)有8個(gè)塊
第1塊豎著放，后面還剩7塊，共f(7)種方法。
第1塊橫著放，后面還剩6塊，共f(6)種方法。
即f(8)=f(6)+f(7)
f(n)=f(n-1)+f(n-2)
function rectCover(n)
{
if(n<=2){
return n;
}
let i = 2;
let pre = 1;
let current = 2;
let result = 0;
while(i++ < n){
result = pre + current;
pre = current;
current = result;
}
return result;
}
3.{{BANNED}}跳臺(tái)階
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
每個(gè)臺(tái)階都可以選擇跳或者不跳，最后一個(gè)臺(tái)階必跳。
每個(gè)臺(tái)階有兩種選擇，n個(gè)臺(tái)階有2的n次方種選擇。
所以一共有2的n-1次跳法。
使用位運(yùn)算
function jumpFloorII(number)
{
return 1<<(--number);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/101222.html
摘要：二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。 1.二維數(shù)組中的查找 在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)...
摘要：二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計(jì)算的時(shí)間復(fù)雜度是以的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。 二維數(shù)組中的查找 在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和...
摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時(shí)間刪除鏈表結(jié)點(diǎn)。 寫在前面 本文的題目均來自于劍指offer中的題目，題目序號(hào)保持了書中的題目序號(hào)，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會(huì)出現(xiàn)題目序號(hào)的中斷。 正文 面試題6：...
摘要：今天去面試筆試題斐波那契數(shù)列實(shí)現(xiàn)，雖然很簡單?；貋硐胂爰热凰惴ㄟ@么重要那就從這個(gè)開始來記錄自己的算法庫吧。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡單，，觀察下數(shù)列值就很容易總結(jié)出來了。 一、寫在前面 算法這塊對(duì)于大多數(shù)程序員（包括我）來說可能都是一個(gè)薄弱的地方，如何彌補(bǔ)尼？ 每個(gè)人都知道那就是學(xué)習(xí)、特別是算法沒有任何捷徑可走。 在這記錄平時(shí)自己工作和生...
閱讀 2848·2021-11-04 16:15
閱讀 3570·2021-09-29 09:35
閱讀 4175·2021-09-22 15:45
閱讀 1475·2019-08-30 15:55
閱讀 1761·2019-08-30 15:44
閱讀 2819·2019-08-29 12:56
閱讀 2785·2019-08-26 13:30
閱讀 2235·2019-08-23 17:00
