[LeetCode] 1643. 第 K 条最小指令

时间：2022-10-15 08:00:00 cnr25d121k电阻

题目

Bob 站在单元格 (0, 0) ，想去目的地 destination ：(row, column) 。他只能向右或向下走吧。你可以 Bob 提供导航指令帮他到达目的地 destination 。

指令每个字符都用字符串表示:

‘H’ ，意味着水平向右移动
‘V’ ，意味着竖直向下移动
能够为 Bob 导航到目的地 destination 如果目的地有多种指令，例如 destination 是 (2, 3)，“HHHVV” 和 “HVHVH” 都是有效指令。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循按字典顺序排列后的第 k 条最小指令导航到目的地 destination 。k 的编号从 1 开始。

给你一个整数数组 destination 和一个整数 k ，请返回 Bob 提供到目的地 destination 导航的按字典顺序排列后的第 k 条最小指令。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-instructions
作权归网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给 $a$ 个 $H$ , $b$ 个 $V$ , 在所有字符串中，字典序第k小串。
第一个元素是固定的 $H$ ，总共有 $C_{a b-1}^{a-1}$ 个元素，第一个为 $V$ , 总共有 $C_{a b-1}^{a}$ 个元素。根据k的大小，我们就知道了第一个元素是什么。依次判断每一个元素就可以了
可能出现计算组合数占用的时间太长的问题，避免重复计算，我们可以用缓存中间的技术。
$C_{n}^{r} = \frac{n}{r}C_{n-1}^{r-1}$

代码

from functools import lru_cache
class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        b, a = destination
        @lru_cache
        def C(n, r):
            if r == 0: return 1
            return n * C(n - 1, r - 1) / r
        
        def solve(a, b,k, ret):
            if a == 0: return ret + ("V" * b)
            if b == 0: return ret + ("H" * a)
            if k > C(a+b-1, a-1):
                return solve(a, b-1, k - C(a+b-1, a-1), ret + "V")
            else:
                return solve(a - 1, b, k , ret + "H")
        
        return solve(a, b , k , "")

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

[LeetCode] 1643. 第 K 条最小指令

相关文章