397. Integer Replacement - jiejackyzhang/leetcode-note GitHub Wiki

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
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 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

采用位运算可以提高效率。

1. 若n的二进制表示以0结尾，则n是even，无符号右移一位。
2. 若n的二进制表示以1结尾，则n是odd，此时需决定是加1还是减1。我们希望处理后n的'1'越少越好。 因此若n=='*01'，则n=n-1；若n=='*11'，则n=n+1不会比n-1差。唯一的例外是3，'11->10->1'比'11->100->10->1'好。 因此，当n==3 || ((n>>>1)&1)==0时，n=n-1，否则n=n+1。

public class Solution {
    public int integerReplacement(int n) {
        int res = 0;
        while(n != 1) {
            if((n & 1) == 0) {
                n >>>= 1;
            } else if(n == 3 || ((n >>> 1) & 1) == 0) {
                n--;
            } else {
                n++;
            }
            res++;
        }
        return res;
    }
}