[LeetCode] 326. Power of Three | 判断数字是否为3的幂

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的幂(与题目不建议使用循环、递归的思想不符)
  • math函数，求log3(n)，判断是否为整数
  • 转换为3进制，判断是否为10*形式的三进制数

方案2：时间复杂度：O(1), 空间复杂度O(1)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//326. Power of Three
//LeetCode: https://leetcode.com/problems/power-of-three/
#include <math.h>
#include <stdbool.h>

bool isPowerOfThree(int n) {
    double res = log10(n)/log10(3);
    return (res - (int)res)?false:true;
}
void main(){
    int n = 729;
    bool res = isPowerOfThree(n);
    printf("Result whether %d isPowerOfThree is : %s\n", n, (res==0)?"False":"True");
}

运行结果：

21038/ 21038 test cases passed.
Status: Accepted
Runtime: 108 ms
Submitted: 0 minutes ago
You are here! Your runtime beats 82.13% of csubmissions.

总结

  1. 最初尝试用树根(Digit Root)理论找3的幂数规律，未找到决定性规律。
  2. 用math库的方式，在leetcode中是支持的。
  3. 循环或递归的方式可行，但时间复杂度是O(logn)。