找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5917|回复: 88
收起左侧

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

  [复制链接]

11

主题

3

精华

206

积分

高级会员

Rank: 3Rank: 3

积分
206
发表于 9-9-2014 10:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 9-27-2015 08:34 PM 编辑
' ~$ l. m+ X: [* [$ r1 E/ J+ t  V4 t2 ?' b
check一个数是否是3的次幂。5 }! C, p7 E/ B
然后挂了.1 s- z, F" ]! [# X0 D
( f" R1 U: E- K1 I) e4 n$ b
我给的是:
5 g9 c7 E  l$ w  PisPowerOf3(int x){
: @9 U2 f! T( x' q/ f8 G% N) k   return (x>0) &&(x==1 || ( x%3==0 && isPowerOf3(x/3) );
, @- @; d( Q2 c9 d( N+ b( C. W9 F: w}
" E' H2 B1 N4 g9 w- O% X* `) r' W6 V5 M0 z" @
请问有没有非递归的方法?/ L  e% W: ]  w( h. x; F  n* y) p
3 _% M8 L0 g6 {0 d

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 赞一个!

查看全部评分

本帖被以下淘专辑推荐:

10

主题

7

精华

623

积分

超级会员

Rank: 4

积分
623
发表于 9-14-2014 03:03 PM | 显示全部楼层
网上搜了下,一个思路是把这个数的每一位想加用和除以3,再将得数相加,继续除3,直到得数为1,如果在这个过程中没有余数,也就是说可以一直都除尽那么这个数就是3的幂。0 x( a8 t1 z8 t! V
* p* `+ E. l  p2 c1 V- T( u1 _
还有个思路是 二分查表 {1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163}
7 F) U+ B% b( I5 q
' i8 o1 [1 ~2 l* g4 @- U另外,请教怎么用divide and conquer 做呢?

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 很给力!

查看全部评分

回复 支持 2 反对 0

使用道具 举报

0

主题

0

精华

265

积分

高级会员

Rank: 3Rank: 3

积分
265
发表于 9-9-2014 11:20 PM | 显示全部楼层
  1. #!/usr/bin/env python3# ]3 Y. k: n5 t& T; z0 m1 g
  2. 8 D3 U  k% u: y  e1 g% n( P
  3. #T = O(log n), S = O(1)
    ) r% V+ T/ y- T) I! w( t
  4. def check3(x):) |! ^  t% b6 L- m6 d* Q3 I9 y
  5.     if x <= 0:$ s. W" p3 m3 Y1 \
  6.         return False5 y, Q' [; Y- [; d/ f
  7.     while x % 3 == 0:
    6 u' U. L9 `0 j/ w2 o4 X& v
  8.         x //= 3! @4 Z% f. q: K8 {" R7 M
  9.     return (x == 1)
    % k, x, n% S1 E8 \! o8 h

  10. * l# F' ^- s1 D' \7 ]
  11. def main():! p4 }& C: A: ~5 x
  12.     for i in range(1, 82):
    7 _8 k$ }4 X) t1 q  W& C* ?& ]
  13.         print(i, check3(i))
    ( |* d1 J  W6 z5 X

  14. 0 e% H+ ^- ]. s8 C
  15. if __name__ == '__main__':2 x8 I+ e+ q5 S  g
  16.     main()
复制代码
回复 支持 2 反对 0

使用道具 举报

3

主题

2

精华

91

积分

资深会员

Rank: 2

积分
91
发表于 9-14-2014 04:08 PM | 显示全部楼层
//log n solution2 u& O1 ~+ P9 q# I9 y- Y% a  r; E/ ?
bool isPowerOfThree(int n)
+ r& {" y9 u: p- f1 g{
: y0 h! L# J( s# D6 S        if(n <= 0) return false;
/ T0 J' }2 t6 Q        if(n == 1) return true;- I6 J+ \% e& u( K7 m) \6 K8 T) X) x
       
% e4 u: D& h+ s2 X        while(n > 3)1 L* L) ~# J0 D" s$ A
        {
" m# c8 \& M) `                if((n/3)*3 == n) n /= 3;# l/ q  b  h9 D2 Y7 _; T- _( k9 K
                else return false;
6 F7 X+ q9 {$ z$ X5 }; D. i' [# |9 c) n        }- Y# u( k. H0 T8 o3 X6 b
        return n == 3;
$ U& E2 S1 W" o  c3 m/ Q' i}
: V) f; X; ?( O  D; T; r5 R//loglog n solution
" }! X/ K7 J; ^- Hbool isPowerOfThree(int n)
  O- e( d+ Q' n{
) K6 e; W1 E% f' S( N( i3 {& C        if(n <= 0) return false;
8 Z0 p1 g0 w# @) o        if(n == 1) return true;/ G2 \% w! n2 `. S/ S
        7 k6 }4 G/ d' F7 [1 c4 `' `5 S% P
        vector<int> powers(1, 3);  G# P' u  f$ p1 R8 H$ }# u
        while((n/powers.back())*powers.back() == n)
! ]8 V* t# L2 Q8 \        {
9 t& C' p& Q2 h( h' Y# f6 m. C' C5 Q                n /= powers.back();' j+ {) f5 J5 N! _
                powers.push_back(powers.back()*powers.back());; ]  _0 d7 b- w* i6 |
        }" K8 r1 M" e' K6 Z4 x
        while(!powers.empty())
4 l& N0 g7 Y! y$ d0 r; l$ f) F        {$ m  L7 W3 @+ f* M. W5 S: S
                if(n >= powers.back())
0 j6 ?- f/ u! t3 e' q                {
/ c( X9 B" J; a! Q0 e% U                        if((n/powers.back())*powers.back() == n)
" @' H6 _* j3 R8 \9 o6 Y( v                        {  \/ @7 ^" P3 j0 x" |' d
                                n/=powers.back();
8 N- o4 r9 \/ x5 `2 Q/ ^+ u                        }
6 e; L- |) m! l  i                        else return false;- e) X: |' g0 n/ w5 C
                }
