使 X 和 Y 相等的最少操作次数

难度: Medium

给你两个正整数 x 和 y 。

一次操作中，你可以执行以下四种操作之一：

如果 x 是 11 的倍数，将 x 除以 11 。
如果 x 是 5 的倍数，将 x 除以 5 。
将 x 减 1 。
将 x 加 1 。

请你返回让 x 和 y 相等的最少操作次数。

示例 1：

输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：
1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
将 26 变为 1 最少需要 3 次操作。

示例 2：

输入：x = 54, y = 2
输出：4
解释：我们可以通过以下操作将 54 变为 2 ：
1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
将 54 变为 2 最少需要 4 次操作。

示例 3：

输入：x = 25, y = 30
输出：5
解释：我们可以通过以下操作将 25 变为 30 ：
1. 将 x 加 1
2. 将 x 加 1
3. 将 x 加 1
4. 将 x 加 1
5. 将 x 加 1
将 25 变为 30 最少需要 5 次操作。

提示：

1 <= x, y <= 10⁴

Submission

运行时间: 27 ms

内存: 16.4 MB

class Solution:
    @cache
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if x <= y:
            return y - x
        return min(x - y,
                   self.minimumOperationsToMakeEqual(x // 11, y) + x % 11 + 1,
                   self.minimumOperationsToMakeEqual(x // 11 + 1, y) + 11 - x % 11 + 1,
                   self.minimumOperationsToMakeEqual(x // 5, y) + x % 5 + 1,
                   self.minimumOperationsToMakeEqual(x // 5 + 1, y ) + 5 - x % 5 + 1
        )

Explain

这个题解采用了递归的方法，结合记忆化搜索（通过 @cache 装饰器实现），来找到将 x 变为 y 的最少操作次数。如果 x 小于等于 y，直接返回 y - x，因为这种情况下只能通过增加操作使 x 等于 y。当 x 大于 y 时，有五种可能的操作：直接减去 x - y，或者通过除以 11 或 5，并考虑到整除后的余数，决定是直接除还是除后再加 1 来尽可能接近 y。递归调用处理除以 11 和 5 的情况，并考虑余数带来的额外操作，最终取所有情况的最小值。

时间复杂度: O(log(x) * log(y))

空间复杂度: O(log(x) * log(y))

class Solution:
    @cache
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if x <= y:
            # 如果 x 小于等于 y，直接通过增加操作使 x 等于 y
            return y - x
        # 递归计算 x 大于 y 的情况，考虑所有可能的操作
        return min(x - y,  # 直接减少 x 到 y
                   self.minimumOperationsToMakeEqual(x // 11, y) + x % 11 + 1,  # 除以 11 后余数处理
                   self.minimumOperationsToMakeEqual(x // 11 + 1, y) + 11 - x % 11 + 1,  # 除以 11 后需要额外加 1 的情况
                   self.minimumOperationsToMakeEqual(x // 5, y) + x % 5 + 1,  # 除以 5 后余数处理
                   self.minimumOperationsToMakeEqual(x // 5 + 1, y ) + 5 - x % 5 + 1  # 除以 5 后需要额外加 1 的情况
        )

Explore

在这个算法中，考虑了11 - x % 11 + 1这种情况，是为了处理x不是11的倍数时的情形。当x不是11的整数倍时，x % 11得到的余数不为0，此时x除以11后还需要进一步的操作使其更接近y。选项11 - x % 11 + 1表示我们将x除以11后，还需要额外加1以确保能整除11，然后再处理余数，这样可以确保在余数大于11的一半时通过加1操作达到更少的总操作次数。即使x是11的倍数，也需要这种考虑来处理通用情况，确保算法的完整性和正确性。

递归解法中使用min函数是为了在所有可能的操作中选择最小的操作次数，从而确保找到将x变为y所需的最少操作次数。直接减少x到y是最优解的情况通常出现在x与y相差不大，且其它操作（如除以11或5后再进行调整）所需的步骤会更多时。特别是当x稍大于y，直接减掉差值通常比进行多次除法和余数处理要高效。

题解中这种做法简单直接，适用于x小于等于y的情况下，确保操作次数是最少的，因为直接增加差值是最直接的方法。如果x刚好是y的11倍或5倍，虽然理论上存在通过多次除法可能减少到y的情况，但从实用角度出发，如果x小于等于y，进行增加操作无疑是最简单直接的方法。在实际问题中，通常考虑操作的复杂性和实现的直观性，直接增加差值是最符合逻辑的选择。

这种策略通过考虑所有可能的余数处理方式来寻找最小的操作次数。加1或直接处理余数的决策基于尝试使x尽可能快地逼近y的原则。如果余数较小，直接处理余数通常是更优的；如果余数较大，通过增加1后再处理余数可能会更接近y，从而减少总的操作次数。通过递归和min函数的组合，算法能够在所有这些可能的情况中找到最优解，并确保每一步都是向着最小操作次数前进。