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

题干分析：

我们针对一个整数x能够进行以下操作：

• x = x - 1
• x = x + 1
• if x % 5 == 0 : x = x / 5
• if x % 11 == 0 : x = x / 11 题设给予我们原始数与目标数，要求我们返回将原始数进行n次操作后能够得到目标数的最小操作数

算法思路：

使用BFS搜索+剪枝缩小搜索范围

我们可以很明显的看到四种操作只有第二种加一的操作能够使x的值增大，其他情况均只能使x的值减小，因此我们很容易得到以下剪枝策略：

• 当k <= y 时对k再进行y-k次操作使其到达y。
• 当k > y 时对k可能的操作进行BFS搜索

实现代码：

int minimumOperationsToMakeEqual(int x, int y) {
        if (x <= y) return y - x; // 特判

        int ans = x - y; // 操作最多进行次数（直接将x持续-1减到y）
        unordered_set<int> vis; // 标记已来过
        vector<int> buf; // 下一轮BFS对象
        int step = 0; // 轮次计数

        auto push = [&](int param) { // 压入可能的BFS搜索对象
            if (param < y) ans = min(ans, step + y - param + 1); // 剪枝策略
            else if (vis.find(param) == vis.end()) {
                vis.insert(param);
                buf.push_back(param);
            }
        };

        push(x); // 启动
        while (true) {
            auto tmp = buf;
            buf.clear();
            for (int i : tmp) { // BFS
                if (i == y) return min(ans, step); // BFS搜到结果
                push(i + 1);
                push(i - 1);
                if (i % 5 == 0) push(i / 5);
                if (i % 11 == 0) push(i / 11);
            }
            ++step;
        }
    }

复杂度分析：

• 时间复杂度：对于小于x的每个值BFS均最多到访一次，总时间复杂度为O（x）
• 空间复杂度：到访标记最高空间消耗为O（x），BFS缓冲暂存数组空间不占主体，总空间复杂度为O（x）