首页 > 代码库 > leetcode_397

leetcode_397

2024-08-14 20:49:50   213人阅读

题目描述：

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:8Output:3Explanation:8 -> 4 -> 2 -> 1

 

Example 2:

Input:7Output:4Explanation:7 -> 8 -> 4 -> 2 -> 1or7 -> 6 -> 3 -> 2 -> 1

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

解法一：递归方式
int integerReplacement(int n){    if(n == INT_MAX)        return 32;    if(n <= 1)        return 0;    if((n & 1) == 0)        return 1 + integerReplacement(n / 2);    else        return 1 + min(integerReplacement(n - 1), integerReplacement(n + 1));}

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

 

解法二：

int integerReplacement(int n){    if (n == INT32_MAX)        return 32;    int counter = 0;    while (n != 1)    {        if ((n & 1) == 0)        {            ++ counter;            n = (n >> 1);        }        else        {            if (n == 3)                n = 2;            else            {                if (containBinaryZeros(n - 1) > containBinaryZeros(n + 1))                    -- n;                else                    ++ n;            }            ++counter;        }    }    return counter;    }int containBinaryZeros(int n){    int counter = 0;    while ((n & 1) == 0)    {        ++counter;        n = n >> 1;    }    return counter;}

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

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



leetcode_397


联系
我们