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:8Output:3Explanation:8 -> 4 -> 2 -> 1

Example 2:

Input:7Output:4Explanation:7 -> 8 -> 4 -> 2 -> 1or7 -> 6 -> 3 -> 2 -> 1

这道题给了我们一个整数n，然后让我们通过变换变为1，如果n是偶数，我们变为n/2，如果是奇数，我们可以变为n+1或n-1，让我们求变为1的最少步骤。那么一看道题的要求，就会感觉应该用递归很合适，我们直接按照规则写出递归即可，注意由于有n+1的操作，所以当n为INT_MAX的时候，就有可能溢出，所以我们可以先将n转为长整型，然后再进行运算，参见代码如下：

解法一：

class Solution {public:    int integerReplacement(int n) {        if (n == 1) return 0;        if (n % 2 == 0) return 1 + integerReplacement(n / 2);        else {            long long t = n;            return 2 + min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2));        }    }}; 

我们也可以使用迭代的解法，那么这里就有小技巧了，当n为奇数的时候，我们什么时候应该加1，什么时候应该减1呢，通过观察来说，除了3和7意外，所有加1就变成4的倍数的奇数，适合加1运算，比如15:

15 -> 16 -> 8 -> 4 -> 2 -> 1

15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1

对于7来说，加1和减1的结果相同，我们可以不用管，对于3来说，减1的步骤小，所以我们需要去掉这种情况。那么我们如何知道某个数字加1后是否是4的倍数呢，我们可以用个小技巧，由于我们之前判定其是奇数了，那么最右边一位肯定是1，如果其右边第二位也是1的话，那么进行加1运算，进位后右边肯定会出现两个0，则一定是4的倍数，搞定。如果之前判定是偶数，那么除以2即可，参见代码如下：

解法二：

class Solution {public:    int integerReplacement(int n) {        long long t = n;        int cnt = 0;        while (t > 1) {            ++cnt;            if (t & 1) {                if ((t & 2) && (t != 3)) ++t;                else --t;            } else {                t >>= 1;            }        }        return cnt;    }};

参考资料：

https://discuss.leetcode.com/topic/58655/0ms-cpp-solution

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Integer Replacement 整数替换