禁止转载巴黎人手机版,求出每个数用二进制表
分类:巴黎人-前端

别人家的面试题:总括“1”的个数

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

本文笔者: 伯乐在线 - 十年踪迹 。未经笔者许可,禁止转载!
应接参预伯乐在线 专辑作者。

小胡子哥 @Barret李靖 给自己引入了三个写算法刷题的地点 leetcode.com,没有 ACM 那么难,但难点很风趣。并且据悉这么些主题材料都来自一些同盟社的面试题。好吧,解解外人集团的面试题其实很有趣,既可以整理思路磨炼技术,又不用忧虑漏题 ╮(╯▽╰)╭。

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

别人家的面试题:多少个平头是还是不是是“4”的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();
}
// 合併七个空白为三个白手
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;

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

笔试面试平时涉及各个算法,本文简介常用的局地算法,并用javascript实现。

统计“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) {
    //在此处实现代码
};

“4”的整多次幂

给定三个三10个人有标记整数(32 bit signed integer),写叁个函数,检查那么些子弹头是或不是是“4”的N次幂,这里的N是非负整数。

例如:

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

叠合条件: 你可见不用循环和递归吗?

你或然感兴趣的稿子:

  • 详解JS中Array对象增加与String对象扩大
  • Javascript string 扩充库代码
  • Javascript String对象扩展HTML编码和平解决码的法门
  • JavaScript 字符串数字左补位,右补位,取固定长度,截位扩张函数代码
  • JavaScript中ES6字符串扩张方法
  • JavaScript常用字符串与数组扩大函数小结
  • js完毕prototype扩大的诀窍(字符串,日期,数组扩张)
  • javascript框架设计读书笔记之字符串的扩展和修补
  • JS字符串函数扩张代码
  • JavaScript落到实处替换字符串中最终二个字符的办法
  • JavaScript利用正则表明式替换字符串中的内容
  • js replace(a,b)之替换字符串中持有钦点字符的艺术
  • JavaScript基于扩张String完结替换字符串中index处字符的方法

那应该是一道新放入的题。意思是给您三个非负整数num,对于0到num那(num+1)个整数,求出每一个数用二进制表示时1的个数。

1、插入排序

解题思路

那道题咋一看还挺轻巧的,无非是:

  • 兑现三个艺术 countBit,对放肆非负整数 n,计算它的二进制数中“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(2) 转成二进制表示的字符串,然后去掉个中的0,剩下的正是“1”的个数。

然后,大家写一下一体化的顺序:

版本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(2) 和 String.prototype.replace 的达成。

故此为了追求越来越好的写法,大家有必不可缺思虑一下 countBit 的通用达成法。

我们说,求贰个卡尺头的二进制表示中 “1” 的个数,最家常的本来是一个 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

如此完毕也很简短不是啊?不过那样完毕是或不是最优?提出此处思量10分钟再往下看。


解题思路

万一忽略“附加条件”,那题还挺轻便的对吗?差相当少是随手拈来:

版本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分钟,然后往下看 ——


最简易的思绪:对各类数,利用活动和按位与(i & 1)运算,总结1的个数。那样时间复杂度为O(n*sizeof(integer)),假若int用叁十三位表示,那么时间复杂度正是O(32n)。

1)算法简要介绍

更快的 countBit

上一个本子的 countBit 的光阴复杂度已经是 O(logN) 了,难道还是能够更加快吗?当然是可以的,我们不要求去看清每壹位是或不是“1”,也能明白n 的二进制中有几个“1”。

有一个门槛,是基于以下贰个定律:

  • 对此自由 n, n ≥ 1,有如下等式创立:

countBit(n & (n - 1)) === countBit(n) - 1

1
countBit(n & (n - 1)) === countBit(n) - 1

以此很轻松通晓,大家只要想转手,对于自由 n,n – 1 的二进制数表示正好是 n 的二进制数的最末三个“1”退位,因而 n & n – 1 恰恰将 n 的最末一位“1”消去,比如:

  • 6 的二进制数是 110, 5 = 6 – 1 的二进制数是 101,6 & 5 的二进制数是 110 & 101 == 100
  • 88 的二进制数是 101一千,87 = 88 – 1 的二进制数是 1010111,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) 却必要循环 7 次。

优化到了这么些水平,是否全方位都终止了呢?从算法上的话仿佛早已是极致了?真的吗?再给大家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秒,要起码想出一种啊 ——


虚拟优化成O(n):

插入排序(Insertion-Sort)的算法描述是一种简易直观的排序算法。它的专业规律是通过创设有序类别,对于未排序数据,在已排序种类中从后迈入扫描,找到呼应地点并插入。插入排序在促成上,平时使用in-place排序(即只需用到O(1)的额外层空间间的排序),因此在从后迈入扫描进程中,供给每每把已排序成分日渐向后挪位,为新型因素提供插入空间。

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 的整多次方,别告诉作者你用循环,想想更抢眼的方法吗~