1 D! b7 D) \* B                powers.pop_back();
! B$ x! ?5 ~. Z        }
& x% T$ D! z% M% L, w, N3 j        return n == 1;- S2 [' e" z$ K1 A; t) I6 ^; G
}
7 M5 r! _3 D7 H9 F) [. ~* W$ D
回复 支持 1 反对 0

使用道具 举报

0

主题

0

精华

79

积分

资深会员

Rank: 2

积分
79
发表于 1-15-2015 09:40 PM | 显示全部楼层
freshwind 发表于 1-15-2015 08:47 PM+ T5 [- S2 {, \* M) y5 S
...你在逗我吗? 还真去把你的代码跑了一下... 3返回false, 9返回false。你那个switch完全没用啊,任何数 ...
8 p$ R( ?0 h& ^$ j  q
不好意思写错了。。应该是 % 10
! R( {% T5 [: K9 h# q. Z- s0 B# J3的4n次幂以1结尾,4n+1次幂以3结尾,4n+2次幂以9结尾,4n+3次幂以7结尾(n >= 0)
; {- m  H2 O3 t3 s: v0 {都转换为4n次幂后只有swtich中的5种情况是在+int范围内的
- o2 X; d: K3 B4 V1 C6 k
' U0 N3 i9 [+ l" z4 A补充内容 (1-15-2015 10:15 PM):
6 g" d/ P) v5 p' d" Z9 C% N谢谢你的建议,我也发现这样做有很多不完善的地方。可是已经不能编辑了。。
回复 支持 1 反对 0

使用道具 举报

11

主题

2

精华

199

积分

资深会员

Rank: 2

积分
199
发表于 9-10-2014 01:13 PM | 显示全部楼层
本帖最后由 bluewater 于 9-10-2014 01:53 PM 编辑
2 }8 t" T. o& K% O4 M  `6 P+ Y- }; K5 q6 h* A+ K2 y% S1 t8 w# @$ f
不好意思,刚看错题了
回复 支持 0 反对 1

使用道具 举报

14

主题

6

精华

289

积分

高级会员

Rank: 3Rank: 3

积分
289
发表于 9-10-2014 04:46 AM | 显示全部楼层
查表法不行么?  3的次幂一共能有多少
回复 支持 1 反对 0

使用道具 举报

4

主题

0

精华

253

积分

高级会员

Rank: 3Rank: 3

积分
253
发表于 9-9-2014 11:21 PM | 显示全部楼层
直接改成迭代版本的吧,递归效率差一点。
回复 支持 反对

使用道具 举报

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

本版积分规则

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