程序员编程艺术,别人家的面试题

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

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

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

小胡子哥 @Barret李靖
给自身推荐了一个写算法刷题的地方
leetcode.com,没有 ACM
那么难,但问题很有趣。而且据说那一个题目都出自一些商厦的面试题。行吗,解解外人公司的面试题其实很好玩,既能整理思路训练能力,又不用操心漏题
╮(╯▽╰)╭。

长话短说,让大家来看一道题:

别人家的面试题:一个平头是还是不是是“4”的N次幂

2016/05/30 · 基本功技术 ·
2 评论 ·
算法

本文小编: 伯乐在线 –
十年踪迹
。未经小编许可,禁止转载!
欢迎参与伯乐在线 专栏撰稿人。

这是 leetcode.com
的第二篇。与上一篇如出一辙,大家探讨共同相对不难的题材,因为上学总强调规行矩步。而且,即便是不难的问题,追求算法的非凡的话,其中也是有大学问的。

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].

前奏

统计“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”的整多次幂

给定一个32位有号子整数(32 bit signed
integer),写一个函数,检查这一个平头是或不是是“4”的N次幂,这里的N是非负整数。

例如:

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

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

那应当是一道新放入的题。意思是给您一个非负整数num,对于0到num那(num+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用32位代表,那么时间复杂度就是O(32n)。

率先节、寻找满意条件的五个数
第14题(数组):
题目:输入一个数组和一个数字,在数组中查找四个数,使得它们的和正好是输入的卓殊数字。
需要时间复杂度是O(n)。即使有多对数字的和格外输入的数字,输出任意一对即可。
诸如输入数组1、2、4、7、11、15和数字15。由于4+11=15,由此输出4和11。

更快的 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 的二进制数是 1011000,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):

分析:

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”的奇很多次幂也唯有 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以此数,大家临时用一个字节来表示

俺们试着一步一步解决那一个题材(注意讲演中数列有序无序的区分):

打赏协理自己写出更加多好小说,谢谢!

任选一种支付形式

亚洲必赢官网 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

直接穷举,从数组中随心所欲选拔五个数,判定它们的和是还是不是为输入的充足数字。此举复杂度为O(N^2)。很显然,我们要寻找功用更高的解法。
题目相当于,对各类a[i],然后搜索判断sum-a[i]是还是不是也在原来种类中,每趟要寻找的时日都要开支为O(N),那样下去,最后找到八个数仍然急需O(N^2)的复杂度。那怎么提升查找判断的进度列?对了,二分查找,将原来O(N)的查找时间提升到O(logN),那样对于N个a[i],都要花logN的小时去寻找相呼应的sum-a[i]是或不是在原有种类中,总的时间复杂度已降为O(N*logN),且空间复杂度为O(1)。(假使有序,直接二分O(N*logN),要是无序,先排序后二分,复杂度同样为O(N*logN+N*logN)=O(N*logN),空间总为O(1))。
有没有更好的点子列?我们可以根据上述思路2的沉思,a[i]在体系中,若是a[i]+a[k]=sum的话,那么sum-a[i](a[k])也一定在连串中,,举个例子,如下:
原本连串:1、 2、 4、 7、11、15    
用输入数字15减一下依次数,获得相应的行列为:
对应连串:14、13、11、8、4、 0     
率先个数组以一指针i 从数组最左端伊始向右扫描,第四个数组以一指南针j
从数组最右端开始向左扫描,假若上边出现了和方面一样的数,即a[*i]=a[*j],就找出那俩个数来了。如上,i,j最后在首先个,和第三个连串中找到了一如既往的数4和11,,所以符合条件的多个数,即为4+11=15。怎样,两端同时摸索,时间复杂度须臾间减少到了O(N),但却同时必要O(N)的空中存储第一个数组(@飞羽:要达到O(N)的复杂度,第二个数组以一指针i
从数组最左端初步向右扫描,第三个数组以一指南针j
从数组最右端早先向左扫描,首先开始i指向元素1,j指向元素0,何人指的因素小,哪个人先活动,由于1(i)>0(j),所以i不动,j向左移动。然后j移动到元素4发觉超越元素1,故而截止运动j,伊始移动i,直到i指向4,那时,i指向的要素与j指向的要素相等,故而判断4是满意条件的第三个数;然后还要移动i,j再展开判断,直到它们到达边际)。
当然,你还足以协会hash表,正如编程之美上的所述,给定一个数字,按照hash映射查找另一个数字是还是不是也在数组中,只需用O(1)的大运,那样的话,总体的算法通上述思路3
一模一样,也能降到O(N),但有个缺陷,就是布局hash额外扩张了O(N)的空中,此点同上述思路
3。然则,空间换时间,仍不失为在岁月需求较严峻的情景下的一种好格局。
假定数组是无序的,先排序(n*logn),然后用三个指针i,j,各自指向数组的首尾两端,令i=0,j=n-1,然后i++,j–,逐次判断a[i]+a[j]?=sum,如若某一刻a[i]+a[j]>sum,则要想艺术让sum的值减小,所以此刻i不动,j–,倘使某一刻a[i]+a[j]<sum,则要想方法让sum的值增大,所以此时i++,j不动。所以,数组无序的时候,时间复杂度最后为O(n*logn+n)=O(n*logn),若原数组是逐步的,则不要求事先的排序,直接O(n)搞定,且空间复杂度仍然O(1),此思路是对峙于上述所有思路的一种立异。(假诺有序,直接八个指针两端扫描,时间O(N),要是无序,先排序后两端扫描,时间O(N*logN+N)=O(N*logN),空间始终都为O(1))。(与上述思路2对照,排序后的时刻支付由事先的二分的n*logn降到了扫描的O(N))。
总结:

