Vison's Blog
所有文章
文章总览
编辑器
Publications
About Me
Search
目录
#toc-container
下载Markdown文件
【4.10】LeetCode每日一题·丑数
2021年04月10日 16时23分
标签：
LeetCode
数学
## 题目描述 给你一个整数n，请你判断n是否为**丑数**。如果是，返回**true**；否则，返回**false**。 丑数 就是**只包含质因数2、3和/或5**的**正整数**。 #### 示例1 ``` 输入：n = 6 输出：true 解释：6 = 2 × 3 ``` #### 示例2 ``` 输入：n = 8 输出：true 解释：8 = 2 × 2 × 2 ``` #### 示例3 ``` 输入：n = 14 输出：false 解释：14 不是丑数，因为它包含了另外一个质因数 7 。 ``` #### 示例4 ``` 输入：n = 1 输出：true 解释：1 通常被视为丑数。 ``` #### 提示 ``` -2^31 <= n <= 2^31 - 1 ``` #### 来源 > 来源：力扣（LeetCode） > 链接：[题目链接](https://leetcode-cn.com/problems/ugly-number/ "题目链接") ## 解题思路 * 根据定义，非正整数都不是**丑数**，首先对此进行判断。 * 然后对输入进行质因数分解，如果发现其有2，3或5的因数，就将其除掉； * 最后判断剩下的数是否为**1**即可，如果为**1**，则说明该数的质因数只有2、3或5，否则说明还有其他质因数。 注意点⚠️：代码中需要注意输入范围，对非正整数进行特判。否则对于输入为**0**的情况，会进入无限循环而超时。 ## 代码 ```cpp class Solution { public: bool isUgly(int n) { if(n <= 0) return false; while(n % 2 == 0) n /= 2; while(n % 3 == 0) n /= 3; while(n % 5 == 0) n /= 5; return n == 1; } }; ``` ## 用时和内存 > 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户 > 内存消耗：5.8 MB，在所有 C++提交中击败了56.44%的用户
所有评论
暂无评论
新增评论
评论
邮箱
邮箱仅作验证使用
图形验证码
邮箱验证码
发送验证码
发表评论
所有评论
暂无评论