一.丑数

链接：丑数

分析：

• 丑数只有2，3，5这三个质因数，num = 2^a + 3^b + 5^c
• 也就是一个丑数是由若干个2，3，5组成，那么丑数除以这若干个数字最后一定变为1

代码

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;

        int[] factors = { 2, 3, 5 };
        for (int factor : factors)
            while (n % factor == 0)
                n /= factor;

        return n == 1;
    }
}

二.丑数II

链接：丑数II

分析

• 最容易想到的思路是暴力解法，因为在上一题中已经知道判断一个丑数的方法，但是时间复杂度太高，不能通过所有样例

暴力解法(无法通过所有样例)

class Solution {
    private boolean isUgly(int n) {
        int[] factors = {2,3,5};
        for(int factor : factors)
            while(n % factor == 0)
                n /= factor;

        return n == 1;
    }
    public int nthUglyNumber(int n) {
        int ret = 0, cnt = 0;
        for(int i = 1;;i++) {
            if(isUgly(i)) cnt++;
            if(cnt == n) return i;
        }
    }
}

• 要取出第n大的丑数，可以使用优先级队列来存储丑数，丑数非常容易获得，就是由前一个丑数分别乘2,3,5所得
• 首先创建最小堆，堆顶元素为最小的丑数
• 初始化最小堆，堆顶元素为最小的丑数1
• 取出堆顶元素x，第几次取出就是第几大的丑数
• x是丑数，那么2x，3x，5x也都是丑数，将这三个数存储到优先级队列之中
• 在这个过程中可能会出现重复元素，可以使用哈希表来去重
• 这样，当第n次取出堆顶元素x时，x就是第n大的丑数

代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> q = new PriorityQueue<>();

        set.add(1L);
        q.add(1L);

        for(int i = 1; i < n; i++) {
            long top = q.poll();
            for(int factor : factors){
                long next = top * factor;
                if(set.add(next))
                    q.add(next); 
            }
        }

        return (int)q.poll().longValue();
    }
}

注意：

1. 注意Long和long是不同的，Long是包装类，long是基本类型
2. Java中，基本类型之间可以直接进行强制类型转换(int x = (int)long)
3. 基本类型和其对应的包装类型在底层是通过方法进行转换的，但是在JDK5之后，编译器会自动帮助我们完成这个过程，也就是拆箱和装箱
4. 包装类不能直接转换为另一个包装类或原始数据类型，必须先进行拆箱或装箱
5. Long 不能直接转换为 int，因为它们是不同的类型，必须先将 Long 拆箱为 long，然后再转换为 int。
6. Long转化为long是通过longvalue方法实现

三.各位相加

链接：各位相加

分析

• 模拟思路：不断获得每一位，然后计算各位和，直到最后的结果是个位数

代码

class Solution {
    // 求各位和
    private int bitSum(int n) {
        int ret = 0;
        while (n > 0) {
            ret += n % 10;
            n /= 10;
        }

        return ret;
    }

    public int addDigits(int num) {
        int ret = num;
        while(ret / 10 != 0) {
            ret = bitSum(ret);
        }

        return ret;
    }
}

数学方法
看推导：

• 核心在于：num和其各位和 MOD9同余
• 进而推导出num和最后的结果MOD9同余

代码

class Solution {
    public int addDigits(int num) {
        if(num == 0) return 0;
        if(num % 9 == 0) return 9;
        return num % 9;
    }
}

四.计数质数

暴力解法(超时)

class Solution {
    private boolean isPrime(int n) {
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0)
                return false;
        }

        return true;
    }
    public int countPrimes(int n) {
        int cnt = 0;
        for(int i = 2; i < n; i++)
            if(isPrime(i))
                cnt++;
        return cnt;
    }
}

埃氏筛

• 核心：如果x是质数，则2x,3x,4x,5x…一定不是质数
• 利用这个原理就能灵活处理很多问题

代码

class Solution {
    public int countPrimes(int n) {
        int[] is_prime = new int[n];// 标记第i个数是否是质数
        Arrays.fill(is_prime,1);// 默认全是质数

        int ret = 0;// 记录结果
        for(int i = 2; i < n; i++) {
            if(is_prime[i] == 1) {
                ret += 1;
                if((long)i*i < n)
                    for(int k = i * i; k < n; k += i)
                        is_prime[k] = 0;
            }
        }

        return ret;
    }
}

线性筛

• 埃氏筛其实还存在冗余的地方，比如12这个数字，被2，4，6都删除过一次，这就是冗余操作，使用线性筛可以解决这个问题
• 线性筛的核心在于：对于一个数x，x乘以小于x的所有质数的结果一定是合数，将这些结果标记为非质数即可，但是发现这样的删除过程仍然存在冗余操作，问题及解决方案如下

代码：

class Solution {
    public int countPrimes(int n) {
        List<Integer> list = new ArrayList<>();// 存储之前出现的所有质数
        int[] is_prime = new int[n];
        Arrays.fill(is_prime,1);

        int ret = 0;
        for(int i = 2; i < n; i++) {
            if(is_prime[i] == 1){
                list.add(i);
                ret++;
            }

            for(int k : list){
                if(k*i >= n) break;
                is_prime[k*i] = 0;
                if(i % k == 0) break;// k是i的最小质因数
            }
        }

        return ret;
    }
}

三种算法的时间复杂度对比(数据量大)

• 线性筛 > 埃氏筛 > 暴力解法

对比实验：求2-n之间所有的质数
代码：

package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 打印2-n之间的所有质数
public class Demo2 {
    // 埃氏筛
    public static void Eratosthenes(int n) {
        List<Integer> list = new ArrayList<>();
        int[] is_prime = new int[n + 1];
        Arrays.fill(is_prime, 1);

        for(int i = 2; i <= n; i++) {
            if(is_prime[i] == 1){
                list.add(i);
                if((long)i*i <= n)
                    for(int k = i*i; k <= n; k += i)
                        is_prime[k] = 0;
            }
        }
    }

    // 暴力解法
    public static void isPrime(int n){
        List<Integer> list = new ArrayList<>();
        for(int i = 2; i<= n; i++){
            if(is_prime(i))
                list.add(i);
        }
    }

    private static boolean is_prime(int n){
        for(int i = 2; i <= Math.sqrt(n); i++)
            if(n % i == 0)
                return false;
        return true;
    }

    // 线性筛
    public static void Euler_prime(int n){
        List<Integer> list = new ArrayList<>();
        int[] is_prime = new int[n + 1];
        Arrays.fill(is_prime, 1);

        for(int i = 2; i <= n; i++) {
            if(is_prime[i] == 1)
                list.add(i);
            for(int k : list){
                if(k*i > n) break;
                is_prime[k*i] = 0;
                if(i % k == 0) break;// k是i的最小质因数
            }
        }
    }


    public static void main(String[] args) {
        int n = 200000000;
        long start1 = System.currentTimeMillis();
        Eratosthenes(n);
        long end1 = System.currentTimeMillis();
        System.out.println("埃氏筛时间:" + (end1 - start1));

        long start2 = System.currentTimeMillis();
        isPrime(n);
        long end2 = System.currentTimeMillis();
        System.out.println("暴力时间:" + (end2 - start2));

        long start3 = System.currentTimeMillis();
        Euler_prime(n);
        long end3 = System.currentTimeMillis();
        System.out.println("线性筛时间:" + (end3 - start3));
    }
}

打印结果：

• 只有当数据量特别大时，才符合上述时间复杂度的排序，对于计算机来说，取模%是一个非常耗时的操作