找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: dzh1121
收起左侧

[Google] google面试题面经 - check一个数是否是3的次幂

  [复制链接]

13

主题

3

精华

260

积分

高级会员

Rank: 3Rank: 3

积分
260
发表于 9-11-2014 04:04 PM | 显示全部楼层
同理有没有讨论check是4的次幂呢

3

主题

1

精华

215

积分

高级会员

Rank: 3Rank: 3

积分
215
发表于 9-11-2014 06:09 PM | 显示全部楼层
感谢分享!

1

主题

0

精华

242

积分

高级会员

Rank: 3Rank: 3

积分
242
发表于 9-11-2014 07:13 PM | 显示全部楼层
感觉这题和leetcode的divide two integer思路类似。首先打表的方法就不说了,受限于integer的范围,确实数量不多。但我觉得面试官期望的算法肯定不是这样,不过也应该好于暴力的每次除3。更快的方法就是用3,3^2, 3^4...这样的数字来快速消除。随便写了点code,比较丑,也可能有bug,但大概意思就是这样。  {* Y/ x/ w% |  d  b
  1. public boolean isThreePower(int n){. Y' f- V! a- _) z, n8 H
  2.                 int base = 3;6 ~0 v6 n! @5 a4 h% E( t/ M$ {
  3.                 long a = Math.abs(n);! H# U, y# p/ W+ o0 e! O
  4.                 while (base <= a) {
    5 H2 p& C8 U- ~
  5.                         if (base == a) return true;2 V; s- A! `$ w+ W6 f) _/ _
  6.                         if (base > Math.sqrt(Integer.MAX_VALUE) || base * base > a) {* b. [5 b3 ^9 T7 m% H4 u
  7.                                 if (a % base != 0) {
    9 k! s* r. y' {8 {
  8.                                         return false;
    7 I7 h  @$ ]+ H0 ?7 f
  9.                                 }) t) s" T; S" j. U
  10.                                 a = a / base;
    . |% r$ E" B3 t9 ^2 m: S6 n
  11.                                 base = 3;6 l3 |' n8 P' [& G; z, H% i
  12.                         } else if (base * base == n) {
    6 Q  I/ J; H. V+ L8 l
  13.                                 return true;7 |# T7 [9 E8 C& W% i
  14.                         } else {- A6 Y$ b' Y( n* I1 ]: Q* ~
  15.                                 base = base * base;& [  \3 d" Y1 i, O
  16.                         }% x' M, c4 R1 z6 m7 o0 I
  17.                 }1 Q- d2 f; G" s  C) S/ O* D& P
  18.                 return a == 1;
    . |, P/ I% i: ]1 E0 q
  19.     }
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表