Python程式：查詢長度為k且距離為n的字典序最小的字串

假設我們有兩個數字 n 和 k。我們需要找到大小為 k 且距離為 n 的字典序最小的字串。距離是指字母在字母表中的序號之和。例如，'a' 的字母序號為 1，'b' 的字母序號為 2，'y' 的字母序號為 25，'z' 的字母序號為 26，以此類推。

因此，如果輸入為 n = 15 k = 3，則輸出為 "aam"，因為 "aam" 是長度為 3 且距離為 1 + 1 + 13 = 15 的字典序最小的字串。

為了解決這個問題，我們將遵循以下步驟：

• dist := 一個大小為 k 的陣列，並用 1 填充
• credit := n - k
• i := k - 1
• 當 credit > 0 時，執行以下操作：
  • val := credit 和 25 的最小值
  • dist[i] := dist[i] + val
  • credit := credit - val
  • i := i - 1
• 連線 (每個 d 在 dist 中的 (d - 1 + "a" 的 ASCII 碼) 的字元) 並返回

示例

讓我們看下面的實現來更好地理解：

def solve(n, k):
   dist = [1] * k

   credit = n - k

   i = k - 1
   while credit > 0:
      val = min(credit, 25)
      dist[i] += val
      credit -= val
      i -= 1

   return "".join(chr(d - 1 + ord("a")) for d in dist)

n = 15
k = 3
print(solve(n, k))

輸入

15, 3

輸出

aam

Arnab Chakraborty

更新於: 2021年10月19日

294 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習