指尖世界

分享的乐趣

[leetcode]326. Power of Three

类别: 观点 更新时间: 2016-03-16

[摘要:Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion? ]

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

题意:给你一个数,判断它是否为3的幂。
程序中最好不采用任何循环和递归。

思路:下面给出两种解法,第一种为常规解法,采用循环。利用3的幂次方的数可表示为: n = 1* 3^n;
第二种解法思路:32bit的整数中最大的3的幂次方数为1162261476。那么任何3的幂次方数 m与这个最大数有如下关系: 1162261467 = m * 3^n.

解法一(有循环,效率差):

bool isPowerOfThree(int n) {
   if(n < 1)
        return 0;

    while( !(n%3) )
        n /= 3;

    return n == 1;
}

解法二(无循环):

bool isPowerOfThree(int n) {
     return n > 0 && !(1162261467%n);
}


感谢关注 V8指尖世界精品文库频道,v8en.com是专门为互联网人打造的学习交流平台,全面满足互联网人工作与学习需求,更多互联网资讯尽在 V8指尖世界!