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

You are given two positive integers x and y.

In one operation, you can do one of the four following operations:

1. Divide x by 11 if x is a multiple of 11.
2. Divide x by 5 if x is a multiple of 5.
3. Decrement x by 1.
4. Increment x by 1.

Return the minimum number of operations required to make x and y equal.

 

Example 1:

Input: x = 26, y = 1
Output: 3
Explanation: We can make 26 equal to 1 by applying the following operations: 
1. Decrement x by 1
2. Divide x by 5
3. Divide x by 5
It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.

Example 2:

Input: x = 54, y = 2
Output: 4
Explanation: We can make 54 equal to 2 by applying the following operations: 
1. Increment x by 1
2. Divide x by 11 
3. Divide x by 5
4. Increment x by 1
It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.

Example 3:

Input: x = 25, y = 30
Output: 5
Explanation: We can make 25 equal to 30 by applying the following operations: 
1. Increment x by 1
2. Increment x by 1
3. Increment x by 1
4. Increment x by 1
5. Increment x by 1
It can be shown that 5 is the minimum number of operations required to make 25 equal to 30.

 

Constraints:

• 1 <= x, y <= 104

// Java Stream solution
// 思路：与Java解法相同，Java Stream不适合处理复杂的控制流，使用Java解法实现即可。
import java.util.LinkedList;
import java.util.Queue;

public class MinOperationsStream {
    public int minOperations(int x, int y) {
        if (x == y) return 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, 0});
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int val = current[0];
            int steps = current[1];
            if (val == y) return steps;
            if (val % 11 == 0) queue.offer(new int[]{val / 11, steps + 1});
            if (val % 5 == 0) queue.offer(new int[]{val / 5, steps + 1});
            queue.offer(new int[]{val - 1, steps + 1});
            queue.offer(new int[]{val + 1, steps + 1});
        }
        return -1;
    }
}

这个题解采用了递归的方法，结合记忆化搜索（通过 @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))