力扣之丑数 leetcode算法

题目描述丑数就是只包含质因数 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循环写法提交结果图