剑指offer 面试题34:寻找丑数 题目:把质数因子只包含2、3和5的正整数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。请按从小到大的顺序的第N个丑数。(据说google曾经采用过这道题。) 提交网址: http://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186
或 http://ac.jobdu.com/problem.php?pid=1214
输入:
输入包括一个整数N(1<=N<=1500)。
输出: 可能有多组测试数据,对于每组数据, 输出第N个丑数。 样例输入:
3
样例输出: 3 分析:
所谓一个数m是另一个数n的因子,是指n能被m整除,也就是n % m == 0。根据丑数的定义,丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除,我们把它连续除以2;如果能被3整除,就连续除以3;如果能被5整除,就除以连续5。如果最后我们得到的是1,那么这个数就是丑数,否则不是。
如果p是丑数,那么p=2^x * 3^y * 5^z,那么只要赋给x,y,z不同的值就能得到不同的丑数。 如果目前数组中最大的丑数是M,那么它后面的丑数应该由它前面的某个丑数*(2或3或5)而得来… NewUglyNum=(2 || 3 || 5)*M
AC代码:
#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
int GetUglyNumber_Solution(int index) {
vector<int> ugly(index, -1);
if(index<=0) return 0;
int idx2=0, idx3=0, idx5=0, i=1;
ugly[0]=1;
while(i<index)
{
int new2=ugly[idx2]*2;
int new3=ugly[idx3]*3;
int new5=ugly[idx5]*5;
int tempVal=min(min(new2,new3), new5);
if(tempVal==new2) idx2++;
if(tempVal==new3) idx3++;
if(tempVal==new5) idx5++;
ugly[i]=tempVal;
i++;
}
return ugly[index-1];
}
};
// 以下为测试
int main()
{
Solution sol;
int n1=11;
int n2=8;
int res1 = sol.GetUglyNumber_Solution(n1);
int res2 = sol.GetUglyNumber_Solution(n2);
printf("%d\n",res1);
printf("%d\n",res2);
return 0;
}
263. Ugly Number
Total Accepted: 55298 Total Submissions: 150561 Difficulty: Easy
提交网址: https://leetcode.com/problems/ugly-number/
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
. For example, 6, 8
are ugly while 14
is not ugly since it includes another prime factor7
.
Note that 1
is typically treated as an ugly number.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
AC代码:
class Solution {
public:
bool isUgly(int num) {
if(num<1) return false;
while(num %2 == 0) num >>= 1;
while(num%3==0) num /= 3;
while(num%5==0) num /= 5;
if(num==1) return true;
else return false;
}
}
313. Super Ugly Number
Total Accepted: 13458 Total Submissions: 39310 Difficulty: Medium
提交网址: https://leetcode.com/problems/super-ugly-number/
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.