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

2015-09-11 08:03:00  浏览:1752  作者:管理员

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

Bitwise AND of Numbers Range


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

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

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

0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1

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

1 0 0 01 0 0 11 0 1 01 0 1 1

除了相同的前缀外,将之后的各位置为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

其他


其他题目我在别的文章中都有所涉及:

  1. Single Number (【位运算经典应用】 寻找那个唯一的数)
  2. Single Number II(同上)
  3. Single Number III(同上)
  4. Number of 1 Bits(JavaScript 位运算总结&拾遗)
  5. Reverse Bits(【位运算经典应用】 求二进制逆序)

评论区

共 0 条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

【随机新闻】

返回顶部