LeetCode Integer Replacement
Given a positive integer n and you can do operations as follow:
- If n is even, replace n with
n/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，不断对n进行如下两种操作中的一种
- 如果n是偶数，把n变成n/2
- 如果n是奇数，把n变成n+1或者n-1
问要把n变为1，需要的最少的变换次数是多少。
为啥我首先想到的是BFS。。。这不就相当于每个点根据情况可以走不同的方向，问走到终点1需要的最少步数吗？很像BFS呀。代码如下：
[cpp]
class Solution {
private:
struct P {
long long val;
int step;
P(long long v_, int s_) :val(v_), step(s_) {};
};
public:
int integerReplacement(int n) {
P p(n, 0);
queue<P> qp;
qp.push(p);
while (!qp.empty()) {
P f = qp.front();
qp.pop();
if (f.val == 1)return f.step;
else if (f.val & 1) {
qp.push(P(f.val + 1, f.step + 1));
qp.push(P(f.val – 1, f.step + 1));
}
else {
qp.push(P(f.val / 2, f.step + 1));
}
}
return 0;
}
};
[/cpp]
本代码提交AC，用时6MS，只击败5%的人。。。
看讨论区，用位运算求解。要想快速的到达1，则n的二进制中0越多越好，因为0越多，后续越有可能用n/2快速的去掉一位。所以如果n是奇数时，我们判断一下n+1和n-1哪个包含的0越多，就走哪步。
但是每次都需要求n+1和n-1中1的个数，复杂度有点高。
其实，我们只需要关注n的最后两个二进制位即可。任何一个数的二进制尾数最后两位可能有四种情况，00、01、10、11，如果n是偶数，即以00或10结尾，则显然n/2能快速的减少一位。但是如果是01或者11呢。如果是01，则减1会变成00，如果加1，会变成10。显然，减1之后多出一个0，而加1之后0的个数没变，所以如果是以01结尾，则减1更优。
如果末尾是11，则减1变成10，加1变成100，显然加1更优。
有一个例外是，如果n就等于3，即二进制为11，则11→10→1比11→100→10→1更优，即当n==3时，减1更好。
完整代码如下：
[cpp]
class Solution {
public:
int integerReplacement(int n) {
if (n == INT_MAX)return 32;
int ans = 0;
while (n > 1) {
if ((n & 1) == 0) n >>= 1;
else if (n == 3 || ((n >> 1) & 1) == 0)–n;
else ++n;
++ans;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时3MS。]]>