JAVA（2021-11-19）leetcode每日一题---- 整数替换

JAVA（2021-11-19）leetcode每日一题---- 整数替换

本题我采用的贪心算法，一个数要么是偶数，要么是奇数，这显而易见，所以我们就要根据这两个条件分类讨论，如果是偶数，那么直接就除以二， *** 作数加1就好了

如果是奇数，就要讨论一番，举一个例子，如果n为7 ，那么他变成8更容易，仅仅需要一次 *** 作数就可以，但是要是变成4，就需要三次 *** 作数，我们需要快速的判断出来要变大还是变小。

我们可以通过%4 *** 作做到，一个奇数%4，要么是3，要么是1，如果是1，比如5%4，那么我们肯定要将其变成4，即n=（n-1）/ 2，反之如果%4得3，比如7，那么一定是变成8，即n=(n+1)/2.

class Solution {
    public int integerReplacement(int n) {
        int res = 0;
        while(n!=1){
            if((n&1)==0){
                n/=2;            
                res++;                
            } else if(n % 4 ==1){
                n/=2;
                res+=2;
            } else{
                if(n==3){
                    res+=2;
                    n=1;
                } else{
                    res+=2;
                    n = n / 2 + 1;
                }
            }
        }
        return res;
    }
}