首页 > 其他 > 详细

ugly number

时间:2019-08-29 00:01:12      阅读:75      评论:0      收藏:0      [点我收藏+]

ugly number 是指质因数只有2, 3, 5的正整数。

1. 判断一个数是否为ugly number

bool isUgly(int num) {
        if(num <= 0) return false;
        if(num == 1) return true;
        while(num % 2 == 0) num /= 2;
        while(num % 3 == 0) num /= 3;
        while(num % 5 == 0) num /= 5;
        return num == 1;
    }

2.找第n个ugly number

int nthUglyNumber(int n) {
        if(n == 1) return 1;
        vector<int> k(n);
        k[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for(int i = 1; i < n; ++i){
            k[i] = min(k[p2] * 2, min(k[p3] * 3, k[p5] * 5));
            if(k[i] == k[p2] * 2) p2++;
            if(k[i] == k[p3] * 3) p3++;
            if(k[i] == k[p5] * 5) p5++;
        }
        return k[n - 1];
    }

3.super ugly number,质因数是给定的 一些质数primes,求第n个super ugly number,思路同第二题

int nthSuperUglyNumber(int n, vector<int>& primes) {
        if(n == 1) return 1;
        vector<int> k(n);
        k[0] = 1;
        int size = primes.size();
        vector<int> pointers(size, 0);
        for(int i = 1; i < n; ++i){
            int ki = INT_MAX;
            for(int j = 0; j < size; ++j){
                ki = min(ki, k[pointers[j]] * primes[j]);
                k[i] = ki;
            }
            for(int j = 0; j < size; ++j){
                if(k[i] == k[pointers[j]] * primes[j]) pointers[j]++;
            }
        }
        return k[n - 1];
    }

 

ugly number

原文:https://www.cnblogs.com/betaa/p/11427087.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!