算法笔试模拟题精解之“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个数

看完之后是不是有了想法了呢，快来练练手吧>>