跳转至

LeetCode: 397. 整数替换

1、题目描述

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

  1. 如果 n 是偶数,则用 n / 2替换 n
  2. 如果 n 是奇数,则可以用 n + 1n - 1替换 n

n 变为 1 所需的最小替换次数是多少?

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1

示例 2:

输入:
7

输出:
4

解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1

2、解题思路

​ 虽然这道题难度被标注为M,实际上只要找到规律,是很简单的。

​ 首先,我们来分析一下题意,题目的要求就是将一个数进行不断地变换,最后变成1,如果从位的角度来看,我们将题目要求变换一下:

​ 给定一个正整数n,可以进行如下变化:

  1. 如果n的最低位是0,n右移1位
  2. 如果n的最低位不是0,加1或减一,变成0以后右移
  3. 最终结果是仅留下最左面的一个1为止

​ 根据上面的描述,我们就很容易找到解题思路了,我们判断最左面的1所在的位置,然后判断这个1右面有多少个1是需要消除的

​ 不过,在这里,有一个需要注意的就是,那就是如果一个数字,二进制位有多个1相连,于是,我们这时候进行加1操作,会同时消去多个1,减少后面的操作数

​ 如果仅仅有两个1,那么加一操作和减一操作带来的损耗是相同的

  • 加一减少了2次数字变化,增加了1位,最终变化是减少1

  • 减一则是最终变化减少1

因此,解题的时候

  • 如果当前位是0,那么直接右移,结果加一
  • 如果当前位是1,这时候,判断下一位
  • 下一位是0,结果直接加2,然后右移一位
  • 下一位是1,数字加一,结果加2,然后右移一位
  • 边界条件:
  • 当n减小到3的时候,是特殊情况,减一而不是加一
class Solution:
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 0
        res = 0
        while n > 1:
            if n == 3:
                res += 2
                break
            if n & 1 == 0:
                res += 1
                n >>= 1
            else:
                if 2 & n != 0:
                    n += 1
                    n >>= 1
                else:
                    n >>= 1
                res += 2
        return res

​ 需要注意边界,就是3,当n被减小到3的时候,仅仅需要2次就可以,而不需要考虑加一