leetcode 263. Ugly Number 、264. Ugly Number II 、313. Super Ugly Number 、204. Count Primes

时间：2023-12-15 09:12:56

263. Ugly Number

注意：1.小于等于0都不属于丑数

　　　 2.while循环的判断不是num >= 0, 而是能被2 、3、5整除，即能被整除才去除这些数

class Solution {

public:

    bool isUgly(int num) {

        if(num <= )

            return false;

        while(num %  == )

            num /= ;

        while(num %  == )

            num /= ;

        while(num %  == )

            num /= ;

        return num ==  ? true : false;

    }

};

264. Ugly Number II

用一个数组去存第n个前面的所有整数，然后记录2 、3、5当前数的索引，每次选择最小的数。注意每次满足最小数，是索引加1，不是数值本身加1

class Solution {

public:

    int nthUglyNumber(int n) {

        int result[n + ];

        result[] = ;

        int index = ,index2 = ,index3 = ,index5 = ;

        while(index < n){

            index++;

            int num2 = result[index2] * ;

            int num3 = result[index3] * ;

            int num5 = result[index5] * ;

            int min_num = min(num2,min(num3,num5));

            result[index] = min_num;

            if(num2 == min_num)

                index2++;

            if(num3 == min_num)

                index3++;

            if(num5 == min_num)

                index5++;

        }

        return result[n];

    }

};

313. Super Ugly Number

这个和Ugly Number II 几乎是一样的，不同的是Ugly Number II是固定了2 、3、5这三个数，这个题是给一个数组。

class Solution {

public:

    int nthSuperUglyNumber(int n, vector<int>& primes) {

        int result[n+];

        result[] = ;

        vector<int> index(primes.size(),);

        int ind = ;

        while(ind < n){

            ind++;

            int min_num = INT_MAX;

            for(int i = ;i < primes.size();i++)

                min_num = min(result[index[i]] * primes[i],min_num);

            result[ind] = min_num;

            for(int i = ;i < primes.size();i++){

                if(result[index[i]] * primes[i] == min_num)

                    index[i]++;

            }

        }

        return result[n];

    }

};

204. Count Primes

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

这个题跟丑数的题一样，也需要用数组存。

思路：用j=2一个一个乘以质数i，只要乘到的值都不是质数，因为质数只能是1和他本身

class Solution {

public:

    int countPrimes(int n) {

        if(n <= )

            return ;

        vector<bool> flag(n+,true);

        int count = ;

        for(int i = ;i < n;i++){

            if(flag[i] == true){

                count++;

                for(int j = ;j*i < n;j++)

                    flag[j*i] = false;

            }

        }

        return count;

    }

};

https://www.jianshu.com/p/12c0e91c696e

https://blog.csdn.net/github_39261590/article/details/73864039 图解

更新代码：　　　

　　　　如果问题变成：求不超过10000的最大质数？用最快方法找到1到10000的质数？

　　　　只要把上面代码里面为false的坐标+1就可以得到，但是有个问题，子循环是j=1开始的，也就是会把当前的质数也变成true，对于计算个数问题不大，但是你如果要再把这些提取出来就错误了，从2开始才是真正可以泛化到其他两个问题的通用代码

相关文章