使用 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
        • 退出迴圈
    • 如果 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 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告