Leetcode 397. Integer Replacement
文章目录
Given a positive integer n and you can do operations as follow:
If n is even, replace n with n/2. If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of replacements needed for n to become 1?
Example:
Input: 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1
Tips: The infamous test with n=3 fails for that strategy because 11 ->10 -> 1 is better than 11 -> 100 -> 10 -> 1.
Solution:
If n is even, halve it.
If n=3 or n-1 has less 1's than n+1,
decrement n. Otherwise, increment n.
Code:
public int integerReplacement(int n){
int count = 0;
while(n!= 1){
if((n&1)==0){
n>>>=1;
}else if(n ==3 ||((n >>>1) & 1 ==0){
--n;
} else{
++n;
}
count++;
}
return count;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论