[LeetCode] 397. Integer Replacement

[grandyang]

 

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:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

 

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 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 题目讲解汇总(持续更新中...)

[JianHangChen]

`
class Solution {

private:

unordered_map<int, int> m = { {1,0} };

public:

int integerReplacement(int n) {

  if(m.count(n) <= 0){
    if(!(n & 1)) m[n] = 1 + integerReplacement(n >> 1);
    else m[n] = 2 + min( integerReplacement((n >> 1) + 1), 
      integerReplacement(n >> 1) );
  }
  return m[n];
}

};
`