找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8775|回复: 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 编辑
: e: f; G7 t4 A2 V: g; M9 M
( D0 m  U5 j4 Y2 Hcheck一个数是否是3的次幂。
* [3 N! J0 Z& U6 T- w& l然后挂了.; E; J# s7 b3 Z

* C+ X9 c& Z& o# \我给的是:& l! [& v# T* r
isPowerOf3(int x){/ |! ]2 i: I- c
   return (x>0) &&(x==1 || ( x%3==0 && isPowerOf3(x/3) );
5 ~( h5 d: A4 L) y- n" t9 L- Y}
# Z  f9 w6 y0 Y7 F" o; K1 C' Q" y8 b5 A( b+ s4 v4 S+ b  i
请问有没有非递归的方法?4 b( D% G( H" m2 m
  ]7 D1 m* U, g0 v; u' c

评分

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

查看全部评分

本帖被以下淘专辑推荐:

10

主题

7

精华

623

积分

超级会员

Rank: 4

积分
623
发表于 9-14-2014 03:03 PM | 显示全部楼层
网上搜了下,一个思路是把这个数的每一位想加用和除以3,再将得数相加,继续除3,直到得数为1,如果在这个过程中没有余数,也就是说可以一直都除尽那么这个数就是3的幂。3 d8 u: d3 G8 x$ M3 b
. `8 g8 r6 `6 `$ K9 a7 \: ]6 }% t
还有个思路是 二分查表 {1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163}
9 @( `0 ?  g: P- f2 ]4 d! F& A* {5 q+ n6 q; R
另外,请教怎么用divide and conquer 做呢?

评分

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

查看全部评分

0

主题

0

精华

265

积分

高级会员

Rank: 3Rank: 3

积分
265
发表于 9-9-2014 11:20 PM | 显示全部楼层
  1. #!/usr/bin/env python3
    & I& E3 v0 g3 u+ n
  2. 8 q( n# @9 V: X" z1 c- D
  3. #T = O(log n), S = O(1)
    # W2 `  h- x0 m* q; M9 Y: U* s
  4. def check3(x):9 B2 k9 a3 R, z* M; H+ P; M
  5.     if x <= 0:% u# E1 c! c4 [$ I; }
  6.         return False% H+ H% a7 X" b" K/ I: W+ j
  7.     while x % 3 == 0:- `: I4 W9 @. y, d& A) F# |
  8.         x //= 3+ t2 j& ?8 K% y! U: L+ O7 s2 n
  9.     return (x == 1), d! }* W' j* e$ B2 d; H
  10. $ }  _# o, p1 C2 V. u" e
  11. def main():
    ; E* u2 G, g7 Y- e
  12.     for i in range(1, 82):
    , ?/ S5 Y  s6 h
  13.         print(i, check3(i))0 M; K  t. b1 `; R3 d
  14. 7 S) e( J0 F; U6 Q" \2 N
  15. if __name__ == '__main__':
    $ g' k- p4 m- X7 i( o  x, `9 O
  16.     main()
复制代码

3

主题

2

精华

91

积分

资深会员

Rank: 2

积分
91
发表于 9-14-2014 04:08 PM | 显示全部楼层
//log n solution" f% m! e5 m. I
bool isPowerOfThree(int n)
4 K: Y3 C$ R0 S- {0 l5 n{
, G% S$ Z: G1 G8 X( c5 K0 o        if(n <= 0) return false;
9 M, @. f8 F* W! z) V. C        if(n == 1) return true;
( C. o! \2 W; z+ K2 A) I       
: j- V$ `) X- u$ w& ]        while(n > 3)) @; I8 v9 B4 v+ L! t0 A
        {
+ a2 s8 j1 c( F  M, o/ Z) ~0 U                if((n/3)*3 == n) n /= 3;
0 y8 `  d" g% G9 t' X                else return false;6 T/ ?8 A# W1 e- f4 T8 Q
        }( Y' n6 b6 Z  U; P
        return n == 3;
) h4 q" A# s2 l$ w; ]! t& Z}
  M$ k8 \3 j% ]5 ~# w//loglog n solution
8 Q/ J& ], ^3 Fbool isPowerOfThree(int n)
6 P9 N/ M. F, P- K{  i4 h4 J) }; G7 t" A& ?
        if(n <= 0) return false;
# v4 ]9 ]! Q& `* W        if(n == 1) return true;" N* k2 t; Z1 T: I4 z/ ~% E
       
! a$ [, H  G7 c: {        vector<int> powers(1, 3);
: ^! K0 ~! @8 W+ r& j9 F4 P$ L2 [6 F        while((n/powers.back())*powers.back() == n)
6 T+ K! |. B& w5 L; g' c        {
4 S' d' r- c0 g+ J5 _) z+ f( A                n /= powers.back();
  T) Z: p# w5 W. Y( O' ^; G! }                powers.push_back(powers.back()*powers.back());7 H5 h* e' ?5 m% W$ W: m
        }
* g. c% S) W4 @3 ]; l5 w; C        while(!powers.empty()): A5 }# ^4 _. m& q8 n) L. }& v
        {7 ?- x5 @" T; r, M0 r8 F. Q& p: b
                if(n >= powers.back())
" w9 w! v4 N9 m" G  e' f! q7 k+ d                {
( E$ ^2 R1 D7 q/ c6 b# a9 u- V/ a3 o                        if((n/powers.back())*powers.back() == n); d$ ?" R! \! R8 f5 Y
                        {
9 w3 P! q1 }; _                                n/=powers.back();
( J! @! y) A- ~. E! ?" J; t; a                        }: r0 w: m/ A) J# c5 E
                        else return false;5 J5 L9 a( G, a/ Q8 }: n
                }
2 c) w  [* Y- C                powers.pop_back();
! t- j% q) J$ M+ X1 C1 F* l        }
8 ^1 ?# K% v1 t/ v) S3 ~- F        return n == 1;
! P/ [. [+ H4 v& ?/ |}2 O7 N3 y/ [! D5 ?( N+ \$ ~

0

主题

0

精华

79

积分

资深会员

Rank: 2

积分
79
发表于 1-15-2015 09:40 PM | 显示全部楼层
freshwind 发表于 1-15-2015 08:47 PM% U& _% J, C. O9 Q, r# x
...你在逗我吗? 还真去把你的代码跑了一下... 3返回false, 9返回false。你那个switch完全没用啊,任何数 ...

% t2 e* a# Q* ^. Q  a" r1 j9 @不好意思写错了。。应该是 % 10) u* C4 p2 l* P* N9 I) q
3的4n次幂以1结尾,4n+1次幂以3结尾,4n+2次幂以9结尾,4n+3次幂以7结尾(n >= 0)
7 a) L/ }% X, h' J3 o都转换为4n次幂后只有swtich中的5种情况是在+int范围内的
- B9 Y6 z- O5 M* C+ D! Y' s( g
补充内容 (1-15-2015 10:15 PM):/ ?0 j( K3 l  n! ~8 w% J1 E2 K
谢谢你的建议,我也发现这样做有很多不完善的地方。可是已经不能编辑了。。

11

主题

2

精华

199

积分

资深会员

Rank: 2

积分
199
发表于 9-10-2014 01:13 PM | 显示全部楼层
本帖最后由 bluewater 于 9-10-2014 01:53 PM 编辑 0 E# Q5 T* V- K9 ]6 k7 d  L
/ H: C/ b4 f( R; M; k: a/ }/ q
不好意思,刚看错题了

14

主题

6

精华

289

积分

高级会员

Rank: 3Rank: 3

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

4

主题

0

精华

253

积分

高级会员

Rank: 3Rank: 3

积分
253
发表于 9-9-2014 11:21 PM | 显示全部楼层
直接改成迭代版本的吧,递归效率差一点。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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