Python程式：查詢字典序第k小的n長度字串

假設我們有一個數字n和另一個值k。現在讓我們考慮一個僅包含“0”，“1”和“2”的字串，其中沒有字元連續重複。我們必須選擇長度為n的此類字串並找到字典序第k小的字串。如果沒有第k個字串，則返回空字串。

因此，如果輸入類似於n = 4 k = 2，則輸出將為“0120”。

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

  • 定義一個方法solve()，它將接收s、k和last
  • 如果s等於0，則
    • 返回空字串
  • 對於“012”中的每個字元c，執行以下操作
    • 如果c等於last，則
      • 進行下一次迭代
    • 如果k < 2^(s-1)，則
      • 返回c + solve(s - 1, k, c)
    • k := k - 2^(s-1)
  • 返回空字串
  • 從主方法呼叫solve(n, k, Null)

讓我們檢視以下實現以獲得更好的理解

示例程式碼

線上演示

class Solution:
   def solve(self, s, k, last=None):
      if s == 0:
         return ""
         for c in "012":
            if c == last:
               continue
            if k < 2 ** (s - 1):
               return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
         return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

輸入

4, 2

輸出

0120

更新於: 2020年11月25日

457 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告