转载

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

这是 leetcode.com 的第二篇。与上一篇一样，我们讨论一道相对简单的问题，因为学习总讲究循序渐进。而且，就算是简单的问题，追求算法的极致的话，其中也是有大学问的。

“4”的整数次幂

给定一个32位有符号整数（32 bit signed integer），写一个函数，检查这个整数是否是“4”的N次幂，这里的N是非负整数。

例如：

给定 num = 16，返回 true，因为 16 = 4 ²
给定 num = 5，返回 flase

附加条件：你能够不用循环和递归吗？

解题思路

如果忽略“附加条件”，这题还挺简单的对吧？简直是信手拈来：

版本1

function isPowerOfFour(num){     while(!(num % 4)){         num /= 4;     }     return num === 1; }

版本1 好像很简单、很强大的样子，它的时间复杂度是 log ₄ N。有同学说，还可以做一些微小的改动：

版本1.1

function isPowerOfFour(num){     while(!(num % 4)){       num >>>= 2;     }     return num === 1; }

上面的代码用位移替代除法，在其他语言中更快，鉴于 JS 通常情况下非常坑的位运算操作，不一定速度能变快。

好了，最关键的是，不管是版本1 还是版本1.1 似乎都不满足我们前面提到的“附加条件”，即不使用循环和递归，或者说，我们需要寻找 O(1) 的解法。

按照惯例，大家先思考10秒钟，然后往下看 ——

不用循环和递归

其实这道题真心有好多种思路，计算指数之类的对数学系学霸们完全不是问题嘛：

版本2

const log4 = Math.log(4); function isPowerOfFour(num){     var n = Math.log(num) / log4;     return n === (0|n); }

嗯，通过对数公式 log _m (n) = log(n) / log(m) 求出指数，然后判断指数是不是一个整数，这样就可以不用循环和递归解决问题。而且，还要注意细节，可以将 log4 当做常量抽取出来，这样不用每次都重复计算，果然是学霸范儿。

不过呢，利用 Math.log 方法也算是某种意义上的犯规吧，有没有不用数学函数，用原生方法来解决呢？

当然有了！而且还不止一种，大家可以继续想30秒，要至少想出一种哦 ——

不用内置函数

这个问题的关键思路和上一道题类似，先考虑“4”的幂的二进制表示：

4 ⁰ = 1B
4 ¹ = 100B
4 ² = 10000B
4 ³ = 1000000B
……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是，“4”的幂的二进制数只有 1 个“1”。如果仔细阅读过上一篇，你就会知道，判断一个二进制数只有 1 个“1”，只需要：

(num & num - 1) === 0

但是，二进制数只有 1 个“1”只是“4”的幂的 必要非充分 条件，因为“2”的奇数次幂也只有 1 个“1”。所以，我们还需要附加的判断：

(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0 ? 因为这个确保 num 的二进制的那个 “1” 出现在“奇数位”上，也就确保了这个数确实是“4”的幂，而不仅仅只是“2”的幂。

最后，我们得到完整的版本：

版本3

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

function isPowerOfFour(num) {     num = Math.sqrt(num);     return num > 0 && num === (0|num) && (num & (num-1)) === 0; };

版本5：用正则表达式

function isPowerOfFour(num) {     return /^1(00)*$/g.test(num.toString(2)); };

以上就是所有的内容，这道题有非常多种思路，相当有趣，也比较考验基本功。如果你有自己的思路，可以留言参与讨论。

下一期我们讨论另外一道题，这道题比这两道题要难一些，但也更有趣： 给定一个正整数 n，将它拆成 至少两个正数 之和，对拆出的正数求乘积，返回能够得到的 乘积最大的结果 。

想一想你的解法是什么？你能够尽可能减少算法的时间复杂度吗？期待你的答案~~

原文 https://www.h5jun.com/post/power-of-four.html

正文到此结束

所属分类：编程技术

本文标签： 时间需求代码 js https 正则表达式 http HTML
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

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

“4”的整数次幂

例如：

解题思路

不用循环和递归

不用内置函数

其他版本

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流