转载

leetcode - 位运算题目汇总(下）

接上文 leetcode - 位运算题目汇总(上），继续来切leetcode中 Bit Manipulation 下的题目。

Bitwise AND of Numbers Range

给出一个范围，[m, n]（0 <= m <= n <= 2147483647），返回这些数字的与运算结果。

直接逐个做与运算，TLE，我们得发现高效解法。

我们把[0, 15]用二进制码表示出来：

仔细看，几个连续的二进制码肯定会有相同的前缀（前缀长度可能为0），比如以下的二进制码相同的前缀就是 1 0 :

除了相同的前缀外，将之后的各位置为0即为所求： 1 0 0 0 ，也就是8。如何求解这个相同前缀？只需要m和n同时右移，直到两数相等为止：

/**  * @param {number} m  * @param {number} n  * @return {number}  */ var rangeBitwiseAnd = function(m, n) {   if (m === n)     return m;    var tmp = rangeBitwiseAnd(m >> 1, n >> 1);   return tmp << 1; };

还有一种更巧妙的方法，将n的最右边的 1 bit 置为0，直到值不大于m即可：

/**  * @param {number} m  * @param {number} n  * @return {number}  */ var rangeBitwiseAnd = function(m, n) {   while (m < n)     n = n & (n - 1);   return n; };

Repeated DNA Sequences

给你一串字符串表示DNA，输出重复的子串。

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",  Return: ["AAAAACCCCC", "CCCCCAAAAA"].

直接用JavaScript的对象哈希字符串，提交，MLE：

var findRepeatedDnaSequences = function(s) {   var hash = {}     , ans = 0;    for (var i = 0, len = s.length; i < len; i++) {     var str = s.substr(i, 10);     if (str.length < 10) break;     if (!hash[str])        hash[str] = 1;     else if (hash[str] === 1)       hash[str]++, ans++;   }    return ans; };

这题的关键是如何哈希，幸运的是JavaScript虽然没有C++那样强大的stl，但是也有 Set ，我们用set进行哈希，AC：

var findRepeatedDnaSequences = function(s) {   var hash = new Set()     , hash_ans = new Set()     , ans = [];    for (var i = 0, len = s.length; i < len; i++) {     var str = s.substr(i, 10);     if (str.length < 10) break;     if (!hash.has(str))        hash.add(str);     else {       if (!hash_ans.has(str)) {         hash_ans.add(str);         ans.push(str);       }     }   }    return ans; };

但是好像没有说到位运算啊！我们思考下如何用 数字哈希 代替 字符串哈希 以减少内存消耗。

如果只有两种字符，我们便可以用0和1分别代替字符，组成一个二进制码，然后用一个整数代替这个二进制码完成哈希。但是不幸的是，现在有四个字符，如何？4进制？4进制的确是个好办法，但是操作起来不方便，我们可以用 两位二进制码代替一位四进制码 ，比如我们分别用 0 1 2 3 表示 A C G T ，用两位的二进制码 00 01 10 11 代替 0 1 2 3 。

var findRepeatedDnaSequences = function(s) {   var map = []     , hash = new Array(0xfffff)     , ans = [];    map['A'] = 0, map['C'] = 1, map['G'] = 2, map['T'] = 3;      var tmp = 0;   for (var i = 0, len = s.length; i < len; i++) {     tmp = tmp << 2 | map[s[i]];     if (i < 9) continue;     if (i > 9) tmp = tmp & 0xfffff;      if (!hash[tmp])        hash[tmp] = 1;     else if (hash[tmp] === 1)        hash[tmp]++, ans.push(s.substring(i - 9, i + 1));   }    return ans; };

不幸的是，又是MLE...这里不得不嗔怪下JavaScript对象的“吝啬”，稍微内存大搞大点，就MLE了，其实也就开了1048575大的数组。还好我们有set..

var findRepeatedDnaSequences = function(s) {   var map = []     , hash = new Set()     , hash_ans = new Set()     , ans = [];    map['A'] = 0, map['C'] = 1, map['G'] = 2, map['T'] = 3;      var tmp = 0;   for (var i = 0, len = s.length; i < len; i++) {     tmp = tmp << 2 | map[s[i]];     if (i < 9) continue;     if (i > 9) tmp = tmp & 0xfffff;      if (!hash.has(tmp))        hash.add(tmp);     else {       if (!hash_ans.has(tmp)) {         hash_ans.add(tmp);         ans.push(s.substring(i - 9, i + 1));       }     }   }    return ans; };

144ms beats 100% JavaScript submissions