程序员面试题精选100题（37）-寻找丑数[算法]
字号：小|大
2019-09-22 FW.5VV.CN范文网题目：我们把只包含因子
2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。
基于前面的分析，我们可以写出如下的函数来判断一个数是不是丑数：
bool IsUgly(int number)
{
while(number % 2 == 0)
number /= 2;
while(number % 3 == 0)
相关文章
- 程序员面试题精选100题（03）－第一个只出现一次的字符[算法]
- 程序员面试题精选100题（21）－左旋转字符串[算法]
- 程序员面试题精选100题（24）－栈的push、pop序列[数据结构]
- 程序员面试题精选100题（26）-和为n连续正数序列[算法]
- 程序员面试题精选100题（32）-不能被继承的类[C/C++/C#]
- 程序员面试题精选100题（46）－对称子字符串的最大长度[算法]
- 程序员面试题精选100题（04）－把字符串转换成整数
- 程序员面试题精选100题（10）－排序数组中和为给定值的两个数字[算法]
- 程序员面试题精选100题（16）－O（logn）求Fibonacci数列[算法]
- 程序员面试题精选100题（17）－把字符串转换成整数[算法]
热门推荐
- 程序员面试题精选100题（03）－第一个只出现一次的字符[算法]
- 程序员面试题精选100题（21）－左旋转字符串[算法]
- 程序员面试题精选100题（24）－栈的push、pop序列[数据结构]
- 程序员面试题精选100题（26）-和为n连续正数序列[算法]
- 程序员面试题精选100题（32）-不能被继承的类[C/C++/C#]
- 程序员面试题精选100题（46）－对称子字符串的最大长度[算法]
- 程序员面试题精选100题（04）－把字符串转换成整数
- 程序员面试题精选100题（10）－排序数组中和为给定值的两个数字[算法]
- 程序员面试题精选100题（16）－O（logn）求Fibonacci数列[算法]
- 程序员面试题精选100题（17）－把字符串转换成整数[算法]
