Processing math: 100%

使用 Python 检查字符频率是否在雷卡曼数列中

假设我们有一个小写字符串 s。我们必须检查 s 中字母的出现次数，在以任何可能的方式重新排列后，是否生成雷卡曼数列（忽略第一项）。

雷卡曼数列如下所示：

an={0(如果n=0)\an−1−n(如果an−n>0∧不存在于数列中):an−1+n(否则)

雷卡曼数列的一些项为 [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24,...]（第一项被忽略，因为它是 0）

因此，如果输入类似于 s = "pppuvuuqquuu"，则输出将为 True，因为字符和频率为 (p, 3)、(u, 6)、(v, 1) 和 (q, 2)。因此，频率形成了雷卡曼数列的前几项 [1, 3, 6, 2]。

为了解决这个问题，我们将遵循以下步骤：

  • freq := 一个存储 s 中所有字符及其频率的映射
  • n := freq 的大小
  • array := 前 n 个雷卡曼数列项
  • f := 1
  • 对于 freq 中的每个字符，执行以下操作：
    • is_found := 0
    • 对于范围从 1 到 n 的 j，执行以下操作：
      • 如果 freq[keys] 与 array[j] 相同，则：
        • is_found := 1
        • 退出循环
    • 如果 is_found 为假，则：
      • f := 0
      • 退出循环
  • 如果 f 设置为 True，则返回 True，否则返回 False

示例

让我们查看以下实现以获得更好的理解：

 在线演示

from collections import defaultdict
def recaman(array, n) :
   array[0] = 0
   for i in range(1, n + 1):
      temp = array[i - 1] - i
      for j in range(i):
         if array[j] == temp or temp < 0:
            temp = array[i - 1] + i
            break
      array[i] = temp
def solve(s) :
   freq = defaultdict(int)
   for i in range(len(s)) :
      freq[s[i]] += 1
   n = len(freq)
   array = [0] * (n + 1)
   recaman(array, n)
   f = 1
   for keys in freq.keys() :
      is_found = 0
      for j in range(1, n + 1) :
         if freq[keys] == array[j]:
            is_found = 1
            break;
      if not is_found:
         f = 0
         break
   return True if f else False
s = "pppuvuuqquuu"
print(solve(s))

输入

"pppuvuuqquuu"

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

True

更新于: 2021年1月18日

76 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告