Python程式：查詢從起點到終點移動的字典序最小的字串

假設我們在笛卡爾平面上的 (0, 0) 位置。我們想只使用單個單位的水平 (H) 和垂直 (V) 移動到達點 (x, y)。有多種可能的方式到達目的地。每種方式都包含一些 H 移動和一些 V 移動。（例如，如果我們想從點 (0,0) 到達點 (2,2)，則 HVVH 就是一種可能的方式。）如果我們還有另一個值 k，我們必須找到到達目的地的字典序第 k 小的方式。

因此，如果輸入類似於 (x, y) = (3, 3) k = 3，則輸出將為“HHVVVH”。

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

  • 定義一個函式 paths()。這將接收 x、y。
  • 如果 min(x, y) < 0，則
    • 返回 0
  • 返回 factorial(x+y)/factorial(x)/factorial(y)
  • 從主方法中執行以下操作：
  • res := 一個新的列表
  • (p, q) := (0, 0)
  • 當 (p, q) 不等於 (x, y) 時，執行以下操作：
    • n := paths(x - p - 1, y - q)
    • 如果 p + 1 <= x 且 k < n，則
      • 在 res 的末尾插入 'H'
      • p := p + 1
    • 否則，
      • k := k - n
      • 在 res 的末尾插入 'V'
      • q := q + 1
  • 返回連線 res 中字元後的結果

示例

讓我們看看以下實現以更好地理解：

from math import factorial

def paths(x, y):
   if min(x, y) < 0:
      return 0
   return factorial(x+y) / factorial(x) / factorial(y)

def solve(x, y, k):
   res = []
   p, q = 0, 0
   while (p, q) != (x, y):
      n = paths(x - p - 1, y - q)
      if p + 1 <= x and k < n:
         res.append('H')
         p += 1
      else:
         k -= n
         res.append('V')
         q += 1
   return ''.join(res)

(x, y) = (3, 3)
k = 3
print(solve(x, y, k))

輸入

(3, 3), 3

輸出

HHVVVH

更新於: 2021年10月25日

158 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告