frendguo's blog

【LeetCode】397. Integer Replacement

原文地址:https://leetcode.com/problems/integer-replacement/#/description

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

刚开始看到这个时一脸懵逼的,大致的算了下,一个输入可能对应着好几个输出,就比如输入 5 的话,就对应着3、4、5 然后测试了下,发现系统要的是3,也就是最小值。

首先想到的就是 将输入化为二进制,然后最高位 1 后面的位数 + 最高位后面 1 的个数就是输出。比如 101 => 2 + 1 = 3; 111 => 2 + 2 = 4;

好像一切都没有问题的样子,然后想了下大点的数 1111, 按照上面的方法计算的话,输出应该是 6, 而实际结果应该是 5 。

于是发现 在 1111 的情况下,上述的方法是减一,而实际上加一的话 输出会更加小。

然后再仔细一想,大多数情况下都是加一要简单点,某些情况下,比如 *01 这种情况下,减一要比加一要好,还有 3 (11) 这个特殊的值。

于是就有下面的代码:

static int IntegerRelacement(int n)
{
	int res = 0;
	while (n != 1)
	{
		if ((n & 1) == 0)
		{
			n >>= 1;
		}
		else if ((n == 3) || ((n >> 1) & 1) == 0)
		{
			--n;
		}
		else
		{
			++n;
		}
		++res;
	}

	return res;
}

然后一提交,超时了┌(。Д。)┐

于是继续想优化,发现是死在了 2147483647 (0111 1111 1111 1111 1111 1111 1111 1111)手里,原来是有符号整数溢出了。。于是有以下代码:

static int IntegerRelacement(int num)
{
	int res = 0;
	long n = (long)num;
	while (n != 1)
	{
		if ((n & 1) == 0)
		{
			n >>= 1;
		}
		else if ((n == 3) || ((n >> 1) & 1) == 0)
		{
			--n;
		}
		else
		{
			++n;
		}
		++res;
	}

        return res;
}

提交,搞定~

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading