Medium

题目描述

给你两个正整数 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（广度优先搜索）或者记忆化搜索来解决。

核心思路分析：

  1. 边界情况：如果 y >= x，我们只能通过加 1 操作来增大 x，所以答案是 y - x。

  2. 搜索范围确定：对于 y < x 的情况，我们需要确定搜索的上界。一个重要观察是，我们不需要让 x 增长到过大的值，因为总可以通过连续减 1 操作在 x - y 步内到达 y。合理的上界是 x + (x - y)，超过这个值的操作步数必然不会更优。

  3. 状态转移：从当前值 curr 出发，可以进行四种操作：

    • 如果 curr % 11 == 0，可以除以 11
    • 如果 curr % 5 == 0，可以除以 5
    • 可以减 1（curr - 1）
    • 可以加 1（curr + 1）

  4. 算法选择：使用 BFS 能够保证找到最少操作次数，因为 BFS 按层遍历，第一次到达目标值时的步数就是最优解。

推荐解法：BFS，时间复杂度较低且实现简单。记忆化递归也是不错的选择，代码更直观。

代码实现

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        if (y >= x) return y - x;
        
        queue<pair<int, int>> q; // {current_value, operations}
        unordered_set<int> visited;
        
        q.push({x, 0});
        visited.insert(x);
        
        while (!q.empty()) {
            auto [curr, ops] = q.front();
            q.pop();
            
            if (curr == y) return ops;
            
            vector<int> next_states;
            if (curr % 11 == 0) next_states.push_back(curr / 11);
            if (curr % 5 == 0) next_states.push_back(curr / 5);
            next_states.push_back(curr - 1);
            next_states.push_back(curr + 1);
            
            for (int next : next_states) {
                if (next >= 1 && next <= x + (x - y) && visited.find(next) == visited.end()) {
                    visited.insert(next);
                    q.push({next, ops + 1});
                }
            }
        }
        
        return x - y; // fallback, should not reach here
    }
};

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        if y >= x:
            return y - x
        
        from collections import deque
        
        queue = deque([(x, 0)])  # (current_value, operations)
        visited = {x}
        
        while queue:
            curr, ops = queue.popleft()
            
            if curr == y:
                return ops
            
            next_states = []
            if curr % 11 == 0:
                next_states.append(curr // 11)
            if curr % 5 == 0:
                next_states.append(curr // 5)
            next_states.append(curr - 1)
            next_states.append(curr + 1)
            
            for next_val in next_states:
                if 1 <= next_val <= x + (x - y) and next_val not in visited:
                    visited.add(next_val)
                    queue.append((next_val, ops + 1))
        
        return x - y  # fallback

public class Solution {
    public int MinimumOperationsToMakeEqual(int x, int y) {
        if (y >= x) return y - x;
        
        var queue = new Queue<(int curr, int ops)>();
        var visited = new HashSet<int>();
        
        queue.Enqueue((x, 0));
        visited.Add(x);
        
        while (queue.Count > 0) {
            var (curr, ops) = queue.Dequeue();
            
            if (curr == y) return ops;
            
            var nextStates = new List<int>();
            if (curr % 11 == 0) nextStates.Add(curr / 11);
            if (curr % 5 == 0) nextStates.Add(curr / 5);
            nextStates.Add(curr - 1);
            nextStates.Add(curr + 1);
            
            foreach (int next in nextStates) {
                if (next >= 1 && next <= x + (x - y) && !visited.Contains(next)) {
                    visited.Add(next);
                    queue.Enqueue((next, ops + 1));
                }
            }
        }
        
        return x - y; // fallback
    }
}

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var minimumOperationsToMakeEqual = function(x, y) {
    if (x <= y) {
        return y - x;
    }
    
    const memo = new Map();
    
    function dfs(curr) {
        if (curr <= y) {
            return y - curr;
        }
        
        if (memo.has(curr)) {
            return memo.get(curr);
        }
        
        let result = curr - y;
        
        if (curr % 11 === 0) {
            result = Math.min(result, 1 + dfs(curr / 11));
        } else {
            result = Math.min(result, (11 - curr % 11) + 1 + dfs(Math.floor(curr / 11) + 1));
            result = Math.min(result, (curr % 11) + 1 + dfs(Math.floor(curr / 11)));
        }
        
        if (curr % 5 === 0) {
            result = Math.min(result, 1 + dfs(curr / 5));
        } else {
            result = Math.min(result, (5 - curr % 5) + 1 + dfs(Math.floor(curr / 5) + 1));
            result = Math.min(result, (curr % 5) + 1 + dfs(Math.floor(curr / 5)));
        }
        
        memo.set(curr, result);
        return result;
    }
    
    return dfs(x);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型BFS解法
时间复杂度O(x - y)
空间复杂度O(x - y)

说明：

  • 时间复杂度：最坏情况下需要遍历从 1 到 x + (x - y) 范围内的所有数字，但由于除法操作的存在，实际遍历的状态数远少于这个上界，约为 O(x - y)
  • 空间复杂度：队列和访问集合最多存储 O(x - y) 个状态

相关题目