面试题 05.04. 下一个数

下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

示例1:

输入：num = 2（或者0b10）
输出：[4, 1] 或者（[0b100, 0b1]）

示例2:

输入：num = 1
输出：[2, -1]

提示:

• num的范围在[1, 2147483647]之间；
• 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

Python 解答：
1.暴力

class Solution:
    def findClosedNumbers(self, num: int) -> List[int]:
        if num == 1:
            return [2, -1]
        if num == 2147483647:
            return [-1, -1]
        a, b = num-1, num+1
        count = bin(num).count('1')
        while bin(a).count('1') != count:
            a -= 1

        while bin(b).count('1') != count:
            b += 1
        return [b, a]

2.寻找1位

class Solution:
    def findClosedNumbers(self, num: int) -> List[int]:
        if num == 1:
            return [2, -1]
        if num == 2147483647:
            return [-1, -1]
        def transform(num):
            res = []
            while num > 0:
                r = num&1
                res.append(r)
                num >>= 1
            res.append(0)
            return res
        def retransform(arr):
            num = 0
            for item in arr:
                num <<= 1
                num += item
            return num

        res = transform(num)
        temp1 = res[::]
        temp2 = res[::]
        i = 0
        while i < len(temp1):
            if temp1[i] == 0 and temp1[i+1] == 1:
                temp1[i], temp1[i+1] = temp1[i+1], temp1[i]
                j = i - 1
                k = i - 1
                while k >= 0:
                    if temp1[k] == 1:
                        temp1[j] = 1
                        j -= 1
                    k -= 1
                while j >= 0:
                    temp1[j] = 0
                    j -= 1
                break
            i += 1

        i = 0
        while i < len(temp2):
            if temp2[i] == 1 and temp2[i+1] == 0:
                temp2[i], temp2[i+1] = temp2[i+1], temp2[i]
                j = 0
                k = 0
                while k <= i-1:
                    if temp2[k] == 1:
                        temp2[j] = 1
                        j += 1
                    k += 1
                while j <= i-1:
                    temp2[j] = 0
                    j += 1    
                break 
            i += 1
        return [retransform(temp2[::-1]), retransform(temp1[::-1])]