0397：整数替换（★）

2016-02-01 约 371 字预计阅读 1 分钟次阅读

力扣第 397 题

题目

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

分析

#1

最简单的就是直接递归。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def integerReplacement(self, n: int) -> int:
        @cache
        def dfs(n):
            if n==1:
                return 0
            if n%2==0:
                return 1+dfs(n//2)
            return 1+min(dfs(n+1),dfs(n-1))
        return dfs(n)

36 ms

#2

也可以用 bfs 遍历，与递归本质相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def integerReplacement(self, n: int) -> int:
        Q = deque([(0,n)])
        vis = {n}
        while Q:
            w,u =Q.popleft()
            if u==1:
                return w
            for v in [u-1,u+1] if u%2 else [u//2]:
                if v not in vis:
                    vis.add(v)
                    Q.append((w+1,v))

#3

还可以从二进制表示考虑
假如后两位是 01，减 1 更优
假如后两位是 11，加 1 更优（除了 3 的特殊情况）

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def integerReplacement(self, n: int) -> int:
        res = 0
        while n>1:
            if n&1==0:
                n >>= 1
            else:
                n += 1 if n&3==3<n else -1
            res += 1
        return res

37 ms

目录

0397：整数替换（★）

题目

分析

#1

#2

#3

解答