397 整数替换

题目描述

给定一个正整数 n ，你可以做如下操作：

如果 n 是偶数，则用 n / 2替换 n 。 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。 n 变为 1 所需的最小替换次数是多少？

示例 1：

输入：n = 8 输出：3 解释：8 -> 4 -> 2 -> 1

题解 我原本想用递归

偶数： retuen f(n / 2) + 1

奇数：retuen min(f(n + 1), f(n - 1)) + 1;

很不幸，栈溢出了，我又用数组改递推了，又很不幸内存爆了

看了题解，这道题有点厉害，其实就是转换二进制，怎么最快取到第一位数1，偶数可以直接直接除2，奇数到底是加1还是减1，其实要看最后两位是11 还是 01，11可以加1，01，可以减1，11直接消除了两个1，01，1的数量不变，除以2直接还是要面临位数是1的结局，转换明显变多了

public int integerReplacement(long n) {
       int count = 0;
       while (n > 1) {
           if (n % 2 == 0) {
               n = n / 2;
               count++;
           } else {
               if ((n & 0x3) == 3 && n != 3) {
                   n = n + 1;
                   count++;
               } else {
                   n = n - 1;
                   count++;
               }
           }
       }
       return count;
    }