每日OJ题_贪心算法四④_力扣397. 整数替换

目录

力扣397. 整数替换

解析代码

力扣397. 整数替换

397. 整数替换

难度 中等

给定一个正整数 n ，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n 。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。

返回 n 变为 1 所需的 最小替换次数 。

示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

示例 2：

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

输入：n = 4
输出：2

提示：

• 1 <= n <= 2^31 - 1

class Solution {
public:
    int integerReplacement(int n) {

    }
};

解析代码1_递归改记忆化搜索

        此题的贪心策略很难想出来，先看看记忆化搜索的方法（记忆化搜索在之前专题已经学过）：用爆搜模拟也可以过，但是加上备忘录优化：

class Solution {
    unordered_map<int, int> memo;
public:
    int integerReplacement(int n) {
        // 时间O(logN) 空间O(logN)
        return dfs(n);
    }

    int dfs(long long n)
    {
        if(n == 1)
            return 0;

        if(memo[n] != 0)
            return memo[n];
        
        if(n % 2 == 0)
        {
            memo[n] = 1 + dfs(n / 2);
            return memo[n];
        }
        else
        {
            memo[n] = 1 + min(dfs(n - 1), dfs(n + 1));
            return memo[n];
        }
    }
};

解析代码2_贪心策略

贪心策略：任何选择都应该让这个数尽可能快的变成 1 。

• 对于偶数：只执行除 2 操作。
• 对于奇数：

1. 当 n== 1 的时候，不用执行任何操作。
2. 当 n == 3 的时候，变成 1 的最优操作数是 2 。
3. 当 n > 1 && n % 4 == 1的时候，那么它的二进制表示是 ......01 ，最优的方式应该选择 -1 ，这样就可以把末尾的 1 干掉，接下来执行除法操作，能够更快地变成1 。
4. 当 n > 3 && n % 4 == 3的时候，那么它的二进制表示是 ......11 ，最优的方式应该选择 +1 ，这样可以把一堆连续的 1 转换成 0 ，更快地变成 1 。

class Solution {
public:
    int integerReplacement(int n){
        // 时间O(logN) 空间O(1)
        int ret = 0;
        while(n != 1)
        {
            if(n % 2 == 0)
            {
                n =  n / 2;
                ++ret;
            }
            else
            {
                ret += 2; // 下面操作都是两步
                if(n == 3)
                    break;
                else if(n % 4 == 1) // ......01
                    n /= 2; // 和减1除2结果一样
                else // ......01
                    n = n / 2 + 1; // 和加1除2结果一样，防溢出
            }
        }
        return ret;
    }
};