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

用 BFS遍历所有可能的操作状态,找到从x到y的最少步数。

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        // 若x<=y,只能通过加1操作达到y,步数为y-x
        if (x <= y) {
            return y - x; 
        }

        unordered_set<int> visited; // 标记已访问的数值
        queue<pair<int, int>> q;
        q.push({x, 0});
        visited.insert(x);

        while (!q.empty()) {
            auto [cur, cnt] = q.front();
            q.pop();
            if (cur == y) {
                return cnt;
            }

            if (cur % 11 == 0 && !visited.count(cur / 11)) {
                visited.insert(cur / 11);
                q.push({cur / 11, cnt + 1});
            }
            if (cur % 5 == 0 && !visited.count(cur / 5)) {
                visited.insert(cur / 5);
                q.push({cur / 5, cnt + 1});
            }
            if (cur - 1 >= y && !visited.count(cur - 1)) {
                visited.insert(cur - 1);
                q.push({cur - 1, cnt + 1});
            }
            if (cur + 1 <= x+10 && !visited.count(cur + 1)) {
                visited.insert(cur + 1);
                q.push({cur + 1, cnt + 1});
            }
        }

        return -1;
    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务