乐趣区

关于leetcode:力扣之丑数

题目形容

丑数 就是只蕴含质因数 235 的正整数。

给你一个整数 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 循环 很少用到

数字中有丑数,鸭子群中有丑小鸭,在理论的生存中,因为基因、血统、传承、家族的缘故,丑小鸭是无奈变成白天鹅的,然而丑小鸭也是要致力的啊,至多要成为一个不那么差的丑小鸭^_^

退出移动版