leetcode 264.丑数

题目描述跳转去leetcode

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

来源：leecode：https://leetcode.cn/problems/ugly-number-ii/

解法1， 动态规划

1. 定义一个数组用来记录前n个丑数，最后返回数组中最后一个元素

class Solution {
    public int nthUglyNumber(int n) {
        // 创建
        int[] arr = new int[n];

        if(n<=6){
            return n;
        }else{
            int index = 6;
            int num = 7;
            int i = 0;
            //生成n个丑数
            while(index<n){
                if(i<6){
                    arr[i] = i+1;
                }else{
                    if(isUgly(num)){
                        arr[index] = num;
                        index++;
                    }
                    num++;
                }
               i++;
            }
        }
        return arr[n-1];

    }
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }

        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }

        return num == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

提交后显示超出时间限制！ 哦我的天
2. 优化代码
方法：使用三个指针来分别记录当前需要乘以2、3、5的丑数的下标。每次取出三个指针对应位置的丑数乘以对应的因子，得到三个候选的下一个丑数，选择其中最小的作为下一个丑数加入数组中，并更新对应的指针和候选丑数。这样就可以避免重复计算和判断每一个数字是否为丑数，降低时间复杂度。
小结：优化后的代码使用了动态规划来求解第 n 个丑数。
动态规划的基本思想是将原问题拆分成不同的子问题，通过求解子问题的最优解来得到原问题的最优解。在这个算法中，我们定义一个数组 arr 来存储前 n 个丑数，其中 arr[0] = 1。
接下来，我们维护三个指针 i2、i3 和 i5，分别指向数组中乘以 2、3 和 5 后得到的下一个丑数。同时，我们维护三个变量 num2、num3 和 num5，表示乘以对应因子后得到的丑数。
我们从第 1 个丑数开始，枚举从已有的丑数中乘以 2、3、5 得到的最小值，并将其加入数组 arr 中。然后，在三个变量 num2、num3 和 num5 中更新对应丑数的值，直到得到第 n 个丑数为止。

class Solution {
    public int nthUglyNumber(int n) {
        // 创建
        int[] arr = new int[n];
        arr[0] = 1; // 第一个丑数是1

        int i2 = 0, i3 = 0, i5 = 0;
        int num2 = 2, num3 = 3, num5 = 5;

        for (int i = 1; i < n; i++) {
            // 下一个丑数是从已有的丑数中乘以2、3、5得到的最小值
            int next = Math.min(num2, Math.min(num3, num5));
            arr[i] = next;

            // 更新num2、num3、num5的值
            if (next == num2) {
                i2++;
                num2 = arr[i2] * 2;
            }
            if (next == num3) {
                i3++;
                num3 = arr[i3] * 3;
            }
            if (next == num5) {
                i5++;
                num5 = arr[i5] * 5;
            }
        }

        return arr[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

最后结果可想而知，当然是通过啦！

解法2， 优先队列！（也是今天重点学习内容）

定义优先队列，用来计算当前最小丑数，最后返回队列中堆顶位置的元素
难点：：如何计算后续的丑数，看了题解才知道因为set具有数据不重复的特点，所以要使用set来记录，前n个的丑数，下一个丑数,其实是从已有的丑数中乘以2、3、5得到的最小值，如果set中没有上述乘积结果值就把值add进去。

class Solution {
    public int nthUglyNumber(int n) {
        // 创建
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(1); // 第一个丑数是1
        HashSet<Integer> set = new HashSet<>();
        set.add(1);

        int num = 1;
        int ugly = 1;
        int[] pers = new int[]{2, 3, 5};

        int u1 = -1, u2 = -1,u3 = -1;
        // 循环n次，找到第n个丑数
        for (int i = 1; i < n; i++) {
            // 取出当前最小丑数
            num = queue.poll();
            // 找下一个丑数, 下一个丑数是从已有的丑数中乘以2、3、5得到的最小值
            for(int per : pers){
                ugly = per*num;
                if(!set.contains(ugly)){
                    queue.offer(ugly);
                    set.add(ugly);
                }
            }

        }

        return queue.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

提交结果错误，排查发现是因为数据溢出的原因，因此要将int类型改成long

以下是改了类型的代码

class Solution {
    public int nthUglyNumber(int n) {
        // 创建
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.offer(1L); // 第一个丑数是1
        HashSet<Long> set = new HashSet<>();
        set.add(1L);

        Long num = 1L;
        long ugly = 1L;
        int[] pers = new int[]{2, 3, 5};

        // 循环n次，找到第n个丑数
        for (int i = 1; i < n; i++) {
            // 取出当前最小丑数
            num = queue.poll();
            // 找下一个丑数, 下一个丑数是从已有的丑数中乘以2、3、5得到的最小值
            for(int per : pers){
                ugly = per * num;
                if(!set.contains(ugly)){
                    queue.offer(ugly);
                    set.add(ugly);
                }
            }
        }

        return (int) queue.peek();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

点击执行~~~~， 糟糕，怎么又错了
可能出现这种情况的原因：

1. queue.peek() 返回的类型不是可以直接转换为 int 类型的基本数据类型。例如，如果 peek() 方法返回的是一个对象或字符串类型，使用 (int) 进行强制类型转换会报错。
2. 如果队列为空，即不存在任何对象，queue.peek() 将返回 null。在将 null 强制转换成 int 时，会出现 java.lang.NullPointerException 空指针异常错误，导致编译错误。
   满足第一种情况：Long是一个对象类型
   所以最后的代码如下：

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.offer(1L); // 第一个丑数是1
        HashSet<Long> set = new HashSet<>();
        set.add(1L);

        Long num = 1L;
        long ugly = 1L;
        int[] pers = new int[]{2, 3, 5};

        // 循环n次，找到第n个丑数
        for (int i = 1; i < n; i++) {
            // 取出当前最小丑数
            num = queue.poll();
            // 找下一个丑数, 下一个丑数是从已有的丑数中乘以2、3、5得到的最小值
            for(int per : pers){
                ugly = per * num;
                if(!set.contains(ugly)){
                    queue.offer(ugly);
                    set.add(ugly);
                }
            }
        }

        long val = queue.peek();
        if (val > Integer.MAX_VALUE || val < Integer.MIN_VALUE) {
            throw new ArithmeticException("Value is out of range for an int.");
        }
        return (int) val;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最后提交结果当然是成功的啦！