外人家的面试题,寻找满意条件的七个或多个数

外人家的面试题:计算“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;
    }
};

//算法所操作的距离,

希望此编程艺术连串能给各位带来的是一种形式,一种创设力,一种举一反三的能力。本章如故同第四章一样,拔取相比较不难的面试题…

Leave a Comment.