X

LEETCODE 476. Number Complement 解题思路分析

题目大意:

数字的补数

给定一个正整数,输出它的补数。补数是对该数的二进制表示取反。

示例 1:

输入: 5
输出: 2
解释: 5 的二进制表示为 101(没有前导零位),其补数为 010。所以你需要输出 2 。

示例 2:

输入: 1
输出: 0
解释: 1 的二进制表示为 1(没有前导零位),其补数为 0。所以你需要输出 0 。

注意:

给定的整数保证在 32 位带符号整数的范围内。
你可以假定二进制数不包含前导零位。
本题与 1009 https://leetcode.com/problems/complement-of-base-10-integer/ 相同


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=476

解题思路分析:

二进制数取反实际上就是将每一位上的数字从0变1,或者将1变0。比如题目给出的例子101,取反后是010。但是这里需要注意前导0的问题,比如010取反是101(十进制数5),不过如果我们去掉前导0,10取反就是01(十进制数1)。这里强调前导0的原因是,在java语言中,十进制数的二进制表现是默认带有前导0,比如数字5的二进制表现不是101,而是:

00000000 00000000 00000000 00000101

因此我们不能简单的使用取反运算(~)来解题。再回到本题,首先我们需要了解2个知识点:

1,如果取得十进制数的二进制表现的每一位上的数字

由于二进制数的每一位不是1就是0,因此我们可以采用当前数字与1进行并运算(&),如果结果是0,代表当前数字最低位是0,反之最低位是1。然后将当前数字向右位移一位(>>运算),继续采用同样的方法查看次低位。以此类推直到查看完所有位上的数字。

2,如何将二进制数转化为十进制

从二进制数的最后一位开始算,依次列为第0、1、2…位。第n位的数(0或1)乘以2的n次方 得到的结果相加就是答案。例如:01101011.转十进制:
第0位:1乘2的0次方=1
1乘2的1次方=2
0乘2的2次方=0
1乘2的3次方=8
0乘2的4次方=0
1乘2的5次方=32
1乘2的6次方=64
0乘2的7次方=0
然后:1+2+0 +8+0+32+64+0=107


解题时,我们首先从题目给定的数字num的二进制表现最低位开始向高位循环,如果当前位上的数字是0,说明它取反后会变成1,此时我们计算1乘2的n次方(n为当前位数),并将该结果累加至十进制的返回结果即可。

实现代码:

public int findComplement(int num) {
    int res=0; // 返回结果
    int index=0; // 当前位
    while(num>0){
        if((num&1)==0){ // 如果当前最低位是0,说明取反后是1
            // 计算1乘2的index次方,并累加至返回结果
            res+=(int)Math.pow(2,index);
        }
        index++; // 位加一
        num=num>>1; // num进一位
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Number Complement.

Memory Usage: 36.6 MB, less than 8.70% of Java online submissions for Number Complement.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-476-number-complement-解题思路分析/
Categories: leetcode
kwantong: