数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 次查看
广告