外人家的面试题:总结“1”的个数

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

本文作者: 伯乐在线 –
拾年踪迹
。未经笔者许可,禁止转发!
迎接参与伯乐在线 专栏撰稿人。

小胡子哥 @Barret李靖
给本人推荐了3个写算法刷题的地点
leetcode.com,没有 ACM
那么难,但难题很风趣。而且传闻这几个主题材料都来源于一些公司的面试题。行吗,解解外人集团的面试题其实很风趣,既能整理思路操练工夫,又并非忧郁漏题
╮(╯▽╰)╭。

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

别人家的面试题:四个整数是还是不是是“肆”的N次幂

2016/05/30 · 基础才能 ·
2 评论 ·
算法

本文小编: 伯乐在线 –
十年踪迹
。未经作者许可,禁止转发!
招待参预伯乐在线 专栏撰稿人。

这是 leetcode.com
的第叁篇。与上一篇同样,大家探究共同相对简单的标题,因为上学总重申循途守辙。而且,尽管是简单的难题,追求算法的特出的话,当中也是有大学问的。

//获取字符数组
String.prototype.ToCharArray=function()
{
         return this.split(“”);
}
//获取N个①律的字符串
String.prototype.Repeat=function(num)
{
    var tmpArr=[];
    for(var i=0;i<num;i++)    tmpArr.push(this);
    return tmpArr.join(“”);
}
//逆序
String.prototype.Reverse=function()
{
     return this.split(“”).reverse().join(“”);
}
//测试是还是不是是数字
String.prototype.IsNumeric=function()
{
    var tmpFloat=parseFloat(this);
    if(isNaN(tmpFloat))    return false;
    var tmpLen=this.length-tmpFloat.toString().length;
    return tmpFloat+”0″.Repeat(tmpLen)==this;
}
//测试是或不是是整数
String.prototype.IsInt=function()
{
    if(this==”NaN”)    return false;
    return this==parseInt(this).toString();
}
// 合并八个空白为3个空手
String.prototype.resetBlank = function()
{
    return this.replace(/s+/g,” “);
}
// 除去左边空白
String.prototype.LTrim = function()
{
    return this.replace(/^s+/g,””); 

// 除去左边空白
String.prototype.RTrim = function()
{
    return this.replace(/s+$/g,””); 
}
// 除去两边空白
String.prototype.trim = function()
{
    return this.replace(/(^s+)|(s+$)/g,””); 
}
// 保留数字
String.prototype.getNum = function()
{
    return this.replace(/[^d]/g,””);
}
// 保留字母
String.prototype.getEn = function()
{
    return this.replace(/[^A-Za-z]/g,””); 
}
// 保留中文
String.prototype.getCn = function()
{
    return this.replace(/[^u4e00-u9fa5uf900-ufa2d]/g,””);
}
// 获得字节长度
String.prototype.getRealLength = function()
{
    return this.replace(/[^x00-xff]/g,”–“).length;
}
// 从左截取内定长度的字串
String.prototype.left = function(n)
{
    return this.slice(0,n);
}
// 从右截取钦命长度的字串
String.prototype.right = function(n)
{
    return this.slice(this.length-n);
}
// HTML编码
String.prototype.HTMLEncode = function()
{
    var re = this;
    var q1 = [/x26/g,/x3C/g,/x3E/g,/x20/g];
    var q2 = [“&”,”<“,”>”,” “];
    for(var i=0;i<q1.length;i++)
    re = re.replace(q1[i],q2[i]);
    return re;
}
// Unicode转化
String.prototype.ascW = function()
{
    var strText = “”;
    for (var i=0; i<this.length; i++) strText += “” + this.charCodeAt(i) + “;”;
    return strText;

统计“1”的个数

给定二个非负整数 num,对于放四 i,0 ≤ i ≤ num,总括 i
的值对应的二进制数中 “1” 的个数,将这个结果回到为三个数组。

例如:

当 num = 5 时,重回值为 [0,1,1,2,1,2]。

/** * @param {number} num * @return {number[]} */ var countBits =
function(num) { //在此处落成代码 };

1
2
3
4
5
6
7
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
    //在此处实现代码
};

“四”的平头次幂

给定3个三十几人有暗记整数(32 bit signed
integer),写两个函数,检查那些平头是还是不是是“四”的N次幂,那里的N是非负整数。

例如:

  • 给定 num = 16,返回 true,因为 16 = 42
  • 给定 num = 5,返回 flase

外加条件: 你可以不用循环和递归吗?

您或然感兴趣的文章:

  • 详解JS中Array对象扩展与String对象扩充
  • Javascript string
    扩充库代码
  • Javascript
    String对象扩充HTML编码和解码的诀窍
  • JavaScript
    字符串数字左补位,右补位,取固定长度,截位扩充函数代码
  • JavaScript中ES陆字符串扩充方法
  • JavaScript常用字符串与数组扩张函数小结
  • js达成prototype增加的法门(字符串,日期,数组扩充)
  • javascript框架企划读书笔记之字符串的扩大和修补
  • JS字符串函数扩展代码
  • JavaScript贯彻替换字符串中最终2个字符的办法
  • JavaScript利用正则表明式替换字符串中的内容
  • js
    replace(a,b)之替换字符串中具备钦命字符的措施
  • JavaScript基于扩大String达成替换字符串中index处字符的情势

解题思路

那道题咋一看还挺简单的,无非是:

  • 贯彻2个艺术 countBit,对任意非负整数
    n,总计它的2进制数中“1”的个数
  • 循环 i 从 0 到 num,求 countBit(i),将值放在数组中回到。

JavaScript中,计算 countBit 能够取巧:

function countBit(n){ return n.toString(2).replace(/0/g,””).length; }

1
2
3
function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

地点的代码里,大家一贯对 n 用 toString(二)
转成二进制表示的字符串,然后去掉在那之中的0,剩下的正是“一”的个数。

然后,大家写一下完好的次序:

版本1

function countBit(n){ return n.toString(2).replace(/0/g,”).length; }
function countBits(nums){ var ret = []; for(var i = 0; i <= nums;
i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
function countBit(n){
   return n.toString(2).replace(/0/g,”).length;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面那种写法十一分别得到益,好处是 countBit 利用 JavaScript
语言特色落成得特别简短,坏处是即使后天要将它改写成此外语言的版本,就有希望懵B了,它不是很通用,而且它的质量还在于
Number.prototype.toString(二) 和 String.prototype.replace 的兑现。

因此为了追求更加好的写法,大家有供给怀想一下 countBit 的通用达成法。

我们说,求3个平头的二进制表示中 “壹” 的个数,最普通的本来是多个 O(logN)
的办法:

function countBit(n){ var ret = 0; while(n > 0){ ret += n & 1; n
>>= 1; } return ret; }

1
2
3
4
5
6
7
8
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

从而我们有了版本2

诸如此类达成也很轻松不是啊?可是如此完成是或不是最优?提议此处考虑拾分钟再往下看。


解题思路

壹旦忽略“附加条件”,那题还挺轻松的对吗?简直是随手拈来:

版本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
日常状态下11分坑的位运算操作,不断定速度能变快。

好了,最要紧的是,不管是 版本一 要么 版本一.一就好像都不满意大家前边提到的“附加条件”,即不选择循环和递归,只怕说,我们须要寻觅O(1) 的解法。

依照常规,大家先研商十分钟,然后往下看 ——


更快的 countBit

上二个本子的 countBit 的年华复杂度已经是 O(logN)
了,难道还是能够更加快吧?当然是足以的,大家不要求去看清每1位是还是不是“壹”,也能明了
n 的贰进制中有多少个“一”。

有八个秘技,是依据以下多少个定律:

  • 对此自由 n, n ≥ 一,有如下等式创设:

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

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

本条很轻便驾驭,大家借使想转手,对于随便 n,n – 壹 的2进制数表示正好是 n
的2进制数的最末1个“1”退位,由此 n & n – 一 恰巧将 n
的最末壹人“一”消去,举个例子:

  • 6 的2进制数是 110, 5 = 6 – 1 的2进制数是 十1,6 & 5
    的2进制数是 110 & 101 == 100
  • 88 的二进制数是 101壹仟,87 = 88 – 1 的2进制数是
    10拾11①,88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是乎,我们有了一个更加快的算法:

版本3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret++;
        n &= n – 1;
    }
    return ret;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面的 countBit(88) 只循环 3 次,而“版本2”的 countBit(88) 却要求循环
七 次。

优化到了那几个水平,是否全部都甘休了呢?从算法上的话就像早已是极致了?真的吗?再给我们30 秒时间思索一下,然后再往下看。


绝不循环和递归

实则那道题真心有数不尽种思路,总括指数之类的对数学系学霸们一起小意思嘛:

版本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秒,要至少想出1种啊 ——


countBits 的时光复杂度

考虑 countBits, 下边包车型地铁算法:

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

下边多个本子的 countBits 的时光复杂度都高于 O(N)。那么有未有时间复杂度
O(N) 的算法呢?

其实,“版本3”已经为大家提示了答案,答案就在上头的要命定律里,笔者把相当等式再写1回:

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
算法面试题连串的率先期,下1期大家谈谈此外壹道题,这道题也很有趣:判别三个非负整数是不是是
肆 的平头次方
,别告诉自身你用循环,想想更抢眼的点子呢~

打赏补助笔者写出越多好作品,多谢!

打赏小编

永不内置函数

以此标题标首要性思路和上1道题类似,先思考“四”的幂的2进制表示:

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

也正是每个数比上一个数的2进制前边多八个零嘛。最关键的是,“四”的幂的2进制数只有一 个“一”。要是仔细阅读过上1篇,你就会知道,剖断三个二进制数唯有 1个“1”,只必要:

JavaScript

(num & num – 1) === 0

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

只是,2进制数唯有 一个“壹”只是“4”的幂的要求非丰裕条件,因为“二”的奇数11遍幂也唯有 1个“壹”。所以,大家还亟需增大的论断:

JavaScript

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

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

干什么是 num & 0xAAAAAAAA === 0? 因为那些保障 num 的二进制的非凡 “一”
现身在“奇数位”上,也就保障了那些数确实是“4”的幂,而不仅只是“贰”的幂。

末尾,大家收获完全的本子:

版本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


打赏接济小编写出越来越多好小说,感激!

任选壹种支付办法

图片 1
图片 2

3 赞 8 收藏 5
评论

其它版本

上边的本子现已符合了我们的急需,时间复杂度是 O(一),不用循环和递归。

除此以外,我们还是能够有别的的本子,它们严刻来说有的依然“犯规”,不过大家仍是能够学习一下这一个思路:

版本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想你的解法是何等?你可见尽大概减弱算法的时日复杂度吗?期待你的答案~~

打赏辅助小编写出越多好作品,多谢!

打赏小编

至于笔者:10年踪迹

图片 3

月影,奇舞团中将,热爱前端开垦,JavaScript
技师一枚,能写代码也能打杂卖萌说段子。
个人主页 ·
笔者的小说 ·
14 ·
    

图片 4

打赏帮助笔者写出越多好文章,多谢!

任选1种支付办法

图片 1
图片 2

1 赞 7 收藏 2
评论

至于笔者:拾年踪迹

图片 3

月影,奇舞蹈艺术团中将,热爱前端开采,JavaScript
技术员一枚,能写代码也能打杂卖萌说段子。
个人主页 ·
作者的篇章 ·
14 ·
    

图片 4

Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注