位1的个数
解题思路
这个题的解法比较多,有位移法、位操作法、查表法、二次查表法等方法。甚至在java
的工具类下面有一个bitCount()
方法可以直接返回一个整数的二进制表达式中1的个数。
但是一般如果面试题中遇到这题,往往还是考察对位操作的使用。
观察一下 n
与 n-1
这两个数的二进制表示:对于 n-1
这个数的二进制来说,相对于n
的二进制,它的最末位的一个 1
会变成 0
,最末位一个 1
之后的0
会全部变成 1
,其它位相同不变。
比如 n = 8888
,其二进制为 10001010111000
则 n - 1 = 8887
,其二进制为 10001010110111
通过按位与操作后:n & (n-1) = 10001010110000
n&(n-1
)这个操作,可以起到消除最后一个1的作用。所以可以通过执行 n&(n-1)
操作来消除 n 末尾的 1 ,消除了多少次,就说明有多少个 1 。代码实现
1 | public int NumberOf1(int n) { |
或者可以直接用jdk
自带函数解决:
1 | public int NumberOf11(int n) { |
2的幂
解题思路
首先,先来分析一下 2 的次方数的二进制写法:
1 | 2 | 4 | 8 | 16 | … |
---|---|---|---|---|---|
1 | 10 | 100 | 1000 | 10000 | … |
仔细观察,可以看出 2 的次方数都只有一个 1 ,剩下的都是 0 。根据这个特点,只需要每次判断最低位是否为 1 ,然后向右移位,最后统计 1 的个数即可判断是否是 2 的次方数。
代码实现
1 | public boolean isPowerOfTwo(int n){ |
该题还有一种巧妙的解法。再观察上面的表格,如果一个数是 2 的次方数的话,那么它的二进数必然是最高位为1,其它都为 0 ,那么如果此时我们减 1 的话,则最高位会降一位,其余为 0 的位现在都为变为 1,那么我们把两数相与,就会得到 0。
比如 2 的 3 次方为 8,二进制位 1000
,那么 8 - 1 = 7
,其中 7 的二进制位0111
。
利用这个性质,只需一行代码就可以搞定。
1 | public boolean isPowerOfTwo(int n){ |
数字的范围按位与
比如:输入[26,30]
输出:24
解题思路
首先,将[ 26 , 30 ]
的范围数字用二进制表示出来:
11010 11011 11100 11101 11110
而输出 24 的二进制是 11000
。
可以发现,只要找到二进制的 左边公共部分 即可。
所以,可以先建立一个 32 位都是 1 的 mask,然后每次向左移一位,比较 m 和 n 是否相同,不同再继续左移一位,直至相同,然后把 m 和 mask 相与就是最终结果。
代码实现
1 | public int rangeBitwiseAnd(int m,int n){ |
重复的DNA序列
例如:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC", "CCCCCAAAAA"]
解题思路
首先,依旧先将 A , C , G , T 的 ASCII 码用二进制来表示:
A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
通过观察发现每个字符的后三位都不相同,因此可以用末尾的三位来区分这四个字符。
题目要求是查找 10 个字母长的序列,这里我们将每个字符用三位来区分的话,10 个字符就需要 30 位 ,在32位机上也 OK 。
为了提取出后 30 位,需要使用 mask ,取值为 0x7ffffff(二进制表示含有 27 个 1) ,先用此 mask 可取出整个序列的后 27 位,然后再向左平移三位可取出 10 个字母长的序列 ( 30 位)。
为了保存子串的频率,这里使用哈希表。
首先当取出第十个字符时,将其存在哈希表里,和该字符串出现频率映射,之后每向左移三位替换一个字符,查找新字符串在哈希表里出现次数,如果之前刚好出现过一次,则将当前字符串存入返回值的数组并将其出现次数加一,如果从未出现过,则将其映射到 1。
举个栗子:
根据题意,第一个操作:首先取出前九个字符 AAAAACCCC ,根据上面的分析,用三位来表示一个字符,所以这九个字符可以用二进制表示为 001001001001001011011011011,
第二个操作:开始遍历字符串,下一个进来的是 C ,则当前字符为 AAAAACCCCC ,二进制表示为001001001001001011011011011011,然后将其存入哈希表中。然后再读入下一个字符 A,则此时字符串为AAAACCCCCA,依旧使用二进制进行表示。
以此类推,当某个序列之前已经出现过了,只需要将其存入结果 res 中即可 。
代码实现
1 | class Solution { |