共计 1756 个字符,预计需要花费 5 分钟才能阅读完成。
题目形容
丑数 就是只蕴含质因数 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 == 5 5 / 5 == 1
// 如:17 被 2 3 5 没法合成,就不是 1,故不是丑数
if (n === 1) {return true} else {return false}
}
}
while 循环写法提交后果图
比照上述两张图发现,确实是递归的性能差一些
总结
当前大家遇到须要把一个大一些的数字不停的分解成小数字的状况,就能够思考应用 递归
,或者应用while 循环
尽管 递归
在工作中偶然用到,while 循环
很少用到
数字中有丑数,鸭子群中有丑小鸭,在理论的生存中,因为基因、血统、传承、家族的缘故,丑小鸭是无奈变成白天鹅的,然而丑小鸭也是要致力的啊,至多要成为一个不那么差的丑小鸭
^_^
正文完