首页 > 代码库 > LeetCode之整数替换

LeetCode之整数替换

最近在开始做LeetCode的算法题

做的第一题是的题目如下:

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?

可以看到题目最难的是在数为奇数时如何判断是加还是减。

最开始我的想法是如果这个基数在加一之后是2的n次幂的话+1,否则就减一,因为程序效率方面的要求的话,使用位操作来判断

代码如下

if((n+1) & n ==0)
    n++;
else
    n--;

但是这段代码提交之后出错:n == 3时,代码出错,我认为这是个特例,所以在代码里面加了额外的判断

再次提交,程序在10000的时候有出现错误。分析之后我发现最初的思路并不能行。

在论坛看了排名第一的解之后恍然大悟:https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations

对数的二进制分析(毕竟和2关系很大),发现奇数的最后两位只有两种情况:01和11
分析后可以发现,在01时减1,11时加1得出的解最优。

但是,这里还有一个叛徒,那就是3(还真是特殊额),你会发现他二进制为11,但是按规则加一并不是最优解。

对3进行特殊处理。

之后的代码就是:

int integerReplacement(int n) 
{
    unsigned int x;
    int count = 0;
    x = n;
    
    while(x != 1)
    {
        if((x & 1) == 0)
            x >>= 1;
        else if(x == 3 || ((x >> 1) & 1) == 0)
            x--;
        else
            x++;
        count++;
    }
    
    return count ;
}

 

LeetCode之整数替换