静态网站代做,中山企业门户网站建设,网站设计拓扑图,什么网站算是h5做的一、题目描述
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n #xff0c;请你判断 n 是否为 丑数 。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 示例 1#xff1a;
输入#xff1a;n 6
输出#xff1a;true
解释#xff1…一、题目描述
丑数 就是只包含质因数 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}使用数组初始化语法创建并初始化一个整数数组。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
