恰好移动 k 步到达某一位置的方法数目

难度: Medium

给你两个正整数 startPos 和 endPos 。最初，你站在无限数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、恰好移动 k 步并到达 endPos 的不同方法数目。由于答案可能会很大，返回对 10⁹ + 7 取余的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意：数轴包含负整数。

示例 1：

输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。

示例 2：

输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。

提示：

1 <= startPos, endPos, k <= 1000

Submission

运行时间: 35 ms

内存: 16.0 MB

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        n = abs(endPos-startPos)
        if k < n or k-n & 1: return 0
        return math.comb(k,k-n>>1) % 1000000007

Explain

此题解的核心思路基于组合数学。首先，考虑从 startPos 到 endPos 的最小步数 n，即直线距离的绝对值。若要恰好移动 k 步到达 endPos，必须满足两个条件：(1) k 要大于或等于 n，因为少于 n 步无法到达；(2) k 和 n 的差必须是偶数，因为每一步向反方向移动会增加两步距离，且只有偶数步可以通过相等数量的左右移动抵消。若这两个条件不满足，则无法在 k 步内准确到达 endPos，返回 0。如果条件满足，那么问题可以转化为在 k 步中，选择一半的步数向目的地方向移动（(k+n)/2 步），其余的步数向相反方向移动，这可以通过计算组合数 C(k, (k+n)/2) 来解决。最后，由于结果可能很大，对 1000000007 取模。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        # 计算 startPos 到 endPos 的距离
        n = abs(endPos - startPos)
        # 如果 k 小于 n 或者 k-n 是奇数，返回 0
        if k < n or (k - n) & 1: return 0
        # 计算组合数 C(k, (k+n)//2)，并取模 1000000007
        return math.comb(k, (k - n) >> 1) % 1000000007

Explore

在题目中，每次移动可以是向目标位置前进或后退一步。如果 k 步全部向前，则到达的最远距离是 k 位置。要在 k 步准确到达 endPos，除了要覆盖最小距离 n 之外，任何额外的步数必须通过等量的前进和后退来抵消。如果 k-n 是奇数，无法将额外步数平分为前进和后退，因为分配会有一个步数无法匹配，从而无法达到目标。而如果 k-n 是偶数，可以将额外的步数平均分配为前进和后退，从而确保精确到达 endPos。

使用 `(k - n) & 1` 判断奇偶性是一种更快的方法。该操作直接检查数字的最低位二进制，如果为 1 则为奇数，为 0 则为偶数。相比之下，使用模运算 `k - n % 2` 需要执行除法操作，效率较低。位运算通常比算术运算要快，因此在性能敏感的上下文中，使用位运算是一种优化。

如果 k 非常大，计算组合数 `C(k, (k+n)//2)` 可能会遇到效率和精度问题。首先，组合数的计算涉及到大数的乘法和除法，计算复杂度和时间成本会随着 k 的增加而显著提高。此外，大数运算可能超过常规数据类型的存储能力，导致溢出或精度损失。在实际应用中，可能需要使用特定的库或算法来处理大数的高精度运算，例如使用动态规划或利用模运算的性质来分步计算结果。

模 1000000007 是常用的一个大质数，广泛用于算法中防止整数溢出并保持结果的可管理性。由于它是质数，可以在模运算的环境下保持良好的数学性质，如避免值的重复。此外，1000000007 足够大，能够保证大多数情况下的计算不会因为模数太小而导致频繁的冲突或溢出，同时又能适应常见的整数数据类型范围。使用模运算也有助于确保结果的稳定性和安全性，特别是在涉及网络和分布式系统的编程中。