有关小编:十年踪迹

亚洲必赢官网 3

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

亚洲必赢官网 4

打赏接济我写出越多好小说,谢谢!

任选一种支付办法

亚洲必赢官网 5亚洲必赢官网
亚洲必赢官网 6

1 赞 7 收藏 2
评论

11/2 = 5:0000 0101

随便原序列是不变依旧无序,解决那类题有以下两种办法:1、二分(若无序,先排序后二分),时间复杂度总为O(n*logn),空间复杂度为O(1);2、扫描几回X-S[i] 
映射到一个数组或社团hash表,时间复杂度为O(n),空间复杂度为O(n);3、多个指针两端扫描(若无序,先排序后扫描),时间复杂度最终为:有序O(n),无序O(n*logn+n)=O(n*logn),空间复杂度都为O(1)。
所以,要想达到时间O(N),空间O(1)的对象,除非原数组是不变的(指针扫描法),不然,当数组无序的话,就不得不先排序,后指针扫描法或二分(时间n*logn,空间O(1)),或映射或hash(时间O(n),空间O(n))。时间或空中,必须捐躯一个,自个权衡吧。
综上,假若数组有序的景况下,优先考虑三个指针两端扫描法,以达成最佳的时(O(N)),空(O(1))效应。否则,即使要排序的话,时间复杂度最快当然是不得不落得N*logN,空间O(1)则是不在话下。
代码:

至于小编:十年踪迹

亚洲必赢官网 7

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

亚洲必赢官网 8

简单发现,除了11最右侧这么些位和5的最高位,其余位对应一样。也就是说i用二进制表示时1面世的次数等于i/2中1面世的次数加1(假设i用二进制表示时最左边一位为1,否则不加1)。这样大家在总结i时可以应用前边已计算出的i/2:ret[i]
= ret[i/2] + (i % 2 == 0 ? 0 : 1);

ok,在进入第四节往日,大家先来兑现思路5(那里假定数组已经是不变的),代码可以如下编写(两段代码达成):
view plaincopy to clipboardprint?
//代码一 
//O(N) 
Pair findSum(int *s,int n,int x)    
{    
    //sort(s,s+n);   如若数组非有序的,那就优先排好序O(N*logN)    
     
    int *begin=s;    
    int *end=s+n-1;    
     
    while(begin<end)   
//俩头夹逼,或称八个指针两端扫描法,很经典的法门,O(N)   
    {    
        if(*begin+*end>x)    
        {    
            –end;    
        }    
        else if(*begin+*end<x)    
        {    
            ++begin;    
        }    
        else   
        {    
            return Pair(*begin,*end);    
        }    
    }    
     
    return Pair(-1,-1);    
}    
 
//或者正如编写, 
//代码二 
//[email protected]
zhedahht && yansha 
//July、updated,2011.05.14。 
bool find_num(int data[], unsigned int length, int sum, int&
first_num, int& second_num) 
{    
    if(length < 1) 
        return true; 
     
    int begin = 0; 
    int end = length – 1; 
     
    while(end > begin) 
    { 
        long current_sum = data[begin] + data[end]; 
         
        if(current_sum == sum) 
        { 
            first_num = data[begin]; 
            second_num = data[end]; 
            return true; 
        } 
        else if(current_sum > sum) 
            end–; 
        else 
            begin++; 
    } 
    return false; 

AC代码(C++):

扩展:
1、即使在再次回到找到的多少个数的还要,还须要您回来那多少个数的岗位列?
2、假若把问题中的要你寻找的五个数改为“四个数”,或随意个数列?(请看下边第三节)
3、二分查找时: left <= right,right = middle – 1;left <
right,right = middle;

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;
    }
};

//算法所操作的间距,

希望此编程艺术连串能给诸位带来的是一种艺术,一种创立力,一种举一反三的力量。本章依旧同第四章一样,拔取比较容易的面试题…

网站地图xml地图