LeetCode Integer Replacement

LeetCode Integer Replacement

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,不断对n进行如下两种操作中的一种

  1. 如果n是偶数,把n变成n/2
  2. 如果n是奇数,把n变成n+1或者n-1

问要把n变为1,需要的最少的变换次数是多少。

为啥我首先想到的是BFS。。。这不就相当于每个点根据情况可以走不同的方向,问走到终点1需要的最少步数吗?很像BFS呀。代码如下:

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;
	}
};

本代码提交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更好。

完整代码如下:

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;
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *