数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 Python 检查字符频率是否在雷卡曼数列中
假设我们有一个小写字符串 s。我们必须检查 s 中字母的出现次数，在以任何可能的方式重新排列后，是否生成雷卡曼数列（忽略第一项）。
雷卡曼数列如下所示：
$$a_{n}=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(如果\:n=0) & \a_{n-1}-n(如果\:a_{n}-n>0\wedge 不存在于数列中) & \\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(否则)\end{cases}$$
雷卡曼数列的一些项为 [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
- 退出循环
- 如果 freq[keys] 与 array[j] 相同，则：
- 如果 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"
输出
True
更新于: 2021年1月18日
76 次浏览
广告