合輯 | 七道典型筆試算法模拟題精解

阿裡雲開發者社群線上程式設計，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。

題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，技術人刷題進階必備工具！

點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家集合了其中的七道典型筆試算法模拟題精解，進階就在此刻！

1.斐波那契字元數

題目概述：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？

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

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

下面介紹一種優化的算法：本題應充分利用斐波那契數列的性質，自頂向下對問題逐漸剪枝，定位需要判斷的數字位置...點選連結檢視詳細解法：

筆試算法模拟題精解之”斐波那契字元數” 2.完美排列

題目概述：完美排列的定義為一個長度為n的數組，n個元素各不相同且每個元素均在[1,n]的範圍内。

現在給你長度為n的數組，你每次可以進行如下操作：任選數組中的一個元素，将其加一或者減一，問最少需要多少次操作才能夠使得該數組為一個完美排列？

題解簡述：本題是一道典型的貪心算法題，問題可以通過每步的最優政策分治解決。如果将 n 個大小未知的正整數，通過題目中的規則“填充”到槽 1~n 中，我們不妨從最小的數字槽 1 開始做起。

顯然，這 n 個正整數中最小的數字 a（無論這個最小的數字是 1 或是 100），是填充槽 1 的最佳選擇。其它(n-1)個數字和 1 的“距離”，都必定大于等于 a，距離槽 1 的距離都不如 a 更優，是以可以将 a 填充進槽 1，并在後續選擇中排除掉它。

當填充槽 2 時，依舊用上面的思路就可以了。用剩下的(n-1)個數字中最小的數字去通過加減 1 進入槽 2，必定是填充槽 2 所有方式中的最佳政策。

将上面的思路重複應用，就得到了結果。複雜度上需要掃描 n 次數組。

但是上面的反複掃描非常浪費時間，文章還為大家提供了一種更加優化的思考方法，快來一探究竟吧！

筆試算法模拟題精解之“完美排列” 3.壞掉的時鐘

題目概述：B同學有一個時鐘，能夠顯示1-d，初始值為1。這個時鐘每天顯示的數字加一，特殊的，當某天顯示的值為d時，第二天就會顯示1。

但是每個月的時間并不總是d天，是以B同學就要通過手動調整使得顯示的時間正确，每次手調都可以使顯示數字加一。

現在給你n個月每月的天數，請你計算一下若是讓時鐘每天顯示的數字都是正确的，他這n個月一共需要調多少次時鐘？

題解簡述：本題關鍵在于了解題意：題幹的含義是，在除去最後一個月後，其餘每個月的最後一天的24點時，時鐘上的邏輯時間會超過那個月的最大天數，同時實際時間變為下一個月的第1天。此時邏輯時間和實際時間有差别，需要調整時鐘，讓邏輯時間重新回到1，使其符合實際時間。

那麼具體是怎麼解題的呢，點進連結檢視詳情：

筆試算法模拟題精解之“壞掉的時鐘” 4.Bob的花束

題目概述：Bob和Alice是青梅竹馬。今天，Bob終于要鼓起勇氣向Alice表白了！說到表白，自然是少不了買花了。Bob來到了花店，花店一共提供了9種花，每一種花都有對應的價錢。但是Bob的零花錢有限，不能把所有的花都買下來送給Alice。

為了友善挑選，Bob給這9種花分别标号1-9，Bob希望買到的花按照編号可以排出盡可能大數字，請問Bob能夠排出的最大的數字是多少？

題解簡述：本本題充分了解題意後，直接模拟這個“選取最大值”的過程就可以得到結果了。

首先，選取最大值，意味着首先這個結果的“位數”要足夠多，比如假設所有的花價格都是1元錢，則11111111是花9塊錢能買到的最大值，而不是333或者9這樣的方案。這樣相當于根據輸入，輸出的位數可以用很小的時間代價來确定：“用可用錢數，除以最便宜的花的價格，并向下取整”。假設這裡的位數為m。

其次，在位數确定的情況下，高位數字越大，結果也就越大，比如同樣是8元錢，隻能購買價格為5的5号花，和價格為3的3号花時，購買35就是最差的方案，而53才是正确答案。而且因為每個花的數量是無限的，是以可以模拟這個 “從高位開始，逐個選取能買得起的最大的數字；同時每選完一位後，要確定剩下的錢，依舊可以買到m位數字的組合方案。”根據上面邏輯再進行優化就可以寫出答案啦，快來一探究竟吧：

筆試算法模拟題精解之“Bob的花束” 5.最優分組

題目概述：給出一個長度為 n 的數組和一個數字 k ，你需要在數組中選出一些數字，這些數字兩兩之間的內插補點不能超過k。你需要判斷最多能夠挑出的數字個數。（n在[1, 100000]之間，k和數組中的數字在[1，1000000000]之間）？

題解簡述：一組數字，在不改變順序的情況下，每相鄰兩個數字之間的內插補點是确定的。在這個思路的引導下，先對數字進行排序，對排序後的新序列進行周遊即可解答出本題目啦，戳連結檢視思路詳情吧：

筆試算法模拟題精解之“ 最優分組” 6.超車

題目概述：一天某地在舉行公路自行車比賽，一共有n名選手參加(2<=n<=100000)，在比賽的過程中，有一段路程觀衆是看不見的，現在給你了選手進入這段路程的順序編号，又給了選手出這段路程的順序編号（順序按照先進先出的原則，編号為1-n），請你計算一下，有多少名選手在這段公路上完成了超車（出路段後超過了進路段前在自己前面的選手）？

題解簡述：根據題意，超車意味着對于入洞前序列中的每輛車x及x前面的車集合{a,b,c,d...}，如果在出洞序列中，發現x前面的某車，出洞時不在{a,b,c,d...}集合中，就說明x超過了這輛不在{a,b,c,d...}集合中的車。而且這個超車行為與其他車無關，也就是說，即使上面個的清空中x的排名後撤了，被其它車超過了，它也依然被視為發生了超車。“隻要超過了一輛車，就算發生了超車”。

根據上面思路，首先需要周遊入洞序列，對每輛車x周遊，同時用一個清單記錄下入洞序列中x前面的車。對這樣的x和清單，再去出洞序列中從尾部開始周遊，直到發現x停止。如果周遊出洞序列的過程中，發現某車存在于清單中，說明這輛車入洞前在x的前面且出洞後在x的後面，發生了超車，此時令結果加1。

如果簡單應用這種代碼，不加優化，會有嵌套循環，時間複雜度很高，不能通過。

上面的思路中，耗時最多的部分，就是内循環的判斷，按照此思路批量判斷超車，就将大大地提高内循環的效率...點選檢視優化算法：

筆試算法模拟題精解之“超車”的兩種解法 7.Alice的01串

題目概述：Alice給了Bob一個字元串s，Alice想讓Bob找出這個字元串中有多少個恰好包含了k個1的子串。請你幫助Bob計算出這些子串的個數是多少？

題解簡述：根據題意，本題可以直接用雙層循環掃描數組，找到所有的連續子串，檢視每個組合是否擁有指定數量的1。點選連結檢視詳細題解：

筆試算法模拟題精解之“Alice的01串”

持續更新中。。。更多内容請關注

算法程式設計技術圈

！

另有線上程式設計周賽、月賽火熱進行中！社群定制衛衣、雙肩背包等你來拿~點選了解周賽詳情：

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

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

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

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

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

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

點選檢視：合輯 | 筆試算法模拟題精解系列（二）