UDN-企业互联网技术人气社区

板块导航

浏览  : 711
回复  : 1

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

[复制链接]
哥屋恩的头像 楼主
发表于 2016-5-27 20:48:27 | 显示全部楼层 |阅读模式
  这是 leetcode.com 的第二篇。与上一篇一样,我们讨论一道相对简单的问题,因为学习总讲究循序渐进。而且,就算是简单的问题,追求算法的极致的话,其中也是有大学问的。

  “4”的整数次幂

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

  例如:

  给定 num = 16,返回 true,因为 16 = 42

  给定 num = 5,返回 flase

  附加条件: 你能够不用循环和递归吗?

  解题思路

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

  版本1

 
  1.  function isPowerOfFour(num){

  2.   while(!(num % 4)){

  3.   num /= 4;

  4.   }

  5.   return num === 1;

  6.   }
复制代码


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

  版本1.1

  
  1. function isPowerOfFour(num){

  2.   while(!(num % 4)){

  3.   num >>>= 2;

  4.   }

  5.   return num === 1;

  6.   }
复制代码


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

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

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

  不用循环和递归

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

  版本2

  
  1. const log4 = Math.log(4);

  2.   function isPowerOfFour(num){

  3.   var n = Math.log(num) / log4;

  4.   return n === (0|n);

  5.   }
复制代码


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

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

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

  不用内置函数

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

  40 = 1B

  41 = 100B

  42 = 10000B

  43 = 1000000B

  ……

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

  
  1. (num & num - 1) === 0
复制代码


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

  
  1. (num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0
复制代码


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

  最后,我们得到完整的版本:

  版本3

  
  1. function isPowerOfFour(num) {

  2.   return num > 0 && (num & (num-1)) === 0

  3.   && (num & 0xAAAAAAAA) === 0;

  4.   };
复制代码


  上面的代码需要加上 num > 0,是因为 0 要排除在外,否则 (0 & -1) === 0 也是 true

  其他版本

  上面的版本已经符合了我们的需求,时间复杂度是 O(1),不用循环和递归。

  此外,我们还可以有其他的版本,它们严格来说有的还是“犯规”,但是我们还是可以学习一下这些思路:

  版本4:用 Math.sqrt

 
  1.  function isPowerOfFour(num) {

  2.   num = Math.sqrt(num);

  3.   return num > 0 && num === (0|num) && (num & (num-1)) === 0;

  4.   };
复制代码


  版本5:用正则表达式

  
  1. function isPowerOfFour(num) {

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

  3.   };
复制代码


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

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

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

原文作者:十年踪迹 来源:开发者头条
发表于 2016-5-27 22:47:38 | 显示全部楼层
赞一个
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部