算法筆試模拟題精解之“2n合體”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的第48題：2n合體，具體如下：

題目描述

等級：容易

知識點：數學

檢視題目：2n合體

有一個隻包含小寫字母n和t的字元串s(1<=|s|<=1000000)，其中如果有兩個n相鄰，那麼它們可以合并成一個m，現在需要你去求這個字元串中，含有多少個'mtm'這樣的子序列。

輸入一行字元串s；

輸出這個字元串中所包含的mtm子序列的個數。

示例1

輸入：

"nnntnnn"

輸出：

4

解題思路

兩個位置容易出現了解問題。

1、子序列。子序列不要求一定是連續的。例如 abcdef的子序列可以是abc，也可以是ace。

2、含有多少個’mtm’這樣的子序列。這裡不是說先判斷如何合并，然後在合并後的字元串上判斷mtm子序列有多少個。

題中的含義是這樣的（感覺題幹确實沒說清楚），每次挑兩對2n合并成m，然後判斷有多少個子序列，之後再挑選不同的2n。是以示例中的答案是4種，而不是1種。

有了上面的解釋，了解題幹就沒有問題了。

求解思路：對于每一個t進行單獨考慮，計算這個t的左側和右側分别可以合成出多少種不同的m，這兩個數的乘積就是對于這個t來說的mtm子序列的個數。

因為隻有相鄰的n才可以合成m，是以t将原來的字元串分成了一系列n的串。

例如：nnntnnnntnntnnn

被分成了nnn nnnn nn nnn

沒有段包含的m個數分别為2 3 1 2

對于每個t來說的mtm子序列就分别是2

*

（3+1+2） 、（2+3）

*

（1+2）、 （2+3+1）*2；是以結果為12+15+12 = 39

時間複雜度為O(2*n) 第一次周遊算出每一段m個數，第二次周遊求和；

空間複雜度O(n) 儲存每一段m個數

看完之後是不是有了想法了呢，快來練練手吧>>