【LeetCode每日一题】263. 丑数
【LeetCode每日一题】263. 丑数
公众号guangcity
发布于 2021-04-22 14:52:36
发布于 2021-04-22 14:52:36
文章被收录于专栏：光城(guangcity)
【LeetCode每日一题】263. 丑数
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;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
