LeetCode.1009-十进制数的补码(Complement

作者: 程序员小川 | 来源:发表于2019-07-08 21:35 被阅读6次

    这是小川的第377次更新,第404篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第238题(顺位题号是1009)。每个非负整数N都具有二进制表示。例如,5可以二进制表示为"101",11可以二进制表示为"1011",依此类推。

    请注意,除N = 0外,任何二进制表示中都没有前导零。

    二进制表示的补码是将1改为0和将0改为1时得到的二进制数。例如,二进制中"101"的补码是二进制的"010"

    对于给定的十进制数N,将其二进制表示的补码作为十进制的整数返回。

    例如:

    输入:5
    输出:2
    说明:5是二进制"101",二进制补码"010",转为十进制是2。

    输入:7
    输出:0
    说明:7是二进制"111",二进制补码"000",转为十进制是0。

    输入:10
    输出:5
    说明:10是二进制"1010",二进制补码"0101",转为十进制是5。

    注意

    • 0 <= N < 10^9

    02 第一种解法

    题目的意思是将N转为二进制,再求其二进制的补码(0和1互换),再将转换后的二进制补码转为十进制整数。

    思路:利用异或位运算,例如5^7=2,那么我们要找到7,而7的二进制为111,长度和5的二进制101相等,但是全为1,所以先将5转为二进制字符串,使用一个32位长度的由1组成的字符串,截取对应长度的子串,再将截取出来的子串转为十进制数,利用得到的十进制数和N异或运算就可得到结果。

    public int bitwiseComplement(int N) {
        String str = Integer.toBinaryString(N);
        String newStr = "11111111111111111111111111111111";
        newStr = newStr.substring(0, str.length());
        int num = Integer.valueOf(newStr, 2);
        return N^num;
    }
    

    03 第二种解法

    思路:将N转为二进制字符串,利用循环,将其中的0转为1,1转为0,变成新的二进制字符串,再将其转为十进制整数。

    public int bitwiseComplement2(int N) {
        String str = Integer.toBinaryString(N);
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<str.length(); i++) {
            sb.append(str.charAt(i) == '0' ? '1' : '0');
        }
        return Integer.valueOf(sb.toString(), 2);
    }
    

    04 第三种解法

    思路和第一种解法类似,只是换了另外的方式来得到全是1的二进制数,全是1的二进制数可以通过1开头后面跟0的二进制数减1得到,例如8的二进制数1000,8减去1得到7,7的二进制数是111,而8可以通过1左移位运算3得到(也可以累乘2三次得到)。

    public int bitwiseComplement3(int N) {
        if (N < 2) {
            return N == 0 ? 1 : 0;
        }
        int num = 1;
        while (num <= N) {
            // 换成 num *= 2; 效果一样
            num <<= 1;
        }
        return N^(num-1);
    }
    

    05 小结

    算法专题目前已连续日更超过七个月,算法题文章244+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,好看、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode.1009-十进制数的补码(Complement

        本文链接:https://www.haomeiwen.com/subject/hxrzhctx.html