0326._power_of_three.md

326. Power of Three

难度: Easy

刷题内容

原题连接

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

内容描述

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

Example 1:

Input: 27
Output: true
Example 2:

Input: 0
Output: false
Example 3:

Input: 9
Output: true
Example 4:

Input: 45
Output: false
Follow up:
Could you do it without using any loop / recursion?

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

直接就上的递归

class Solution(object):
    def isPowerOfThree(self,n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        if n == 1:
            return True
        if n % 3 == 0:
            return self.isPowerOfThree(n/3)
        return False   

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

看到了取巧的办法，因为是Given an integer,是有范围的（<2147483648),存在能输入的最大的3的幂次，即 3^19=1162261467。

只用检查是否能被这个数整除

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and pow(3, 19) % n == 0