合輯 | 10+筆試算法模拟題精解，帶你玩轉算法！

上一篇：合輯 | 七道典型筆試算法模拟題精解系列（一）

阿裡雲開發者社群

線上程式設計

産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。技術人進階學習必備工具！點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家集合了其中部分題目的解析，助你沖榜！！

1、

2的幂次方數

題目概述：Tom是一個十分喜歡數學的人，尤其喜歡2的幂次方的數字。現有n（1<=n<=150000）個數字，對于其中的每一個數字ai(1<=i輸入數字個數n和n個數字；

輸出一個數字，表示最終需要删除的數字的個數。

題解簡述：對于本題，因為要從數組中删除數字。删除分為兩步，一是定位（查找），二是删除（将出現次數減1）。是以首先需要考慮的難題是，如何快速定位要查找的數字，并記錄下數字出現的次數？for循環的線性查找，遞歸的二分查找（對有序數組），建立哈希表，都是可選的方式。既然追求最佳解法，你不妨先試試将題目提供的資料結構轉為哈希表？

之後的第二個難點，就是如何得出“與某個數相加為2的幂次方數”的數字了。我們知道，用二進制表示時，一個2的幂次方的正整數，譬如2，4，8，16...，隻有最高位為1，其餘位都是0，譬如b1，b10，b100，b1000...是以，對每個數字，隻要用位元算找到它的最高位1的位置，就可以确定比它大的2的幂次方數中最小的數字了...本題還有一個陷阱，點選連結檢視詳情：

筆試算法模拟題精解之“2的幂次方數”

2、

神奇數字在哪裡

題目概述：

請計算出1-n(1<=n<=1000000000)中有多少個數字中，隻存在'1','2','3'這三個數字，且這三個數字至少都要出現1次。

輸入一個數n。

輸出1-n中符合要求的數字的個數。

題解簡述：

注意讀題，本題要求的數字中“隻”含有1，2，3三個數字。

方法 1：暴力搜尋

對本題，最簡單的想法是針對每個數字，轉為字元串，然後判斷數字中是否隻同時包含1，2，3三個字元。

鑒于本題輸入是int，n最大可以達到2^31-1≈2*10^9，一個這麼長的for循環，時間複雜度還是比較高的，為O(n)，當然這并不是最優解法。

可以使用深度優先搜尋的思維去想，極大的降低時間複雜度，點選連結了解詳情...

筆試算法模拟題精解之“神奇數字在哪裡”

3、

神奇的棋子

Tom有一天在玩棋子，這些棋子都不是普通的棋子。現在有n個棋子排成一排(2<=n<=18)，每個棋子都有它們自己的權值ai(0<=ai<=1e9)，現在Tom每次選擇連續的三枚棋子，然後中間的那枚棋子會消失，而它左右兩邊的棋子會分别加上它的權值，問最後隻剩下兩枚棋子的時候，這兩枚棋子的權值的最小的和為多少？

輸入棋子個數n和一個數組a，a[i]表示每個棋子的權值。

輸出一個數，表示最終剩下的兩枚棋子的權值的最小的和。

因為我們每選擇一次，消失的數對左右都有影響，而且也會被挑選的順序影響，是以需要去考慮每個棋子的貢獻。

枚舉一段區間最後選的棋子，然後将其分為兩段區間，設該段區間的左端點最終的貢獻為x，右端點最終的貢獻為y，那麼在隻剩最後選的數，左端點，右端點三個點時，我們選擇最後的那個點，那麼最後那個數最終的貢獻就是x+y次了，然後根據這個思路已知分治下取就好了...

筆試算法模拟題精解之“神奇的棋子”

4、

Jerry的考驗

有一天Jerry給Tom出了一道題來考驗他。Jerry給了Tom一個長度為2

*

n的隻包含小寫字母的字元串，讓Tom将這個字元串任意挑選字元，将其分成兩個等長的字元串a和b(對于一個si不能同時被選到a和b中)，然後a要和reverse(b)相同(a和反轉後的b相同)，問這樣的方案數有多少？Tom有些為難，是以請你來幫幫他吧。

輸入一個正整數n，和一個長度為2*n的字元串

輸出方案數。

首先我們來看樣例abba，如果我們選擇ab，剩下ba，如果我們選擇ba，剩下ab，這兩種情況都是符合題意的，而且這兩種情況都各有兩種選取方式，是以一共有4種。

對于這種選和不選的情況，很容易可以想到二進制枚舉的方法。但是如果直接用二進制枚舉的話時間複雜度是2^36的，肯定要逾時，是以我們需要對其進行優化...

筆試算法模拟題精解之“Jerry的考驗”

5、

采摘聖誕果

聖誕節馬上就要來了，果園裡的 n 棵聖誕樹馬上就要結果子了，每棵聖誕樹會在第a[i]天結出b[i]個果實。果園裡有許多聖誕小精靈，它們非常喜歡吃聖誕果，如果在結果後兩天内也就是第a[i]天和第a[i]+1天，沒有将果實采摘下來，那麼将會被小精靈們偷吃掉。

你，作為聖誕樹的看守者，必須采摘盡可能多的聖誕果，但是你每天最多隻能采摘v個聖誕果，當然，可以是不同的果樹上的。現在你需要判斷自己最多可以收獲多少聖誕果？

我們定義數組a[i]表示第i天可以采摘的剛剛結出來的果子，數組b[i]表示第i天可以采摘的已經過了一天的果子。根據輸入先初始化a[]...

筆試算法模拟題精解之“采摘聖誕果”

6、

數組變換

給出一個長度為 n 的數組，和一個正整數 d。

你每次可以選擇其中任意一個元素 a[i] 将其變為 a[i] + d 或 a[i] - d，這算作一次操作。你需要将所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出-1。

輸入數字n、數字d，和一個長度為n的數組a。1 <= n <= 100000，1 <= d <= 100, 1 <= a[i] <= 100000。

輸出一個數字，表示最小的操作次數，如果無解輸出-1。

首先判斷無解的情況，可以發現 a[i]，a[i]+d, a[i]-d 在 模d情況下的餘數不會發生改變，是以如果原數組中的存在任意兩個數字它們對d取餘結果不同，那麼此時無解。

設餘數為r。判斷完無解之後，需要求出最小值。

先将數組a[i]排序，然後除以d，得到從r變成a[i]需要的步數。

枚舉元素a[i]，将所有元素全部變成a[i]需要考慮兩部分，i之前和i之後:對于i之前的元素，假設都是r，那麼需要 (i-1)*a[i]，但是因為并不都是0，所有我們可以用一個變量val存放前i-1項的和，然後我們在減去val就是前i-1個元素真正需要操作的步數...

筆試算法模拟題精解之“數組變換”

7、

恢複字元串

給出兩個僅包含“+”、“-”兩種字元且長度相同字元串s1、 s2，你需要通過填充數字将這兩個字元串恢複成一個合法的表達式。并且隻能填入正整數，恢複後的表達式的值必須非負。

例如對于字元串“+-”，你可以将其變成“1+1-2”，但是不可以變成“1+1-3”，也不可以變成“1+0-1”。定義你的消耗為你填充的所有正整數的和。比如“1+1-2”的消耗為 1 + 1 + 2 = 4。你需要将這兩個字元串都恢複成合法表達式，并且盡量的使它們的內插補點最小，于此同時你還需要使你的消耗最小。

相信你通過思考已經發現最小內插補點總是0，是以你隻需要求出內插補點為0時的最小消耗即可。字元串長度都小于100000。

輸入兩個字元串s1和s2。

輸出一個數字，表示最小消耗。

首先可以确定最小值一定為0。分兩種情況讨論。

兩個字元串都沒有負号的時候，最優解的所有位置都填1。最小消耗為 2*（n+1）。

表達式中僅需要有一個負号，表達式的值就可以為任何值。此時兩個表達式可以互相調整，是以最小差也是0。

表達式中除了第一位以外每位數字填1可以得到最小消耗，因為值加在哪一位都是等效的...

筆試算法模拟題精解之“恢複字元串”

8、

填數問題

有m個格子，編号為1,2…m，每個格子可以填1,2...n中的任意一個數。定義這m個格子上的數都是“好的”，僅當對于任意一個編号為i的格子，編号大于i的格子上的數都大于等于i号格子上的數。求有多少個填數方案，滿足這m個格子中填的數是“好的”，答案對P取模。

三行分别輸入三個整數，m、n、P，分别表示有m個格子、填入的最大數字n和模P。（保證1<=n,m<=1e18,2<=P<=1e5且P是質數）

輸出一個整數表示答案對P取模的結果。

“對于任意一個編号為i的格子，編号大于i的格子上的數都大于等于i号格子上的數”可以轉化為m個格子上的數是單調不減的。令cnt_i表示i這個數在m個格子中的出現次數，可以發現一組∑cnti = m(i∈[1,n])唯一對應着一個單調不減的填數方案。

由插闆法可知...

筆試算法模拟題精解之“填數問題”

9、

學習小組

在一個課堂上，有n個學生(1<=n<=3e5)，每個學生都有他們自己的學分ai(1<=ai<=1e9,ai<=ai-1)，現在老師想将他們分為m個小組(1<=m<=n)，為了友善交流，所有的小組都是由相鄰的學生組成(abc相鄰,不存在ac一個小組b在另一個小組的情況)，現在老師想讓每個小組的學分內插補點盡量小(最大值減去最小值)，請你幫助老師來分一下組，輸出最後的每個小組的最小的內插補點的總和。

第一行和第二行輸入兩個數n、m表示有n個學生要分成m個小組，再輸入n個數，表示每個學生的學分。

輸出一個數字，表示最後分出的m個小組的最小的內插補點的總和。

因為題目中說了ai是一個非遞減的數列，是以我們可以推導出一個式子。

比如我們要将一個數組分成3組，那麼可以假設為，[a1,ai],[ai+1,aj],[aj+1,an]這三組，然後我們所要求的值就是(ai - a1) + (aj - ai+1) + (an - aj+1) .

那麼就可以推導出an - a1 + aj - aj+1 - ai - ai+1，是以就是an - a1減去最大的m-1個相鄰的內插補點，那麼ai-ai+1這個顯然是差分的性質，是以我們對于原數列求一個差分數組出來，然後對差分數組進行排序，貪心的去減去前m-1個最大的就好了...

筆試算法模拟題精解之“學習小組”

10、

Tom的手工課

一天Tom在上手工課，老師給他們每個人發了一個白色的紙條，上面有n個方格(2<=n<=1e6)。

然後又給他們每個人發了n-1個彩帶，一個彩帶可以粘到兩個相鄰的方格上。現在老師讓他們把n個方格都粘上彩帶(可以不用完n-1個彩帶，一個方格上可以重複粘彩帶)。

Tom是一個熱愛數學的人，他想知道所有的方案中，一共用了多少次彩帶(所有的方案所用的彩帶的總和)。（答案對1e9+7取模）

輸入一個數n表示方格的個數。

輸出一個數表示最終方案數，答案對1e9+7取模。

對于每個方案來說，最少需要n/2個彩帶，最多要n-1個彩帶，然後我們分别對其進行計算貢獻。

操作最多 i 次的方案數是 f[i]，恰好 i 次的方案就是 f[i]−f[i−1]，而 f[i]=C(n-1-I, i-1)。

具體含義:可以看作是每次可以選擇 +1,+2 ,求構成 n−2 的方案數,我們先預設都 +1,剩下就是選擇 +0,+1 了,隻要總共的 i−1 次操作中有 n−1−i 個選擇了 +1,就一定可以達到目标了...

筆試算法模拟題精解之“Tom的手工課”

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

算法程式設計技術圈

！

另有線上程式設計周賽、月賽火熱進行中！點選連結了解詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！