整数替换
难度:
标签:
题目描述
给定一个正整数 n
,你可以做如下操作:
- 如果
n
是偶数,则用n / 2
替换n
。 - 如果
n
是奇数,则可以用n + 1
或n - 1
替换n
。
返回 n
变为 1
所需的 最小替换次数 。
示例 1:
输入:n = 8 输出:3 解释:8 -> 4 -> 2 -> 1
示例 2:
输入:n = 7 输出:4 解释:7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1
示例 3:
输入:n = 4 输出:2
提示:
1 <= n <= 231 - 1
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
* This code provides a solution for the given problem using Java Streams.
* Streams in Java are typically used for collections, so here we use an
* iterative approach wrapped in a lambda function to apply the necessary
* operations. Note that using Streams directly for this problem isn't
* the most natural fit, but we can simulate a stream-like behavior.
*/
import java.util.function.IntUnaryOperator;
import java.util.stream.IntStream;
public class Solution {
public int integerReplacement(int n) {
IntUnaryOperator operator = num -> {
int count = 0;
while (num != 1) {
if (num % 2 == 0) {
num /= 2;
} else if (num == 3 || (num & 2) == 0) {
num--;
} else {
num++;
}
count++;
}
return count;
};
return operator.applyAsInt(n);
}
}
解释
方法:
这个题解采用迭代的方式求解整数替换问题。通过循环对给定的整数 n 进行操作,每次循环根据 n 的奇偶性选择不同的操作。当 n 为偶数时,直接除以2;当 n 为奇数时,判断 n 的二进制表示的次低位是否为1(即 n&2 是否为真),如果是的话(排除 n=3 的特殊情况),就给 n 加1,否则就给 n 减1。循环进行直到 n 变为1,记录操作次数并返回。
时间复杂度:
O(log(n))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在处理奇数的时候,需要检查n的二进制表示的次低位是否为1?这种方法如何影响操作次数的最小化?
▷🦆
特例n=3时为什么选择减1而不是加1,这种选择对于算法的效率有何影响?
▷🦆
在每次操作时,对n进行加1或减1的决策依据是什么?如何确定这种决策会导致更快地达到目标1?
▷🦆
这种迭代方法是否考虑了所有可能的操作路径以确保结果是最小操作次数?如果没有,如何改进算法以考虑不同的路径选择?
▷