下一个数

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

示例1:

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

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

num的范围在[1, 2147483647]之间；
如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
通过次数3,168提交次数6,994

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/closed-number-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int[] findClosedNumbers(int num) {

        if (num == 0) return new int[]{-1, -1};
        int[] n = new int[32];
        int flag = 1;

        for (int i = 0; i < 32; i++) {
            if ((flag & num) != 0) {
                n[31 - i] = 1;
            }
            flag <<= 1;
        }

        int[] n1 = new int[32];
        int[] n2 = new int[32];

        int index = 0;
        for (int i = 0; i < 32; i++) {
            n1[i] = n[i];
            n2[i] = n[i];
            if (n[i] == 1) {
                index = i;
            }
        }


        boolean flag1 = false;
        boolean flag2 = false;
        int[] res = new int[]{-1, -1};
        for (int i = index + 1; i < 32; i++) {
            if (n1[i] == 0) {
                n1[i] = 1;
                n1[index] = 0;
                flag1 = true;
                break;
            }
        }

        if (flag1 == false) {
            for (int i = index - 1; i >= 0; i--) {
                if (n1[i] == 1) {
                    for (int j = i + 1; j < 32; j++) {
                        if (n1[j] == 0) {
                            n1[j] = 1;
                            n1[i] = 0;
                            flag1 = true;
                            //右边的1，替换到左边
                            int left = j + 1, right = 31;
                            while (left < right) {
                                if (n1[left] == 0 && n1[right] == 1) {
                                    n1[left] = n1[left] ^ n1[right];
                                    n1[right] = n1[left] ^ n1[right];
                                    n1[left] = n1[left] ^ n1[right];
                                }

                                left++;
                                right--;
                            }
                            break;
                        }
                    }
                }
                if (flag1) break;
            }
        }
        
        for (int i = index - 1; i >= 0; i--) {
            if (n2[i] == 0) {
                n2[i] = 1;
                n2[index] = 0;
                flag2 = true;
                int left = i + 1, right = 31;
                while (left < right) {
                    if (n2[left] == 1 && n2[right] == 0) {
                        n2[left] = n2[left] ^ n2[right];
                        n2[right] = n2[left] ^ n2[right];
                        n2[left] = n2[left] ^ n2[right];
                    }

                    left++;
                    right--;
                }

                break;
            }
        }

        if (flag1) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < 32; i++) {
                bd.append(n1[i]);
            }

            res[1] = Integer.valueOf(bd.toString(), 2);
        }

        if (flag2) {
            StringBuilder bd = new StringBuilder();
            for (int i = 0; i < 32; i++) {
                bd.append(n2[i]);
            }

            res[0] = Integer.valueOf(bd.toString(), 2);
        }

        return res;
    }
}

赏

谢谢你请我吃糖果

微信