原文链接: https://leetcode-cn.com/problems/closed-number-lcci

英文原文

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

Example1:

 Input: num = 2 (0b10)
 Output: [4, 1] ([0b100, 0b1])

Example2:

 Input: num = 1
 Output: [2, -1]

Note:

1. 1 <= num <= 2147483647
2. If there is no next smallest or next largest number, output -1.

中文题目

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

示例1:

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

示例2:

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

提示:

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

通过代码

高赞题解

解题思路

比 num 大的数：从右往左，找到第一个 01 位置，然后把 01 转为 10，右侧剩下的 1 移到右侧的低位，右侧剩下的位清0。
比 num 小的数：从右往左，找到第一个 10 位置，然后把 10 转为 01，右侧剩下的 1 移到右侧的高位，右侧剩下的位置0。

常规上，低位在右侧，bitset 注意方向相反

代码

class Solution {
   public:
    vector<int> findClosedNumbers(int num) {
        bitset<32> small(num);
        bitset<32> bigger(num);

        int s = -1;
        // small, 10 转 01，1移到左侧
        for (int i = 1; i < 32; i++) {
            if (small[i] == 1 && small[i - 1] == 0) {
                small.flip(i);
                small.flip(i - 1);
                for (int left = 0, right = i - 2; left < right;) {
                    while (left < right && small[left] == 0) left++;
                    while (left < right && small[right] == 1) right--;
                    small.flip(left);
                    small.flip(right);
                }
                s = (int)small.to_ulong();
                break;
            }
        }

        // bigger, 01转10，1移到最右侧
        int b = -1;
        for (int i = 1; i < 32; i++) {
            if (bigger[i] == 0 && bigger[i - 1] == 1) {
                bigger.flip(i);
                bigger.flip(i - 1);

                for (int left = 0, right = i - 2; left < right;) {
                    while (left < right && bigger[left] == 1) left++;
                    while (left < right && bigger[right] == 0) right--;
                    bigger.flip(left);
                    bigger.flip(right);
                }
                b = (int)bigger.to_ulong();
                break;
            }
        }

        return {b, s};
    }
};

统计信息

通过次数	提交次数	AC比率
5615	14717	38.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言