1.题目基本信息

1.1.题目描述

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

1. 如果 n 是偶数，则用 n / 2替换 n 。

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

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

1.2.题目地址

https://leetcode.cn/problems/integer-replacement/description/

2.解题方法

2.1.解题思路

递归 / 贪心

3.解题代码

python代码

class Solution:
    def integerReplacement(self, n: int) -> int:
        # 思路：贪心。对于n为奇数的情况，优先转到(n+1)//2和(n-1)//2中为偶数的情况（除3外）
        result = 0
        while n > 1:
            if n & 1 == 0:
                n = n // 2
                result += 1
            else:
                if n == 3:
                    n = 1
                    result += 2
                else:
                    if ((n - 1) // 2) & 1 == 0:
                        n = (n - 1) // 2
                    else:
                        n = (n + 1) // 2
                    result += 2
        return result

    @cache
    def integerReplacement1(self, n: int) -> int:
        # 思路1：递归
        if n == 1:
            return 0
        if n & 1 == 0:
            return self.integerReplacement(n // 2) + 1
        else:
            return 2 + min(self.integerReplacement((n - 1) // 2), self.integerReplacement((n + 1) // 2))

c++代码

class Solution {
private:
    map<int, int> mem;
public:
    int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (mem.find(n) != mem.end()) {
            return mem[n];
        }
        int result;
        if (n % 2 == 0) {
            result = integerReplacement(n / 2) + 1;
        } else {
            result = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
        }
        mem[n] = result;
        return result;
    }
};

4.执行结果