您现在的位置是:首页 >其他 >leetcode 264.丑数网站首页其他

leetcode 264.丑数

daladalabao 2024-07-01 11:59:47
简介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;
    }
}

提交后显示超出时间限制! 哦我的天在这里插入图片描述
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];
    }
}

最后结果可想而知,当然是通过啦!
在这里插入图片描述

解法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();
    }
}

提交结果错误,排查发现是因为数据溢出的原因,因此要将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. 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;
    }
}

最后提交结果当然是成功的啦!在这里插入图片描述

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。