LeetCode 326 Power of Three

Tag: 数学类题目 LeetCode Posted on 2022-03-07 16:21:42 Edited on 2022-03-07 16:30:14 Views: 145

概述

https://leetcode.com/problems/power-of-three/

递归法

时间复杂度 O(logn)。

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n == 0) return false;
        if (n == 1) return true;
        if (n % 3 != 0) return false;
        return isPowerOfThree(n / 3);
    }
};

质数法

https://leetcode.com/problems/power-of-three/discuss/77856/1-line-java-solution-without-loop-recursion

利用其质数的性质,

public class Solution {
public boolean isPowerOfThree(int n) {
    // 1162261467 is 3^19,  3^20 is bigger than int  
    return ( n > 0 &&  1162261467 % n==0);
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/