题目

解题思路

解题代码

递归

class Solution {
    public int integerReplacement(int n) {
       if(n == 1) return 0;
       if(n == Integer.MAX_VALUE) return 32;
       if((n & 1 ) == 0) return integerReplacement(n >> 1) + 1;
       else return Math.min(integerReplacement(n+1),integerReplacement(n-1) ) + 1;
    }
}

递归（map减枝）

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public int integerReplacement(int n) {
       if(n == 1) return 0;
       if(n == Integer.MAX_VALUE) return 32; //避免溢出
       if(map.containsKey(n) ) return map.get(n);
       if((n & 1 ) == 0) { //炫技 模2可用 & 替换
           int cnt = integerReplacement(n >> 1) + 1; //炫技，除2可用>>替换
           map.put(n,cnt);
           return cnt;
       }
       else {
           int cnt = Math.min(integerReplacement(n+1),integerReplacement(n-1) ) + 1;
           map.put(n,cnt);
           return cnt;
       }
    }
}

贪心

class Solution {
    public int integerReplacement(int n) {
       if(n == 1) return 0;
       if(n == Integer.MAX_VALUE) return 32; //避免溢出
       int time = 0;
       while(n != 1) {
           if((n & 1 ) == 0) { // 为偶数 
               n = n >> 1; //除2
           } else {
               n = n - 1; //默认-1
               //判断减1后,n除2后的奇偶性，若为基数且减1后的n不为2时取 n+ 2
               //需考虑特殊情况，n为3,减去1后，除2位1，不应取 原 n + 1
               if(  ( ( n >> 1 ) & 1 ) == 1 && n != 2  ) { 
                   n = n + 2; //前面n - 1,故此处+2 (等价于 未减1的n  加 1)
               }
           }
           time++;
       }
        return time;
    }
}