This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

Topic request

Idea 1: Traversal

Start the simulation directly as the problem tells you, going through each digit and comparing it with the previous digit.

Java

class Solution {
    public boolean hasAlternatingBits(int n) {
        int pre = -1;
        while(n ! =0) {
            int cur = n & 1; / / remove the bottom
            if((pre ^ cur) == 0) // Check whether it is the same as the previous bit
                return false;
            pre = cur;
            n >>= 1; / / moves to the right
        }
        return true; }}Copy the code

• Time complexity: Olog⁡n)O\log n)Ologn)
• Space complexity: O(1)O(1)O(1)

C++

Oh, it’s just like Java.

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int pre = - 1;
        while(n ! =0) {
            int cur = n & 1; / / remove the bottom
            if((pre ^ cur) == 0) // Check whether it is the same as the previous bit
                return false;
            pre = cur;
            n >>= 1; / / moves to the right
        }
        return true; }};Copy the code

• Time complexity: O(log⁡n)O(\log n)O(logn)
• Space complexity: O(1)O(1)O(1)

Idea two: alternating bits binary number properties

Applying the property of alternating binary numbers – if you shift it right, it will still be alternating binary numbers, and it will be different or different from the original number, resulting in consecutive numbers of 000 and consecutive numbers of 111 binary string, such as 00… 000111… 1100\000111 dots \ 1100 dots… 000111… 11, add the result to get a 00… 001000… 000 \ dots001000 \ dots000… 001000… The result of 0, if you put the two bits together you get 0 (because each bit is exactly different).

Java

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

• Time complexity: O(1)O(1)O(1)
• Space complexity: O(1)O(1)O(1)

C++

【 oh ~ it and Java or a little bit different, notice to use long, actually didn’t really understand the difference between them two int, probably is a problem of the sign bit?”

class Solution {
public:
    bool hasAlternatingBits(int n) {
        long x = n ^ (n >> 1); // If int will overflow
        return (x & (x + 1)) = =0; }};Copy the code

• Time complexity: O(1)O(1)O(1)
• Space complexity: O(1)O(1)O(1)

Idea 3: Opposite events

A one-line solution, however, which is convenient for Python and time complex, but interesting. 000, 111 appear alternately, that is to say, there will not be 000000, 111111 appear, that is, the concept of the opposite event, then scan to see if there is a matching substring.

Java

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

• Time complexity:
  $O(m * n)$.indexOfIs the product of the length of the original string and the length of the matching string
• Space complexity: O(1)O(1)O(1)

C++

I didn’t expect to get stuck here today. I looked up the binary container of c++ for a long time just to get python one line done.

class Solution {
public:
    bool hasAlternatingBits(int n) {
        bitset<32> bit(n); // Convert to binary
        string str =  bit.to_string(a);// get rid of the extra 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; }};Copy the code

• Time complexity: O(m∗n)O(m * n)O(m∗n)
• Space complexity: O(n)O(n)O(n)

bitset

• Study References
• Introduction to the
  • Composed of a number of bits, easy to modify a middle one.
  • Initialize thebitset<N> bit(num).
    $N$The container size is an integer constant,
    $num$It can be a decimal number or a string of 01.

Python

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

• Time complexity: O(m∗n)O(m * n)O(m∗n)
• Space complexity: O(1)O(1)O(1)

conclusion

It’s a simple question, but it goes a long way. Method two is a delicate and efficient method to calculate by using the characteristics of alternating binary numbers. Method three… It’s neat to think of opposing events, but C++ writing brings out a lot of extra content.