筆試算法模拟題精解之”斐波那契字元數”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“55.斐波那契字元數”的解法探究。先來看一下題目内容：

題目詳情：

等級：中等

知識點：遞歸、剪枝

檢視題目：斐波那契字元數

Tom發現了一種神奇的字元串-斐波那契字元串,定義f[1]=0,f[2]=1,對于所有的i>2都有f[i]=f[i-2]+f[i-1]，其中“+”代表拼接，比如01+10=0110，現在對于字元串f[n]，請判斷f[n]的第k項是0，還是1。

輸入兩個數字n和k(n<=300,k<=1000000000)。

輸出f[n]的第k位，如果k大于f[n]的位數，則輸出-1。

本題在答題過程中很多小夥伴反應會出現超記憶體的現象，導緻JVM崩潰。但其實這道題目是不可以暴力解題的，首先來看一下一般思路解法。

方法1：直接法（逾時并超出記憶體限制）

這是一道找規律的題目，最簡單的想法可以是自底向上地建構出從第一個字元串f[1]直到最後的f[n]，然後檢視f[n]的第k項是0還是1。

由于斐波那契數遞增速度非常快，當n較大時，這種暴力拼接法無法完成。

下面介紹一種優化的算法。

方法2：找規律（送出通過）

本題應充分利用斐波那契數列的性質，自頂向下對問題逐漸剪枝，定位需要判斷的數字位置。

比如，對輸入n=19, k=98：

1. 先算出n=19對應的字元串長度len，也就是斐波那契數列的第19項。考慮到k是int類型，故可以先算出n=1~47對應的斐波那契數組成的數組（n=47時，斐波那契數大于2^31-1，無需再提前計算更多的斐波那契數），然後直接在計算好的斐波那契數組中取出第19項。
2. 找到n-2=17，n-1=18對應的斐波那契字元串長度（也就是第17/18個斐波那契數）len1，len2。同樣也是在提前計算好的斐波那契數組中找到。
3. 對于k=98，如果k>len1，說明要找的數字在n=18對應的斐波那契字元串中，也就是n=19對應的斐波那契字元串的後半部分；如果k<=len1，說明要找的數字在n=17對應的斐波那契字元串中，也就是n=19對應的斐波那契字元串的前半部分。
4. 根據判斷結果，将n指派為n-2或n-1，同時将k指派為k或(k-len1)，完成剪枝。回到第1步，遞歸向下搜尋。直到n=1或者2，這時k也變為1，定位完成，結束遞歸，直接傳回結果。

進一步優化：

當輸入的n > 47時，斐波那契字元串的長度超出了int型變量k的表示範圍。需要提前進行推斷剪枝。你能根據k的int表示範圍（小于等于2^31-1）這一特性，對n較大的那些用例進行優化麼？

方法3：遞歸

這個問題可以使用遞歸的方法來求解。

題目中給出了字元串拼接的規律：f[i]=f[i-2]+f[i-1]。可以看出對于第i個字元串，它的前半部分屬于第i-2個字元串，後半部分屬于第i-1個字元串。

這樣，當給定具體的n和k時，我們可以首先判斷k位于第n個字元串的前半部分還是後半部分，然後遞歸的把k傳遞給第n-2或n-1個字元串。

計算過程：

1. 為了判斷屬于前半部分還是後半部分，需要計算每一個字元串的長度。

   一個len數組。每個位置為對應字元串的長度。

len[1] = len[2] = 1;

len[i] = len[i-2]+len[i-1];

1. 如果k > len[n]，則輸出-1。
2. 設定遞歸函數 int find(int i, int k);這個函數傳回第i個字元串中k個位置的字元

3. 判斷k在前半部分還是後半部分。

   a) K <= len[i-2] 前半部分，調用find(i-2, k)

b) K > len[i-2] 後半部分，調用find(i-1, k-len[i-2])

上面的計算在第一步時會遇到問題，當n大于幾十的時候，len就會超出int的範圍。

對這個問題的解決基于對遞歸過程的觀察，第4步a）中k始終是不變的，i的奇偶性也保持不變。是以在計算第1步len時可以提前停止，當發現len[i]>=k且i與n的奇偶性相同時。第4步中的遞歸起始也可以使用第i個字元串開始，而不是第n個。

時間複雜度O(2*n)

空間複雜度O(n)

是不是感覺有思路了，

立刻點選這裡開啟答題！

算法題目的解法并不唯一，這裡介紹部分解題思路給大家，希望可以給大家啟發~

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！

下一篇： 筆試算法模拟題精解之“壞掉的時鐘”