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 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告