> 文档中心 > LeetCode_交替位二级制数

LeetCode_交替位二级制数


LeetCode_交替位二级制数

业精于勤,荒于嬉;行成于思,毁于随。——韩愈


正题:


题目:

给定一个正整数,检查它的二进制表示是否总是 0、1 交替出现:换句话来说,就是二级制表示中相邻两位的数字永不相同。

示例

示例 1:
输入:n = 5
输出:true
解释:5 的二进制表示是:101

示例 2:
输入:n = 7
输出:false
解释:7 的二进制表示是:111

示例 3:
输入:n = 11
输出:false
解释:11 的二进制表示是:1011

提示:

1 <= n <= 2^31 - 1


这道题有两种方法来实现:

方法一:模拟

思路:

这个方法的核心就是十进制转化为二级制,从最低位到最高位,我们使用对2取模再除以2的方法,依次求出输入的二级制表示的每一位,并对前一位进行比较。如果相同,则不符合条件;如果每次比较都不相同,则符合条件。
代码如下(示例):

public boolean hasAlternatingBits1(int n) { int prev = 2; while (n != 0){     int cur = n % 2;     if(cur == prev){  return false;     }     prev = cur;     n /= 2; } return true;    }

复杂度分析:

  • 时间复杂度:O(log n)。输入n的二级制表示最多有O(log n)位;
  • 空间复杂度:O(1)。使用了常数空间来存储中间变量。

方法二:位运算

思路:

根据位运算中右移和按位异或的性质,我们先对输入n的二级制表示右移一位后,然后将得到的数字再与n按位异或得到a。当且仅当输入n为交替位二级制数时,a的二级制表示全为1(注意:并不包括前导0)。这里进行简单证明:当a的某一位为1时,当且仅当n的对应位和其前一位相异。当a的每一位为1时,当且仅当n的所有相邻位相异,即n为交替位二级制数。
根据位运算中按位与的性质,我们将a与a + 1按位与,当且仅当a的二级制表示全为1时,结果为0。这里进行简单证明:当且仅当a的二级制表示全为1时,a + 1可以进位,并将原最高位置为0,按位与的结果为0。否则吗,不会产生进位,两个最高位都为1,相与结果不为0。
结合上述两步,可以判断输入是否为交替位二级制数。

代码如下(示例):

public boolean hasAlternatingBits2(int n) {    int a = n ^ (n >> 1);    return (a & (a + 1)) == 0;}

复杂度分析:

  • 时间复杂度:O(1)。仅使用了常数空间来计算;
  • 空间复杂度:O(1)。使用了常数空间来存储中间变量。

小结

这道题主要考查的是位运算和进制转换的使用,其难度是没有太大的。