0263. 丑数

题目地址(263. 丑数)

题目描述

1
编写一个程序判断给定的数是否为丑数。
2
3
丑数就是只包含质因数 2, 3, 5 的正整数。
4
5
示例 1:
6
7
输入: 6
8
输出: true
9
解释: 6 = 2 × 3
10
示例 2:
11
12
输入: 8
13
输出: true
14
解释: 8 = 2 × 2 × 2
15
示例 3:
16
17
输入: 14
18
输出: false
19
解释: 14 不是丑数,因为它包含了另外一个质因数 7。
20
说明:
21
22
1 是丑数。
23
输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
Copied!

前置知识

  • 数学
  • 因数分解

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

题目要求给定一个数字,判断是否为“丑陋数”(ugly number), 丑陋数是指只包含质因子 2, 3, 5 的正整数。
263.ugly-number
根据定义,我们将给定数字除以 2、3、5(顺序无所谓),直到无法整除。 如果得到 1,说明是所有因子都是 2 或 3 或 5,如果不是 1,则不是丑陋数。
这就好像我们判断一个数字是否为 n(n 为大于 1 的正整数)的幂次方一样,我们只需要 不断除以 n,直到无法整除,如果得到 1,那么就是 n 的幂次方。 这道题的不同在于 它不再是某一个数字的幂次方,而是三个数字(2,3,5),不过解题思路还是一样的。
转化为代码可以是:
1
while (num % 2 === 0) num = num / 2;
2
while (num % 3 === 0) num = num / 3;
3
while (num % 5 === 0) num = num / 5;
4
5
return num === 1;
Copied!
我下方给出的代码是用了递归实现,只是给大家看下不同的写法而已。

关键点

  • 数论
  • 因数分解

代码

  • 语言支持:JS, C++, Java, Python
Javascript Code:
1
/*
2
* @lc app=leetcode id=263 lang=javascript
3
*
4
* [263] Ugly Number
5
*/
6
/**
7
* @param {number} num
8
* @return {boolean}
9
*/
10
var isUgly = function (num) {
11
// TAG: 数论
12
if (num <= 0) return false;
13
if (num === 1) return true;
14
15
const list = [2, 3, 5];
16
17
if (list.includes(num)) return true;
18
19
for (let i of list) {
20
if (num % i === 0) return isUgly(Math.floor(num / i));
21
}
22
return false;
23
};
Copied!
复杂度分析
  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(logN)$
C++ Code:
1
class Solution {
2
public:
3
bool isUgly(int num) {
4
int ugly[] = {2,3,5};
5
for(int u : ugly)
6
{
7
while(num%u==0 && num%u < num)
8
{
9
num/=u;
10
}
11
}
12
return num == 1;
13
}
14
};
Copied!
Java Code:
1
class Solution {
2
public boolean isUgly(int num) {
3
int [] ugly = {2,3,5};
4
for(int u : ugly)
5
{
6
while(num%u==0 && num%u < num)
7
{
8
num/=u;
9
}
10
}
11
return num == 1;
12
}
13
}
Copied!
Python Code:
1
# 非递归写法
2
class Solution:
3
def isUgly(self, num: int) -> bool:
4
if num <= 0:
5
return False
6
for i in (2, 3, 5):
7
while num % i == 0:
8
num /= i
9
return num == 1
Copied!
复杂度分析
  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。