给定一个正整数 n ,你可以做如下操作:
- 如果 n 是偶数,则用 n / 2替换 n 。
- 如果 n 是奇数,则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少?
示例 1:
输入:n = 8
输出:3
解释:8 -> 4 -> 2 -> 1
方法一:贪心
分析所有的可能我们能列出如下情况
- 传入 n 是偶数 -> 计数+1,n /= 2
- n 是奇数
- n % 4 == 1,通过分析我们可知将 n -= 1 所得结果不会比 n+= 1 更坏,故可将 n -= 1,计数+1
- n % 4 == 3
- n == 3,此时无需继续运算,计数+2 即为正确答案
- n != 3,通过分析我们可知将 n += 1 所得结果不会比 n -= 1 更坏,故可将 n += 1,计数+1
public static int integerReplacement(long n) {
int times = 0;
while (n > 1) {
if ((n & 1) != 0) { // 奇数
if (n % 4 == 1) {
++ times;
} else { // == 3
if (n == 3) {
times += 2;
break;
} else {
++ times;
++ n;
}
}
}
n >>= 1;
++ times;
}
return times;
}