Java&C++题解与拓展——leetcode693.交替位二进制数【bitset学习与使用】

题目要求思路一：遍历

JavaC++ 思路二：交替位二进制数性质

JavaC++ 思路三：对立事件

JavaC++

bitset Python 总结

直接按照题目要求开始模拟，遍历每一位并与上一位比较。

class Solution {
    public boolean hasAlternatingBits(int n) {
        int pre = -1;
        while(n != 0) {
            int cur = n & 1; //取末位
            if((pre ^ cur) == 0) //是否与上一位相同
                return false;
            pre = cur;
            n >>= 1; // 右移
        }
        return true;
    }
}

时间复杂度： O log ⁡ n ) Olog n) Ologn)空间复杂度： O ( 1 ) O(1) O(1) C++

【哦~它和java简直可以嗦一模一样呢】

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int pre = -1;
        while(n != 0) {
            int cur = n & 1; //取末位
            if((pre ^ cur) == 0) //是否与上一位相同
                return false;
            pre = cur;
            n >>= 1; // 右移
        }
        return true;
    }
};

时间复杂度： O ( log ⁡ n ) O(log n) O(logn)空间复杂度： O ( 1 ) O(1) O(1) 思路二：交替位二进制数性质

应用一下交替位二进制数的性质——右移后仍是交替位二进制数，且与原数异或会得到连续的数个 0 0 0和连续的数个 1 1 1组成的二进制串，形如 00 … 000111 … 11 00dots 000111dots 11 00…000111…11，对这个结果加一会进位得到一个 00 … 001000 … 0 00dots001000dots0 00…001000…0的结果，将二者按位与会得到0（因为恰好每一位都不相同）。

class Solution {
    public boolean hasAlternatingBits(int n) {
        int x = n ^ (n >> 1);
        return (x & (x + 1)) == 0;
    }
}

时间复杂度： O ( 1 ) O(1) O(1)空间复杂度： O ( 1 ) O(1) O(1) C++

【哦~它和java还是有一点不一样的，注意一下要用long，其实没太懂它们两个int的区别，大概是符号位的问题？】

class Solution {
public:
    bool hasAlternatingBits(int n) {
        long x = n ^ (n >> 1); //如果int会overflow
        return (x & (x + 1)) == 0;
    }
};

时间复杂度： O ( 1 ) O(1) O(1)空间复杂度： O ( 1 ) O(1) O(1) 思路三：对立事件

一个用一行代码解决的思路，然而只是对于Python比较方便，时间复杂度也挺高的，但是思路很有趣。
0 0 0、 1 1 1交替出现，也就是说不会有 00 00 00、 11 11 11出现，也就是对立事件的概念，那么就去扫描是否有匹配的子串。

class Solution {
    public boolean hasAlternatingBits(int n) {
        return Integer.toBinaryString(n).indexOf("00") == -1 && Integer.toBinaryString(n).indexOf("11") == -1;
    }
}

时间复杂度： O ( m ∗ n ) O(m * n) O(m∗n)，indexOf的复杂度，即原字符串长度和匹配字符串长度之积空间复杂度： O ( 1 ) O(1) O(1) C++

没想到今天题目卡在这儿了，就为了python一行搞定，查了半天c++的二进制容器。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        bitset<32> bit(n); //转为二进制
        string str =  bit.to_string();
        //去除前面多余的0
        int i = 0;
        while(i < str.length() && str[i] == '0')
            i++;
        str = str.erase(0, i);
        
        return str.find("00") == -1 && str.find("11") == -1;
    }
};

时间复杂度： O ( m ∗ n ) O(m * n) O(m∗n)空间复杂度： O ( n ) O(n) O(n) bitset

学习参考资料简介

由若干个位构成，易于修改中间的某一位。初始化bitset bit(num)， N N N表示容器大小是一个整型常数， n u m num num可以是一个十进制数，也可以是01字符串。 Python

class Solution(object):
    def hasAlternatingBits(self, n):
        return all(p not in bin(n) for p in ('00', '11'))

时间复杂度： O ( m ∗ n ) O(m * n) O(m∗n)空间复杂度： O ( 1 ) O(1) O(1) 总结

题目很简单，但能延伸出很多内容。
法二想到利用交替位二进制数自身的特性进行计算，是一种精巧高效的方法。
法三……能想到对立事件很巧妙，但是C++写就额外引出了很多内容。