这是 leetcode.com 的第二篇。与上一篇一样,我们讨论一道相对简单的问题,因为学习总讲究循序渐进。而且,就算是简单的问题,追求算法的极致的话,其中也是有大学问的。
给定一个32位有符号整数(32 bit signed integer),写一个函数,检查这个整数是否是“4”的N次幂,这里的N是非负整数。
附加条件:你能够不用循环和递归吗?
如果忽略“附加条件”,这题还挺简单的对吧?简直是信手拈来:
版本1
function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num === 1; }
版本1 好像很简单、很强大的样子,它的时间复杂度是 log 4 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”的幂的二进制数只有 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,将它拆成 至少两个正数 之和,对拆出的正数求乘积,返回能够得到的 乘积最大的结果 。
想一想你的解法是什么?你能够尽可能减少算法的时间复杂度吗?期待你的答案~~