[263][简单][回溯] 丑数

题目描述

263. 丑数

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

• 1 是丑数

• 输入不会超过 32 位有符号整数的范围: $[−2^{31}, 2^{31} - 1]$

解题思路

回溯即可. 不停地除以2, 3, 5因子, 直到无法整除(回溯停止条件), 为1则为丑数, 不唯一说明有别的质数, 不是丑数.

递归版本如下:

class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1:
            return False

        def is_ugly(number):
            if number == 1:
                return True

            cond2, cond3, cond5 = False, False, False
            if number % 2 == 0:
                cond2 = is_ugly(number // 2)
            if number % 3 == 0:
                cond3 = is_ugly(number // 3)
            if number % 5 == 0:
                cond5 = is_ugly(number // 5)
            return cond2 or cond3 or cond5
        return is_ugly(num)

但递归的效率低, 原因是做了很多重复的除法计算. 例如6对2, 3可整除, 在2和3处都进行了递归, 算了两遍. 优化的方法是使用迭代, 整除完之后, 就判断结果是否为丑数即可.

class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1:
            return False

        while num > 1:
            if num % 2 == 0:
                num //= 2
            elif num % 3 == 0:
                num //= 3
            elif num % 5 == 0:
                num //= 5
            else:
                return False
        return True