LeetCode题练习与总结：丑数--263
一、题目描述
丑数 就是只包含质因数 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 。
提示：
-2^31 <= n <= 2^31 - 1
二、解题思路
- 首先判断 n 是否为正整数，如果不是，则直接返回 false。
- 不断将 n 除以 2、3、5，直到 n 不能被这三个数整除为止。
- 如果最后 n 等于 1，则说明 n 只包含质因数 2、3、5，返回 true；否则，返回 false。
三、具体代码
class Solution {public boolean isUgly(int n) {// 判断 n 是否为正整数if (n <= 0) {return false;}// 不断将 n 除以 2、3、5，直到 n 不能被这三个数整除为止for (int factor : new int[]{2, 3, 5}) {while (n % factor == 0) {n /= factor;}}// 如果最后 n 等于 1，则返回 true；否则，返回 falsereturn n == 1;}
}
以上代码中，我们首先判断 n 是否为正整数，然后使用一个 for 循环和一个 while 循环来不断将 n 除以 2、3、5。如果最后 n 等于 1，则说明 n 只包含质因数 2、3、5，返回 true；否则，返回 false。
四、时间复杂度和空间复杂度
1. 时间复杂度
代码中的主要操作是循环除以 2、3、5，直到 n 不能被这三个数整除为止。假设 n 的质因数分解为 n = 2^a x 3^b x 5^c x d，其中 d 是除了 2、3、5 以外的质因数（如果有的话）。
- 第一个循环，当 n 能被 2 整除时，n 会除以 2，直到 n 不能被 2 整除。这需要最多 a 次操作。
- 第二个循环，当 n 能被 3 整除时，n 会除以 3，直到 n 不能被 3 整除。这需要最多 b 次操作。
- 第三个循环，当 n 能被 5 整除时，n 会除以 5，直到 n 不能被 5 整除。这需要最多 c 次操作。
因此，总的操作次数是 a + b + c，即 n 中 2、3、5 的质因数个数之和。在最坏的情况下，n 是 2、3、5 的幂，那么 a、b、c 可以达到 log_2(n)、log_3(n)、log_5(n)的数量级。因此，时间复杂度可以表示为 O(log_2(n) + log_3(n) + log_5(n))。由于对数函数的增长速度远低于线性函数，我们可以简化时间复杂度为 O(log n)。
2. 空间复杂度
代码中使用的额外空间主要是常数空间，即用于存储质因数 2、3、5 的数组。这个数组的大小是固定的，不随输入 n 的大小而变化。因此，空间复杂度为 O(1)。
五、总结知识点
-
类定义：
class Solution：定义了一个名为Solution的类。
-
方法定义：
public boolean isUgly(int n)：定义了一个名为isUgly的公共方法，它接受一个整数参数n并返回一个布尔值。
-
条件判断：
if (n <= 0)：使用了if语句来检查n是否小于或等于 0，用于判断n是否为正整数。
-
循环结构：
for (int factor : new int[]{2, 3, 5})：使用了增强型for循环（也称为“for-each”循环）来遍历一个整数数组，该数组包含质因数 2、3、5。
-
数学运算：
%：取模运算符，用于判断一个数是否能被另一个数整除。/=：除法赋值运算符，用于将一个数除以另一个数，并将结果赋值给原数。
-
逻辑运算：
while (n % factor == 0)：while循环用于在n能被factor整除的情况下重复执行循环体内的代码。
-
返回值：
return false;和return n == 1;：根据条件返回布尔值true或false。
-
数组初始化：
new int[]{2, 3, 5}：使用数组初始化语法创建并初始化一个整数数组。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。