Day16打卡,一起来刷题吧~
每日微信群推送题目->文章题解->探讨交流~
类别题目汇总及模板也在推出中~
今日题目263题,每日一题微信交流群可以点击右下角:合作转载->联系我,拉你入群。
题目:给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1:
输入:n = 6
输出:true
解释:6 = 2 × 3
题解:
注意输入是负数的n与为0的n都不是丑数。
如果n是正整数,那么我们需要对2、3、5进行整除,具体顺序可以变化,因为丑数的构成满足乘法交换律。
不断迭代除以2、3、5,直到最后剩余1。
class Solution {
public:
bool isUgly(int n) {
if (n <= 0) return false;
while (!(n % 2)) {
n /= 2;
}
while (!(n % 3)) {
n /= 3;
}
while (!(n % 5)) {
n /= 5;
}
return n == 1;
}
};
递归写法:
class Solution {
public:
bool isUgly(int n) {
if (n <= 0) return false;
if (!(n%2)) return isUgly(n/2);
if (!(n%3)) return isUgly(n/3);
if (!(n%5)) return isUgly(n/5);
return n == 1;
}
};