397. Integer Replacement

题目描述和难度

题目描述：

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

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

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1

示例 2:

输入:
7

输出:
4

解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1

题目难度：中等。
英文网址：397. Integer Replacement 。
中文网址：397. 整数替换。

思路分析

求解关键：

参考解答

参考解答1：比较容易想到的一种做法是根据题意，使用递归完成。

这里要特别注意一个特例，那就是整型数的最大值的二进制：1111111111111111111111111111111，对于它的结果是 32（我是从测试用例中看出来的，但是我觉得这个数要变成 1 应该经过 33 步），不过只有这一个特殊的用例，我们暂且这样写是不会错的。

public class Solution6 {

    public int integerReplacement(int n) {
        if (n == Integer.MAX_VALUE) {
            return 32;
        }
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n % 2 == 0) {
            return 1 + integerReplacement(n / 2);
        }
        return 1 + Math.min(integerReplacement(n - 1), integerReplacement(n + 1));
    }
}

写成下面这样也是可以的：

public class Solution {

    public int integerReplacement(int n) {
        return longReplacement(n);
    }

    private int longReplacement(long n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n % 2 == 0) {
            return longReplacement(n / 2) + 1;
        }
        return 1 + Math.min(longReplacement(n + 1), longReplacement(n - 1));
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = Integer.MAX_VALUE;
        int integerReplacement = solution.integerReplacement(n);
        System.out.println(integerReplacement);
    }
}

参考解答2：动态规划的写法。

使用了递归，那么根据套路，可以将这道问题的解法改成非递归的形式。比较容易想到用动态规划试试。
我们知道，这道题一个较大的数的结果，可以通过较少的数的结果计算得到，于是，很容易写出下面的代码。
但是，提交之后，我们会发现，一下子要开辟那么多空间其实是没有必要的。并且，如果我们要计算 8 ，实际上只需要 1、2、4 的结果就可以了，没有必要依次计算 1、2、3、4、5、6、7 的结果，所以这种做法其实更浪费时间和空间。

(注意：下面这种做法不能通过测试，是一个反例。)

public class Solution2 {

    // 接下来把递归改成动态规划，这个解法通不过，不过采用动态的方式就可以了
    // 这行解法空间复杂度太高，会 超出内存限制

    public int integerReplacement(int n) {
        // 0 要占一个位子，所以要给出 n+1 个位子

        if (n <= 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 1;
            } else {
                // 这样写就太死板了
                // dp[i] = 1 + Math.min(dp[i - 1], dp[i + 1]);
                dp[i] = Math.min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2);
            }
        }
        return dp[n];
    }
}

不过，我们不用那么死板，我们可以使用动态的数据结构。
下面的这种写法更像是记忆化搜索。

import java.util.HashMap;
import java.util.Map;

public class Solution2 {

    // 接下来把递归改成动态规划，使用 Hash 表
    // 使用动态的红黑树就不会 超出内存限制 了

    public int integerReplacement(int n) {
        // 0 要占一个位子，所以要给出 n+1 个位子
        if (n <= 1) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        return helper(n, map);
    }

    private int helper(int n, Map<Integer, Integer> map) {
        Integer value = map.get(n);
        if (value == null) {
            if (n % 2 == 0) {
                value = helper(n / 2, map) + 1;
            } else {
                // n-1 /2
                // n+1 /2
                value = 2 + Math.min(helper(n / 2, map), helper(n / 2 + 1, map));
            }
        }
        return value;
    }
}

参考解答3：这种写法要使用一些数学知识。

根据规则，如果遇到奇数，要先变成偶数。
二进制后面的 0 越多，表示除以 2 一直可以整除的次数就越多，不妨举几个例子，写出二进制分解，可以提取出 2 的次方数。

根据上面的思路，可以写出下面的代码。

public class Solution3 {

    // https://www.cnblogs.com/maizi-1993/p/5909887.html
    // 有点贪心算法的意思

    public int integerReplacement(int n) {
        // 先考虑特殊情况
        if (n == Integer.MAX_VALUE) {
            return 32;
        }
        int res = 0;
        while (n != 1) {
            // 当 n 不论是奇数还是偶数的时候，变成偶数，消耗一个操作
            res++;
            if ((n & 1) == 0) {
                n >>= 1;
            } else {
                // 谁末尾的 0 多，就变成谁
                // 只有 3 这一个特例
                if (n == 3 || countTailZeros(n - 1) > countTailZeros(n + 1)) {
                    n--;
                } else {
                    n++;
                }
            }
        }
        return res;
    }

    // 这里很关键！！！末尾有几个 0 就表示可以提取的公因子！
    // 这里很关键！！！末尾有几个 0 就表示可以提取的公因子！
    // 这里很关键！！！末尾有几个 0 就表示可以提取的公因子！
    // 110100 52 26 13

    // 这个做法有点"过"，是很充分的做法
    private int countTailZeros(int num) {
        int count = 0;
        while (num % 2 == 0) {
            count++;
            num >>= 1;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));
    }
}

参考解答4：这种解法更深地挖掘了一些数学上的性质。

public class Solution4 {

    // 参考资料：https://segmentfault.com/a/1190000007318944

    public int integerReplacement(int n) {
        long num = n;
        int res = 0;
        while (num != 1) {
            res++;
            if ((num & 1) == 0) {
                // 是偶数的时候，直接右移
                num >>= 1;
            } else {
                // 是奇数的时候
                // 2 的二进制是 10，即如果倒数第 2 位是 1 的话
                // 加 1 能消耗掉更多的 1
                // 例如：
                // 如果倒数第二位是 0，那么 n - 1 的操作比 n + 1 的操作能消掉更多的 1
                // 1001 + 1 = 1010
                // 1001 - 1 = 1000
                // 如果倒数第二位是 1，那么 n + 1 的操作能比 n - 1的操作消掉更多的 1
                // 1011 + 1 = 1100
                // 1111 + 1 = 10000
                if ((num & 2) != 0 && num != 3) {
                    num++;
                } else {
                    num--;
                }
            }
        }
        return res;
    }
}

参考解答1

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0397-integer-replacement ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。