LeetCode 397. 整数替换

Categories:

题目描述
思路分析
1. 解法一：贪心 + 位运算（推荐）
相似题目

题目描述

✅ 397. 整数替换

思路分析

解法一：贪心 + 位运算（推荐）

核心思路：

偶数直接除以 2，步数最优。

奇数时，若 n == 3 或 n % 4 == 1，选择 n - 1；否则选择 n + 1。

该策略让二进制末尾尽快出现更多 0，从而减少除 2 的次数。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示输入数值。

空间复杂度：O(1)。

class Solution {
    public int integerReplacement(int n) {
        long x = n;
        int steps = 0;

        while (x > 1) {
            if ((x & 1) == 0) {
                x >>= 1;
            } else {
                if (x == 3 || (x & 3) == 1) {
                    x--;
                } else {
                    x++;
                }
            }
            steps++;
        }

        return steps;
    }
}

func integerReplacement(n int) int {
	x := int64(n)
	steps := 0

	for x > 1 {
		if x&1 == 0 {
			x >>= 1
		} else {
			if x == 3 || x&3 == 1 {
				x--
			} else {
				x++
			}
		}
		steps++
	}

	return steps
}

相似题目

题目	难度	考察点
231. 2 的幂	简单	位运算
342. 4的幂	简单	位运算
476. 数字的补数	简单	位运算
190. 颠倒二进制位	简单	位运算
395. 至少有 K 个重复字符的最长子串	中等	递归/分治

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/99030167