力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0263. 丑数
题目地址(263. 丑数)
https://leetcode-cn.com/problems/ugly-number/
题目描述
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 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0232. 用栈实现队列
下一个
0283. 移动零
最近更新
1yr ago
复制链接
内容
题目地址(263. 丑数)
题目描述
前置知识
公司
思路
关键点
代码