算法题每日一练---第76天：丑数 l-阿里云开发者社区

算法题每日一练---第76天：丑数 l

2022-04-13 138

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 丑数就是只包含质因数 2、3 和 5 的正整数。

一、问题描述

丑数就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为 **丑数 ** 。如果是，返回 true ；否则，返回 false 。

题目链接：丑数 l

二、题目要求

样例 1

输入： n = 6
输出： true
解释： 6 = 2 × 3

样例 2

输入： n = 1
输出： true
解释： 1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。

考察

贪心、模拟
建议用时15~35min

三、问题分析

这一题其实简单判断就行了，比如我一开始的想法就是看看这个数字能否被若干个 2 3 5相乘得到，如果可以的话，就返回true，否则返回false。

我最初写的代码有点长，但很容易理解。

后来发现，这种方法还可以优化，三重循环嵌套太差劲了。

优化

思想还是这一个思想，只不过是把三重循环分成各自独立的。

n是2的倍数，进入循环/2n是3的倍数，进入循环/3n是5的倍数，进入循环/5

四、编码实现

1.初始版本

classSolution {
public:
boolisUgly(intn) {//（●＞ω＜●）inti,j,k,a,b,c;//初始化数据for(i=0;pow(2,i)<=n;i++)//判断有几个2        {
a=pow(2,i);
for(j=0;pow(3,j)<=n/a;j++)//判断有几个3            {
b=pow(3,j);
for(k=0;pow(5,k)<=n/(a*b);k++)//判断有几个5                {
c=pow(5,k);
if(a*b*c==n)//如果能够构成，返回truereturntrue;
                }
            }
        }
returnfalse;//不能构成，返回false    }
};

2.优化后

classSolution {
public:
boolisUgly(intn) {
if(n<1) returnfalse;//n为0,返回falsewhile(n%2==0)   n=n/2;//进入2循环while(n%3==0)   n=n/3;//进入3循环while(n%5==0)   n=n/5;//进入5循环if(n==1)//结果是1，那么肯定能被2 3 5组成returntrue;
else//否则不能returnfalse;
    }
};