C++版 - 剑指offer 面试题34：寻找丑数(Leetcode 263.Ugly number)解题报告

剑指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.