Medium

题目描述

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

  • 如果 n 是偶数，则用 n / 2替换 n 。
  • 如果 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

解题思路

这道题有多种解法，包括记忆化搜索、动态规划和贪心策略。

基本思路：

  • 对于偶数，只能选择除以2
  • 对于奇数，可以选择加1或减1，需要找到最优策略

贪心策略（推荐）： 通过位运算观察规律，当n为奇数时：

  • 如果n的二进制表示末尾是01（即n % 4 == 1），选择n-1更优
  • 如果n的二进制表示末尾是11（即n % 4 == 3），选择n+1更优
  • 特殊情况：n = 3时，选择n-1更优

这是因为：

  • n-1会消除一个1位，然后可以直接右移
  • n+1可能会产生进位，消除多个1位

记忆化搜索： 使用递归 + 备忘录，避免重复计算。对于奇数递归计算min(f(n+1), f(n-1)) + 1。

复杂度分析： 贪心解法时间复杂度O(log n)，空间复杂度O(1)，是最优解法。

代码实现

class Solution {
public:
    int integerReplacement(int n) {
        int count = 0;
        long long num = n;  // 使用long long避免溢出
        
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                // 奇数情况：贪心策略
                if (num == 3 || num % 4 == 1) {
                    num--;
                } else {
                    num++;
                }
            }
            count++;
        }
        
        return count;
    }
};

class Solution:
    def integerReplacement(self, n: int) -> int:
        count = 0
        
        while n != 1:
            if n % 2 == 0:
                n //= 2
            else:
                # 奇数情况：贪心策略
                if n == 3 or n % 4 == 1:
                    n -= 1
                else:
                    n += 1
            count += 1
            
        return count

public class Solution {
    public int IntegerReplacement(int n) {
        int count = 0;
        long num = n;  // 使用long避免溢出
        
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                // 奇数情况：贪心策略
                if (num == 3 || num % 4 == 1) {
                    num--;
                } else {
                    num++;
                }
            }
            count++;
        }
        
        return count;
    }
}

var integerReplacement = function(n) {
    let count = 0;
    
    while (n !== 1) {
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            if (n === 3 || ((n - 1) / 2) % 2 === 0) {
                n = n - 1;
            } else {
                n = n + 1;
            }
        }
        count++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
贪心策略O(log n)O(1)
记忆化搜索O(log n)O(log n)

说明：

  • 贪心策略是最优解法，每次操作都能有效减少数字的位数
  • 时间复杂度O(log n)是因为每次操作至少减少一个二进制位
  • 空间复杂度O(1)，只使用常数额外空间