leetcode: 326. 3的幂

题目

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/power-of-three

给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false 。

整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x

示例 1:

输入:n = 27
输出:true

示例 2:

输入:n = 0
输出:false

示例 3:

输入:n = 9
输出:true

示例 4:

输入:n = 45
输出:false

提示:
-231<= n <= 231 - 1

解法

  • 循环: 循环31次,判断此时的幂指数是否是n
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        for i in range(31):
            target = 3 ** i
            if n == target:
                return True
        return False
  • 递归: n是3的幂指数,n/3仍然是3的幂指数
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True
        def help(n):
            if n == 0:
                return False
            if n == 1:
                return True
            n = n / 3
            return help(n)
        return help(n)
  • 整除判断余数是否为1
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n = n / 3
        return n == 1
  • 判断是否是3最大幂指数的约数
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        max_val = 3 ** 31
        if max_val % n == 0:
            return True
        return False

复杂度分析

最好的情况下

  • 时间复杂度:O(1) 常数大小
  • 空间复杂度:O(1) 只使用了常量的额外空间
上一篇:基于Linux的C++ | 2_程序控制结构


下一篇:顺序表