时间戳

首页 > 解决方案 > 优化 Haskell 中无限字符串的过滤

algorithm - 优化 Haskell 中无限字符串的过滤

问题描述

我正在解决 HackerRank 中的一个问题，其中我必须计算无限重复序列字符串的'a'第一个n元素中的字母数，例如"abc"对于"abcabcabcabc...".

我已经使用列表推导实现了以下功能：

repeatedString s n = length $ [x | x <- take (fromInteger n) (cycle s), x == 'a']

wheres是重复序列，n是从无限字符串中获取的元素数。

但是 HackerRank 抱怨说，某些测试没有在时限内执行。

问题是：

非常感谢您！

编辑：澄清功能参数。

标签： algorithmperformancehaskelloptimizationbig-o

解决方案

您不需要明确a计算s的数量。你可以做的是：

  1. 计算'a's 中的数量c；
  2. 检查你做了多少次完整的循环s（除以n的长度s）；
  3. 计算在最后一个（不完整的）循环中发出了多少个字符s；
  4. 计算该部分中的'a's 数量。
  5. 'a'将完整循环的s个数和不完整循环的s个数相加'a'。

因此，该程序如下所示：

repeatedString :: String -> Int -> Int
repeatedString s n = (length (filter ('a' ==) s) * div n (length s)) + …

…您仍然需要填写处理最后一个（不完整）周期的部分。

即使n很大，算法仍然会在O(|s|)中运行。

推荐阅读