leetcode 397

题目描述：

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

分析，这个题第一眼看上去可以用递归，而且用递归确实可以实现，这就是第一种解法，但是递归的效率不高，这是大家的共识，在我翻看他人的博客和结题经验时，发现了另外一种非递归的方式，
只是这种非递归的方法比较难想，就是自己按照思路实现之后仍然一头雾水，毕竟这个算法不是自己想出来的，感觉其中糅合了贪心算法和动态规划，这是算法题中比较难的两种思想，这也理所当
然地成了我的拦路虎……

解法一：递归方式

int integerReplacement(int n)

{

    if(n == INT_MAX)

        return ;

    if(n <= )

        return ;

    if((n & ) == )

        return  + integerReplacement(n / );

    else

        return  + min(integerReplacement(n - ), integerReplacement(n + ));

}

注意第一种case，可以防止溢出，第一次提交的时候就是这个case出错。

解法二：

int integerReplacement(int n)

{

    if (n == INT32_MAX)

        return ;

    int counter = ;

    while (n != )

    {

        if ((n & ) == )

        {

            ++ counter;

            n = (n >> );

        }

        else

        {

            if (n == )

                n = ;

            else

            {

                if (containBinaryZeros(n - ) > containBinaryZeros(n + ))

                    -- n;

                else

                    ++ n;

            }

            ++counter;

        }

    }

    return counter;

}

int containBinaryZeros(int n)

{

    int counter = ;

    while ((n & ) == )

    {

        ++counter;

        n = n >> ;

    }

    return counter;

}

注意其中的特殊case（如3），以及运算的顺序（如== 和 &的运算顺序），第一次提交的时候也是因为没有把&运算给单独括起来导致的bug，所以一定要清晰运算的优先级，

尤其是逻辑运算和算术运算的优先级，这很重要，我已经连续在这个坑栽了两次（泪目）！如果不确定运算的优先级，一定要多用括号！

巴特西

leetcode 397

最新文章

热门文章