首页 > 代码库 > [LeetCode]Ugly Number
[LeetCode]Ugly Number
题目：Ugly Number
正数中质因子只有2,3,5的数被称为"丑数"。判断一个数是不是"丑数"。
例如前十个最小的丑数：1 2 3 4 5 6 8 9 10 12
思路：
合数能表示成质数的积的形式，所以，丑数必然是只有2,3,5的因子。
bool LeetCode::isUgly(int num){ for (size_t i = 2; i < 6 && num; i++){ while (!(num % i)) num /= i;//循环除以[2,6]的数，最后为1，则是丑数 } return num == 1; }
题目：Ugly Number II
找到第n个丑数。
思路：
从第一个丑数开始向上找，知道找到第n个。
由上面的分析可以知道，丑数只是有2,3,5的因子，所以可以用2,3,5分别乘以一个丑数来得到新的丑数。
按照这种方式从小到大的求丑数，就可以了。
int LeetCode::nthUglyNumber(int n){ if (n < 1)return 0; vector<int>uglys;//保存求出的丑数 uglys.push_back(1); uglys.push_back(2); uglys.push_back(3); uglys.push_back(4); uglys.push_back(5);//前5个丑数 if (n <= 5)return uglys.at(n - 1); int i2 = 2, i3 = 1, i5 = 1;//2,3,5分别乘以的uglys中的丑数的下标 n -= 5; while (n){//求出第n个跳出循环 int temp = min(uglys.at(i2) * 2, uglys.at(i3) * 3); temp = min(temp, uglys.at(i5) * 5);//找到最小的丑数 uglys.push_back(temp); //因为可能是这三个数中的两个或三个的到的乘积，所以不能用else if if (temp == uglys.at(i2) * 2)++i2;//判断是哪个2得到的新的丑数 if (temp == uglys.at(i3) * 3)++i3;//判断是哪个3得到的新的丑数 if (temp == uglys.at(i5) * 5)++i5;//判断是哪个5得到的新的丑数 --n; } return uglys.at(uglys.size() - 1); }
[LeetCode]Ugly Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。