← 返回目录

算法笔试模拟题精解之“2n 合体”

第 64 / 74 卷日期：

算法笔试模拟题精解之“2n 合体”

贡献者 | 黄信旭

简介：关键在于理解题意，题中的含义是这样的，每次挑两对 2n 合并成 m，然

后判断有多少个子序列，之后再挑选不同的 2n。所以示例中的答案是 4 种，而不是

1 种。

题目描述

等级：容易

知识点：数学

查看题目：2n 合体

有一个只包含小写字母 n 和 t 的字符串 s(1<=|s|<=1000000)，其中如果有两

个 n 相邻，那么它们可以合并成一个 m，现在需要你去求这个字符串中，含有多少

个 'mtm' 这样的子序列。

输入一行字符串 s；

输出这个字符串中所包含的 mtm 子序列的个数。

示例 1

输入：

"nnntnnn"

输出：

解题思路

两个位置容易出现理解问题。

  1. 子序列。子序列不要求一定是连续的。例如 abcdef 的子序列可以是 abc，

也可以是 ace。

  1. 含有多少个’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 个数

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：2n 合体

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”