LeetCode 476 数字的补数

LeetCode 476 数字的补数,第1张

LeetCode 476 数字的补数 LeetCode 476 数字的补数

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-complement/

博主Github:https://github.com/GDUT-Rp/LeetCode

题目:

整数的二进制表示取反(0 变 1 ,1 变 0)后,再转换为十进制表示,可以得到这个整数的补数。

例如,整数 5 的二进制表示是 “101” ,取反后得到 “010” ,再转回十进制表示得到补数 2 。
给你一个整数 num ,输出它的补数。

示例 1:

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

示例 2:

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

提示:

1 <= num < 2 31 2^{31} 231

解题思路: 方法一:找二进制规律然后相减 直观想法

原数字num + 其补数 + 1 = 2 n 2^n 2n (刚好比起>=的一个数)

C++
 
Golang 
func findComplement(num int) int {
    two_pow := 1
    for i:=0; i<=32; i++ {
        if two_pow - 1 >= num {
            return two_pow - num - 1
        } 
        two_pow = two_pow << 1
    }
    return 0
}
Python
class Solution:
    def __init__(self):
        self.two_pows = [2 ** i - 1 for i in range(32)]

    def findComplement(self, num: int) -> int:
        for elem in self.two_pows:
            if elem >= num:
                return elem - num

复杂度分析

时间复杂度: O ( n ) O(n) O(n)

方法二:异或运算符

找到最大的 2 n 2^n 2n,然后进行异或运算符运算即可以取补数。

C++
class Solution {
public:
    int findComplement(int num) {
        int temp = num, c = 0;
        while (temp > 0) {
            temp >>= 1;
            c = (c << 1) + 1;
        }
        return num ^ c;
    }
};
Go
func findComplement(num int) int {
    temp := num
    c := 0
    for temp > 0 {
        temp >>= 1
        c = (c << 1) + 1
    }
    return num ^ c
}
Python
class Solution:
    def findComplement(self, num: int) -> int:
        temp = num
        c = 0
        while temp > 0:
            temp >>= 1
            c = (c << 1) + 1
        return num ^ c

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/3973784.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表(0条)

保存