将整数减少到零需要的最少操作数
难度:
标签:
题目描述
You are given a positive integer n, you can do the following operation any number of times:
- Add or subtract a power of
2fromn.
Return the minimum number of operations to make n equal to 0.
A number x is power of 2 if x == 2i where i >= 0.
Example 1:
Input: n = 39 Output: 3 Explanation: We can do the following operations: - Add 20 = 1 to n, so now n = 40. - Subtract 23 = 8 from n, so now n = 32. - Subtract 25 = 32 from n, so now n = 0. It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
Example 2:
Input: n = 54 Output: 3 Explanation: We can do the following operations: - Add 21 = 2 to n, so now n = 56. - Add 23 = 8 to n, so now n = 64. - Subtract 26 = 64 from n, so now n = 0. So the minimum number of operations is 3.
Constraints:
1 <= n <= 105
代码结果
运行时间: 18 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 计算小于 n 的所有 2 的幂次方。
* 2. 使用广度优先搜索（BFS）找到到达 0 的最短路径。
* 3. 使用 Stream 处理数据。
*/
import java.util.*;
import java.util.stream.IntStream;
public class MinOperationsToZeroStream {
public int minOperations(int n) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(n);
visited.add(n);
int operations = 0;
// 计算所有可能的2的幂次方
int[] powersOfTwo = IntStream.range(0, 18)
.map(i -> 1 << i)
.toArray();
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int current = queue.poll();
if (current == 0) return operations;
for (int power : powersOfTwo) {
int next1 = current + power;
int next2 = current - power;
if (visited.add(next1)) queue.offer(next1);
if (visited.add(next2)) queue.offer(next2);
}
}
operations++;
}
return -1; // 不会到达这里
}
}解释
方法:
这个题解采用了一种贪心的思路。首先，将整数 n 转换为二进制表示。然后从最低位开始遍历，每次遇到 1 时，进行一次操作，将该位变为 0。如果这个 1 的左边还有 1，则需要额外进行一次操作，将左边的 1 都变为 0，最左边的 0 变为 1。这样做的原因是，每次操作都是加上或减去 2 的某个幂，所以在二进制表示中，就是在某个位置加上或减去 1。这个过程一直进行，直到整个二进制表示中没有 1 为止。
时间复杂度:
O(log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
为何在处理二进制表示中的每个位时，遇到1就要进行加或减操作？这种操作如何保证最终能够使n等于0？
▷🦆
在题解中提到，如果1的左边还有1，则需要额外进行一次操作，这种操作的逻辑是如何确定的？即为什么要将最左边的0变为1？
▷🦆
题解中提到，当整个二进制表示中没有1为止时，过程才结束。这是否意味着对于每个位的处理都是必需的，即使这个位后面全是0？
▷🦆
题解中没有详细说明如何处理二进制数的最高位。当最高位为1，且左边没有更高的位时，我们如何处理这种情况？
▷