LC 1009.Complement of Base 10 Integer

题目描述

这是 LeetCode 上的 1009. 十进制整数的反码 - 力扣（LeetCode） ，难度为简单。

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

提示：

1. 0 <= N < 10^9
2. 本题与 476：https://leetcode-cn.com/problems/number-complement/ 相同

解答

方法一：使用库函数

使用 Integer.toBinaryString() 将十进制转化为二进制，然后逐位修改二进制位得到最终的结果。

class Solution {
    public int bitwiseComplement(int n) {
        char[] arr = Integer.toBinaryString(n).toCharArray();
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = (arr[i] == '0') ? '1' : '0';
        }
        String ans = new String(arr);
        return Integer.parseInt(ans, 2);
    }
}

• 时间复杂度：\(O(N)\)，其中 N 为数字 n 的二进制表示的长度。

• 空间复杂度：\(O(N)\)， N 的含义同上。

方法二：模拟

只需要构造一个和 n 的二进制位数相同的掩码即可。

class Solution {
    public int bitwiseComplement(int n) {
        int mask = 1;
        while (mask < n) {
            mask = (mask << 1) + 1;
        }
        return n ^ mask;
    }
}

• 时间复杂度：\(O(\log n)\)，其中 n 为题目所给的 n 。
• 空间复杂度：\(O(1)\)。

每题一图