使 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;
}
};