题目描述
给你两个正整数 x
和 y
。
一次操作中,你可以执行以下四种操作之一:
- 如果
x
是11
的倍数,将x
除以11
。 - 如果
x
是5
的倍数,将x
除以5
。 - 将
x
减1
。 - 将
x
加1
。
请你返回让 x
和 y
相等的 最少 操作次数。
样例
输入:x = 26, y = 1
输出:3
解释:我们可以通过以下操作将 26 变为 1:
1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
将 26 变为 1 最少需要 3 次操作。
···
···
输入:x = 54, y = 2
输出:4
解释:我们可以通过以下操作将 54 变为 2:
1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
将 54 变为 2 最少需要 4 次操作。
输入: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
算法1
(宽度优先遍历) $O(x)$
- 如果 $x \le y$,则只能使用加 1 操作,返回 $y - x$。
- 其它情况下,使用宽度优先遍历,宽搜的范围为 $[y, x + x - y)$,每次最多有四种转移方式。
时间复杂度
- 宽搜的状态数为 $O(x)$,拓展状态为常数,故总时间复杂度为 $O(x)$。
空间复杂度
- 需要 $O(x)$ 的额外空间存储状态。
C++ 代码
class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y) {
if (x <= y)
return y - x;
vector<int> d(x + x - y, INT_MAX);
queue<int> q;
q.push(x);
d[x] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == y)
break;
if (u % 11 == 0 && d[u / 11] > d[u] + 1) {
d[u / 11] = d[u] + 1;
q.push(u / 11);
}
if (u % 5 == 0 && d[u / 5] > d[u] + 1) {
d[u / 5] = d[u] + 1;
q.push(u / 5);
}
if (u < x + x - y - 1 && d[u + 1] > d[u] + 1) {
d[u + 1] = d[u] + 1;
q.push(u + 1);
}
if (u > 0 && d[u - 1] > d[u] + 1) {
d[u - 1] = d[u] + 1;
q.push(u - 1);
}
}
return d[y];
}
};
算法2
(动态规划) $O(x)$
- 如果 $x \le y$,则只能使用加 1 操作,返回 $y - x$。
- 设状态 $f(i)$ 表示从 $i$ 到 $y$ 的最小操作次数。
- 初始时,对于 $0 \le i \le y$,$f(i) = y - i$,其余为正无穷待定。
- 转移时,对于 $f(i)$,可以通过减 1 操作,从 $f(i - 1) + 1$ 转移。也可以从 $i / 11$ 转移,需要 $i \text{ MOD } 11 + 1$ 次操作。从 $i / 11 + 1$ 转移,需要 $11 - i \text{ MOD } 11 + 1$ 次操作。对于 $5$ 的转移同理。
- 最终答案为 $f(x)$。
时间复杂度
- 动态规划的状态数为 $O(x)$,转移时间为常数,故总时间复杂度为 $O(x)$。
空间复杂度
- 需要 $O(x)$ 的额外空间存储状态。
C++ 代码
class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y) {
if (x <= y)
return y - x;
vector<int> f(x + 1, INT_MAX);
for (int i = 0; i <= y; i++)
f[i] = y - i;
for (int i = y + 1; i <= x; i++) {
f[i] = f[i - 1] + 1;
f[i] = min(f[i], f[i / 11] + i % 11 + 1);
f[i] = min(f[i], f[i / 11 + 1] + 11 - i % 11 + 1);
f[i] = min(f[i], f[i / 5] + i % 5 + 1);
f[i] = min(f[i], f[i / 5 + 1] + 5 - i % 5 + 1);
}
return f[x];
}
};