菜单

澳门金沙国际[LeetCode]Counting Bits

2019年1月21日 - 金沙前端

旁人家的面试题:计算“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,对于0到num那(num+1)个整数,求出每个数用二进制表示时1的个数。

   
希望此编程艺术体系能给诸位带来的是一种方法,一种创立力,一种举一反三的力量。本章照旧同第四章一样,选拔比较不难的面试题,恭祝各位旅途高兴。同样,有任何问题,欢迎不吝指正。谢谢。

解题思路

澳门金沙国际,那道题咋一看还挺简单的,无非是:

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。

相关文章

发表评论

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

网站地图xml地图