别人家的面试题:统计“1”的个数

其他版本

上面的版本已经符合了我们的需求,时间复杂度是 O(1),不用循环和递归。

此外,我们还可以有其他的版本,它们严格来说有的还是“犯规”,但是我们还是可以学习一下这些思路:

版本4:用 Math.sqrt

JavaScript

function isPowerOfFour(num) { num = Math.sqrt(num); return num > 0 &&
num === (0|num) && (num & (num-1)) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    num = Math.sqrt(num);
    return num > 0 && num === (0|num) && (num & (num-1)) === 0;
};

版本5:用正则表达式

JavaScript

function isPowerOfFour(num) { return /^1(00)*$/g.test(num.toString(2));
};

1
2
3
function isPowerOfFour(num) {
    return /^1(00)*$/g.test(num.toString(2));
};

以上就是所有的内容,这道题有非常多种思路,相当有趣,也比较考验基本功。如果你有自己的思路,可以留言参与讨论。

下一期我们讨论另外一道题,这道题比这两道题要难一些,但也更有趣:给定一个正整数
n,将它拆成至少两个正整数之和,对拆出的正整数求乘积,返回能够得到的乘积最大的结果

想一想你的解法是什么?你能够尽可能减少算法的时间复杂度吗?期待你的答案~~

打赏支持我写出更多好文章,谢谢!


打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

图片 1
图片 2

3 赞 8 收藏 5
评论

不用内置函数

这个问题的关键思路和上一道题类似,先考虑“4”的幂的二进制表示:

  • 40 = 1B
  • 41 = 100B
  • 42 = 10000B
  • 43 = 1000000B
  • ……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是,“4”的幂的二进制数只有
1 个“1”。如果仔细阅读过上一篇,你就会知道,判断一个二进制数只有 1
个“1”,只需要:

JavaScript

(num & num – 1) === 0

1
(num & num – 1) === 0

但是,二进制数只有 1
个“1”只是“4”的幂的必要非充分条件,因为“2”的奇数次幂也只有 1
个“1”。所以,我们还需要附加的判断:

JavaScript

(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

1
(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这个确保 num 的二进制的那个 “1”
出现在“奇数位”上,也就确保了这个数确实是“4”的幂,而不仅仅只是“2”的幂。

最后,我们得到完整的版本:

版本3

JavaScript

function isPowerOfFour(num) { return num > 0 && (num & (num-1)) === 0
&& (num & 0xAAAAAAAA) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    return num > 0 && (num & (num-1)) === 0
                   && (num & 0xAAAAAAAA) === 0;
};

上面的代码需要加上 num > 0,是因为 0 要排除在外,否则 (0 & -1) === 0
也是 true


countBits 的时间复杂度

考虑 countBits, 上面的算法:

  • “版本1” 的时间复杂度是 O(N*M),M 取决于 Number.prototype.toString
    和 String.prototype.replace 的复杂度。
  • “版本2” 的时间复杂度是 O(N*logN)
  • “版本3” 的时间复杂度是 O(N*M),M 是 N 的二进制数中的“1”的个数,介于
    1 ~ logN 之间。

上面三个版本的 countBits 的时间复杂度都大于 O(N)。那么有没有时间复杂度
O(N) 的算法呢?

实际上,“版本3”已经为我们提示了答案,答案就在上面的那个定律里,我把那个等式再写一遍:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

也就是说,如果我们知道了 countBit(n & (n - 1)),那么我们也就知道了
countBit(n)

而我们知道 countBit(0) 的值是 0,于是,我们可以很简单的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums;
i++){ ret.push(ret[i & i – 1] + 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i++){
       ret.push(ret[i & i – 1] + 1);
   }
   return ret;
}

原来就这么简单,你想到了吗 ╮(╯▽╰)╭

以上就是所有的内容,简单的题目思考起来很有意思吧?程序员就应该追求完美的算法,不是吗?

这是 leetcode
算法面试题系列的第一期,下一期我们讨论另外一道题,这道题也很有趣:判断一个非负整数是否是
4 的整数次方
,别告诉我你用循环,想想更巧妙的办法吧~

打赏支持我写出更多好文章,谢谢!


打赏作者

解题思路

如果忽略“附加条件”,这题还挺简单的对吧?简直是信手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num
=== 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

版本1 好像很简单、很强大的样子,它的时间复杂度是
log4N。有同学说,还可以做一些微小的改动:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; }
return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

上面的代码用位移替代除法,在其他语言中更快,鉴于 JS
通常情况下非常坑的位运算操作,不一定速度能变快。

好了,最关键的是,不管是 版本1 还是 版本1.1
似乎都不满足我们前面提到的“附加条件”,即不使用循环和递归,或者说,我们需要寻找
O(1) 的解法。

按照惯例,大家先思考10秒钟,然后往下看 ——


别人家的面试题:统计“1”的个数

2016/05/27 · JavaScript
· 5 评论 ·
Javascript,
算法

本文作者: 伯乐在线
十年踪迹
。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者

小胡子哥 @Barret李靖
给我推荐了一个写算法刷题的地方
leetcode.com,没有 ACM
那么难,但题目很有趣。而且据说这些题目都来源于一些公司的面试题。好吧,解解别人公司的面试题其实很好玩,既能整理思路锻炼能力,又不用担心漏题
╮(╯▽╰)╭。

长话短说,让我们来看一道题

不用循环和递归

其实这道题真心有好多种思路,计算指数之类的对数学系学霸们完全不是问题嘛:

版本2

JavaScript

const log4 = Math.log(4); function isPowerOfFour(num){ var n =
Math.log(num) / log4; return n === (0|n); }

1
2
3
4
5
const log4 = Math.log(4);
function isPowerOfFour(num){
    var n = Math.log(num) / log4;
    return n === (0|n);
}

嗯,通过对数公式 logm(n) = log(n) / log(m)
求出指数,然后判断指数是不是一个整数,这样就可以不用循环和递归解决问题。而且,还要注意细节,可以将
log4 当做常量抽取出来,这样不用每次都重复计算,果然是学霸范儿。

不过呢,利用 Math.log
方法也算是某种意义上的犯规吧,有没有不用数学函数,用原生方法来解决呢?

当然有了!而且还不止一种,大家可以继续想30秒,要至少想出一种哦 ——


关于作者:十年踪迹

图片 3

月影,奇舞团团长,热爱前端开发,JavaScript
程序猿一枚,能写代码也能打杂卖萌说段子。
个人主页
·
我的文章
·
14
·
    

图片 4

相关文章