LeetCode算法题-Binary Number with Alternating Bits（Java实现）

Dear 丶 2022-01-07 11:57 161阅读 0赞

这是悦乐书的第**292**次更新，第**310**篇原创

### 01 看题和准备 ###

今天介绍的是LeetCode算法题中Easy级别的第160题（顺位题号是693）。给定正整数，检查它是否具有交替位：即它的二进制数的任意两个相邻位总是具有不同的值。例如：  
  
  
输入：5

输出：true

说明：5的二进制表示是：101  
  
  
输入：7

输出：false

说明：7的二进制表示为：111。  
  
  
输入：11

输出：false

说明：11的二进制表示是：1011。  
  
  
输入：10

输出：true

说明：10的二进制表示是：1010。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

### 02 第一种解法 ###

最直接解法，将正整数转为二进制字符串，借助包装类Integer的toBinaryString方法实现，然后对字符串的字符进行遍历，如果相邻的字符相等了，直接返回false。

public boolean hasAlternatingBits(int n) {
        String str = Integer.toBinaryString(n);
        for (int i=1; i<str.length(); i++) {
            if (str.charAt(i) == str.charAt(i-1)) {
                return false;
            }
        }
        return true;
    }

### 03 第二种解法 ###

我们也可以观察下为true的那些数，从1开始：

1，其二进制数为：1

2，其二进制数为：10

5，其二进制数为：101

10，其二进制数为：1010

通过观察这些二进制数，我们可以发现，它们可以看做是10和1的组合体。对于10，可以有零个，也可以有多个，而对于1，只可能是0个或者1个，多了就重复了。因此，我们也可以使用正则表达式来解。

匹配多字符10，使用圆括号；匹配0次或者多次，使用星号，或者\{0,\}。

匹配1，可以直接写1，匹配0次或者1次，使用问号，或者\{0,1\}。

public boolean hasAlternatingBits(int n) {
        String str = Integer.toBinaryString(n);
        //(10){0,}1{0,1} 这样写也是可以的    
        return str.matches("(10)*1?");
    }

### 04 第三种解法 ###

我们也可以不将其转为二进制字符串，直接使用位运算来判断，借助与(&)运算。与运算的规则是对应位都为1才为1，否则对应位为0。每次将n和1进行与运算，看它最后一位是0还是1，使用一个临时变量，将其二进制数的最后一位记录下来，与当前的最后一位比较，如果相同了，就返回false。

public boolean hasAlternatingBits(int n) {
        // 记录每次操作的最后一位    
        int prev = -1;
        while (n > 0) {
            if ((n&1) == 1) {
                if (prev == 1) {
                    return false;
                }
                prev = 1;
            } else {
                if (prev == 0) {
                    return false;
                }
                prev = 0;
            }
            // 每次将其右移一位
            n >>= 1;
        }
        return true;
    }

### 05 第四种解法 ###

对于第三种解法，我们还可以再简化下。上面我们每进行一次计算都会去判断一下，是否等于上一次计算的最后一位，这里我们将其移动到while循环的判断条件中去，反过来处理，先得到下一次正确的最后一位，看其符不符合。依旧使用一个临时变量，循环继续的条件变成了当前最后一位是否等于预先设定好的那个数，在循环内部，我们对temp变量进行变动，取每次计算的相反值，如果计算为0，那么temp就为1，表示下一次参与计算后的最后一位要为1，否则就去判断n是否已经等于0了。

public boolean hasAlternatingBits(int n) {
        int temp = n&1;
        while ((n&1) == temp) {
            temp = 1-temp;
            n >>= 1;
        }
        return n == 0;
    }

### 06 第五种解法 ###

此解法利用了n的二进制数0与1交替的特征，与自身右移一位后的数进行错位相加，变成了一个全部由1组成的二进制数，然后再利用检测是否全为1的方法，判断是否符合题意。而检测的方法就是，加1后和自身进行与运算，因为如果该二进制数全为1，加1后就转为了首位为1，其余位都是0的二进制数，再与原来的自己进行与运算，运算的结果就是0。比如5，5+5/2变成了7，二进制数为111，加1后，其二进制数变为了1000，两者进行与运算后，得到的结果是0。除以2和右移一位的效果等同。

public boolean hasAlternatingBits(int n) {
        // ((n + (n >> 1) + 1) & (n + (n >> 1))) == 0 这样写也行    
        return ((n+n/2+1) & (n+n/2)) == 0;
    }

### 07 小结 ###

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

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

转载于:https://www.cnblogs.com/xiaochuan94/p/10625383.html