菜单

manbetx2.0手机版争判断一个整数是否是2的N次幂

2018年11月15日 - Html/Html5

别人家的面试题:一个整数是否是“4”的N次幂

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

本文作者: 伯乐在线 –
十年踪迹
。未经作者许可,禁止转载!
接加入伯乐在线 专栏作者。

这是 leetcode.com
的第二首。与上一篇同等,我们谈论并相对简便易行的题目,因为学到底强调循序渐进。而且,就终于简单的题材,追求算法的最为的话,其中为是发高校问底。

static bool CheckPowerOfTwo(ulong num)
{
    return num > 0 && (num & (num - 1)) == 0;
}

“4”的整数赖幂

让一定一个32各类来号整数(32 bit signed
integer),写一个函数,检查这个平头是否是“4”的N次幂,这里的N是非负整数。

例如:

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

 

解题思路

若是忽视“附加条件”,这题还老简单的针对性吧?简直是随手拈来:

版本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秒钟,然后朝生看 ——


无须循环和递归

实质上就道题真心有成百上千种植思路,计算指数之类的对准数学系学霸们一齐不是问题嘛:

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


永不搭函数

这个题材之重要性思路和达成同鸣题类似,先考虑“4”的埋的二进制表示:

呢就是是每个数比达一个频底二进制后面多简单个零嘛。最关键的凡,“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


其余版本

点的版现已入了我们的要求,时间复杂度是 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,将她拆成起码少独刚刚整数之和,对拆有底正整数求乘积,返回能够得到的乘积最酷的结果

想同一怀念你的解法是啊?你能尽可能减少算法的光阴复杂度吗?期待你的答案~~

打赏支持我形容来双重多好章,谢谢!

打赏作者

打赏支持我形容有又多好文章,谢谢!

任选一种植出方式

manbetx2.0手机版 1
manbetx2.0手机版 2

1 赞 7 收藏 2
评论

有关作者:十年踪迹

manbetx2.0手机版 3

月影,奇舞团团长,热爱前端开发,JavaScript
程序猿一朵,能写代码也会由杂卖萌说段子。
个人主页 ·
我之稿子 ·
14 ·
    

manbetx2.0手机版 4

相关文章

标签:

发表评论

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

网站地图xml地图