打赏协理自个儿写出越来越多好小说,多谢!

打赏作者

不用内置函数

其一主题素材的重大思路和上一道题类似,先考虑“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”的奇数14回幂也只有 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


对于11这一个数,我们一时用二个字节来代表

2)算法描述和贯彻

打赏帮忙本身写出越多好小说,多谢!

任选一种支付方式

巴黎人手机版 1 巴黎人手机版 2

3 赞 8 收藏 5 评论

其他版本

地点的本子现已符合了我们的供给,时间复杂度是 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,将它拆成起码八个正整数之和,对拆出的正整数求乘积,重回可以获得的乘积最大的结果

想一想你的解法是怎么?你能够尽恐怕收缩算法的大运复杂度吗?期待您的答案~~

打赏补助小编写出更加的多好作品,谢谢!

打赏笔者

11:           0000 1011

一般的话,插入排序都使用in-place在数组上贯彻。具体算法描述如下:

关于小编:十年踪迹

巴黎人手机版 3

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

巴黎人手机版 4

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

任选一种支付办法

巴黎人手机版 5 巴黎人手机版 6

1 赞 7 收藏 2 评论

11/2 = 5:0000 0101

从第八个成分最初,该因素得以以为曾经被排序;

至于笔者:十年踪迹

巴黎人手机版 7

月影,奇舞蹈艺术团准将,热爱前端开荒,JavaScript 工程师一枚,能写代码也能打杂卖萌说段子。 个人主页 · 我的稿子 · 14 ·     

巴黎人手机版 8

轻便发觉,除了11最左边那个位和5的最高位,别的位对应同样。也等于说i用二进制表示时1面世的次数等于i/第22中学1面世的次数加1(假诺i用二进制表示时最右侧一个人为1,不然不加1)。那样我们在测算i时能够选拔前边已总计出的i/2:ret[i] = ret[i/2] + (i % 2 == 0 ? 0 : 1);

取出下贰个要素,在曾经排序的成分种类中从后迈入扫描;

AC代码(C++):

假使该因素(已排序)大于新因素,将该因素移到下一岗位;

class Solution {
public:
    vector<int> countBits(int num) {
        if (num <= 0)
            return vector<int>(1, 0);

        vector<int> ret(num+1, 0);
        int i = 0;
        int half = 0;

        for (i = 1; i <= num; ++i)
        {
            //the number of 1's in half equals the number of 1's in i except the right-most bit in i 
            half = i >> 1;
            if (i % 2 == 0)//the right-most bit in i is 0
                ret[i] = ret[half];
            else//the right-most bit in i is 1
                ret[i] = ret[half] + 1;
        }

        return ret;
    }
};

再度步骤3,直到找到已排序的要素小于恐怕等于新因素的岗位;

将新成分插入到该职位后;

再一次步骤2~5。

JavaScript代码实现:

function insertionSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

for (var i = 1; i < array.length; i++) {

var key = array[i];

var j = i – 1;

while (j >= 0 && array[j] > key) {

array[j + 1] = array[j];

j–;

}

array[j + 1] = key;

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法解析

极品状态:输入数组按升序排列。T(n) = O(n)

最坏情状:输入数组按降序排列。T(n) = O(n2)

平均情状:T(n) = O(n2)

二、二分插入排序

1)算法简单介绍

二分插入(Binary-insert-sort)排序是一种在直接插入排序算法上进展小改动的排序算法。其与间接插入排序算法最大的区分在于寻觅插入地点时行使的是二分查找的格局,在速度上有一定升高。

2)算法描述和促成

貌似的话,插入排序都应用in-place在数组上落实。具体算法描述如下:

从第二个成分开首,该因素得以感觉已经被排序;

收取下三个因素,在已经排序的要素体系中二分查找到第八个比它大的数的任务;

将新成分插入到该岗位后;

重复上述两步。

JavaScript代码完结:

function binaryInsertionSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

for (var i = 1; i < array.length; i++) {

var key = array[i], left = 0, right = i – 1;

while (left <= right) {

var middle = parseInt((left + right) / 2);

if (key < array[middle]) {

right = middle – 1;

} else {

left = middle + 1;

}

}

for (var j = i – 1; j >= left; j–) {

array[j + 1] = array[j];

}

array[left] = key;

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法解析

最棒状态:T(n) = O(nlogn)

最差意况:T(n) = O(n2)

平均情形:T(n) = O(n2)

三、选用排序

1)算法简单介绍

本文由巴黎人手机版发布于巴黎人-前端,转载请注明出处:禁止转载巴黎人手机版,求出每个数用二进制表

上一篇:网络连接上的优化巴黎人手机版 下一篇:没有了
猜你喜欢
热门排行
精彩图文