0397. 整数替换【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 位运算

1. 📝 题目描述

• leetcode

给定一个正整数 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

2. 🎯 s.1 - 贪心 + 位运算

c

int integerReplacement(int n) {
    int count = 0;
    long long num = n;
    while (num != 1) {
        if (num % 2 == 0) {
            num /= 2;
        } else if (num == 3 || (num & 2) == 0) {
            num--;
        } else {
            num++;
        }
        count++;
    }
    return count;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var integerReplacement = function (n) {
  let count = 0
  while (n !== 1) {
    if (n % 2 === 0) {
      n = Math.floor(n / 2)
    } else if (n === 3 || (n & 2) === 0) {
      n--
    } else {
      n++
    }
    count++
  }
  return count
}

py

class Solution:
    def integerReplacement(self, n: int) -> int:
        count = 0
        while n != 1:
            if n % 2 == 0:
                n //= 2
            elif n == 3 or (n & 2) == 0:
                n -= 1
            else:
                n += 1
            count += 1
        return count

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$

算法思路：

• 偶数直接除 2
• 奇数时，若倒数第二位为 1（即 n & 2 != 0）则 +1（可产生更多尾部 0），否则 -1
• 特例：$n=3$ 时 -1 更优