题目描述
丑数 就是只包含质因数 2
、3
和 5
的正整数。
给你一个整数 n
,请你判断 n
是否为 丑数 。如果是,返回 true
;否则,返回 false
。
示例 1:
输入:n = 6
输出:true
解释:6 = 2 × 3
示例 2:
输入:n = 1
输出:true
解释:1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3:
输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。
力扣原题目地址:https://leetcode.cn/problems/...思路解法 题目不难,核心就是如何把一个数进行
分解
,如:6分解成2*
3、12分解成3*
4。不断按照2或3或5进行分解,直到分解不出来了(不能被2 3 5整除)。抽象即为:某个操作一直执行,直到符合某个条件才会停止下来。所以我们会相到使用
递归
,或者使用while循环
递归写法
在写代码之前,我们可以为了更好的理一下思路,可以使用枚举法,多举几个例子。如:
/**
* 0不是丑数
* 1是丑数
* 2是丑数
* 3是丑数
* 4是丑数 = 2 * 2
* 5是丑数
* 6是丑数 = 2 * 3
* 7不是丑数,没法被 2 3 5整除
* 8是丑数 = 2 * 4
* 9是丑数 = 3 * 3
* 10是丑数 = 2 * 5 或 5 * 2
* 11不是丑数,没法被 2 3 5整除
* */
所以我们为了代码的可读性更强一些,可以多写几个if判断,如下解法代码:
var isUgly = function (n) {
if (n == 0) { // 0 不是丑数
return false
} else if (n == 1 | n == 2 | n == 3 | n == 4 | n == 5) { // 1 是第一个丑数
return true // 2 3 4 5 也都是丑数
} else { // 从6开始做递归
if (n % 2 == 0) { // 能被2整除,继续分解(递归)
n = n / 2
return isUgly(n)
} else if (n % 3 == 0) { // 能被3整除,继续分解(递归)
n = n / 3
return isUgly(n)
} else if (n % 5 == 0) { // 能被5整除,继续分解(递归)
n = n / 5
return isUgly(n)
} else {
// 若是没法被2 3 5分解整除的数,就一定不是丑数,比如7 11 13等...
return false
}
}
}
递归写法提交结果图
文章图片
的确递归的性能,貌似不是非常好,不过可以作为我们
保命
解法,毕竟在面试的时候,常常精神状态不是非常好,首要是能把算法题做出来,再才是优化的解法while循环写法
思路类似,就是把数字的分解放在while循环中去了,如下代码
var isUgly = function (n) {
if (n === 0) { // 0 不是丑数
return false
} else if (n === 1 | n === 2 | n === 3 | n === 4 | n === 5) { // 1 是第一个丑数
return true // 2 3 4 5 也都是丑数
} else {// 从6开始做while循环分解
while (n % 2 === 0) {
n = n / 2
}
while (n % 3 === 0) {
n = n / 3
}
while (n % 5 === 0) {
n = n / 5
}
// 当一个大于等于6的数字被2 3 5不停的分解,最终的结果只有两个,要么是1,即分解到头了
// 要么不是1,说明没法分解了
// 如:10 / 2 == 55 / 5 == 1
// 如:17 被 2 3 5 没法分解,就不是1,故不是丑数
if (n === 1) {
return true
} else {
return false
}
}
}
while循环写法提交结果图
文章图片
对比上述两张图发现,的确是递归的性能差一些总结 以后大家遇到需要把一个大一些的数字不停的分解成小数字的情况,就可以考虑使用
递归
,或者使用while循环
【力扣之丑数】虽然
递归
在工作中偶尔用到,while循环
很少用到
数字中有丑数,鸭子群中有丑小鸭,在实际的生活中,由于基因、血统、传承、家族的缘故,丑小鸭是无法变成白天鹅的,但是丑小鸭也是要努力的啊,至少要成为一个不那么差的丑小鸭^_^
推荐阅读
- 力扣之加一
- 力扣之找不同
- 力扣之检查两个字符串数组是否相等
- 力扣之数组中数字出现的次数 II
- 优雅地翻转数组
- #yyds干货盘点# leetcode算法题( 删除有序数组中的重复项)
- #yyds干货盘点# leetcode算法题(括号生成)
- #yyds干货盘点# leetcode算法题(有效的括号)
- #yyds干货盘点# leetcode算法题(最长公共前缀)