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

题目

给你两个正整数 x 和 y 。

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

1. 如果 x 是 11 的倍数，将 x 除以 11 。
2. 如果 x 是 5 的倍数，将 x 除以 5 。
3. 将 x 减 1 。
4. 将 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^4

解答

方法一：BFS

建图操作：

• 从 v 向 v // 11 连边
• 从 v 向 v // 5 连边
• 从 v 向 v - 1 连边
• 从 v 向 v + 1 连边
• 边权为 1，因此是求 x -> y 的最短路

要不要估计 x 的最大值呢？

• vis 数组实现访问过的点：要估计
• 哈希表则不用估计
• 最短路长度最多是 x - y（使用最慢的第三步）
• 因此数组中可能存在的最大值为 x + x - y， + 1 防止边界

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if x <= y:
            return y - x
        
        # x > y
        ans = x - y
        vis = [False] * (x + x - y + 1)
        q = []
        step = 0
        # dis 数组

        # 把 v 加到队列中
        def add(v: int) -> None:
            if v < y:
                nonlocal ans
                ans = min(ans, step + 1 + y - v)
                
            elif not vis[v]:
                vis[v] = True
                q.append(v)

        add(x)

        while True:
            tmp = q
            q = []

            for v in tmp:
                if v == y:
                    return min(ans, step)
                
                if v % 11 == 0:
                    add(v // 11)
                if v % 5 == 0:
                    add(v // 5)
                add(v - 1)
                add(v + 1)
            
            step += 1