[leetcode] Binary Number with Alternating Bits
发布时间:2020-12-14 03:21:37 所属栏目:大数据 来源:网络整理
导读:Given a positive integer,check whether it has alternating bits: namely,if two adjacent bits will always have different values. Example 1: Input: 5Output: TrueExplanation:The binary representation of 5 is: 101 ? Example 2: Input: 7Output: F
Given a positive integer,check whether it has alternating bits: namely,if two adjacent bits will always have different values. Example 1: Input: 5 Output: True Explanation: The binary representation of 5 is: 101 ? Example 2: Input: 7 Output: False Explanation: The binary representation of 7 is: 111. ? Example 3: Input: 11 Output: False Explanation: The binary representation of 11 is: 1011. ? Example 4: Input: 10 Output: True Explanation: The binary representation of 10 is: 1010. ?
分析:题目给一个int型正整数n,要求判断n的二进制是不是1、0间隔开的。思路也很清晰,首先就要先找到n的二进制,保存在一个数组里,然后去观察这个数组是不是1、0间隔的。这里有个小tip:int[]数组的大小设置为32,因为int型变量有32位。代码如下:
1 class Solution { 2 public boolean hasAlternatingBits(int n) { 3 int[] binary = new int[32]; 4 int i = 0; 5 while ( n > 0 ){ 6 binary[i++] = n % 2; 7 n = n/2; 8 } 9 for ( int j = 0 ; j < i - 1 ; j ++ ){ 10 if ( binary[j] + binary[j+1] != 1 ) return false; 11 } 12 return true; 13 } 14 } ? ? ? 运行时间9ms,击败97.56%。 ?
第二个思路,这个想法运用到了位运算。如果n满足条件,比如n=5,二进制是101,那么n>>1就是对101又移1位,低位补0,得到010,101^010=111。也就是说如果n是一个alternating数,那么经过上面的两步之后一定变成全1。然后判断操作之后的数是不是全1就可以了。代码如下:
1 class Solution { 2 public boolean hasAlternatingBits(int n) { 3 n = n ^ (n>>1); 4 return (n&(n+1) )== 0; //判断是否是全1,如果是全1, 5 } 6 } ? ? ? 位运算的运行时间就比较长了,16ms。不过位运算更简洁,理解了位运算也能更好理解程序。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |