【剑指Offer】个人学习笔记_49_丑数

目录

• • 题目：
  • • • [剑指 Offer 49. 丑数](https://leetcode-cn.com/problems/chou-shu-lcof/)
      • 题目分析
  • 初始解答：
  • 学习他人：
  • • 方法一:
    • 方法二：
    • 方法三：
    • 方法四：
  • 总结

刷题日期：下午7:51 2021年5月13日星期四

个人刷题记录，代码收集，来源皆为leetcode

经过多方讨论和请教，现在打算往Java方向发力

主要答题语言为Java

题目：

剑指 Offer 49. 丑数

难度中等157

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
           

说明:

1. 1

   是丑数。

2. n

   不超过1690。

题目分析

这题只能靠找规律了，要么就只能遍历，求出所有的丑数的序列，然后再返回序列的最后一个值。

初始解答：

class Solution {
    public int nthUglyNumber(int n) {
        int[] res = new int[n + 1]; //结果
        int x = 1, i = 1; //计数
        res[0] = 1; //初始化
        while(res[n] == 0){
            i++;
            if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 ) {
                res[x] = i;
                x++;
            }
        }
        return res[x-2];
    }
}
           

只能跑的通测试用例，但是再往后数就没办法了，14这种即有2又有7的就不算了吗。

也算是动态规划题目了吧，慢慢往后遍历找的，学习K神

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0; //三指针
        int[] dp = new int[n]; //存结果的序列
        dp[0] = 1; //初始化
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5); //求最小
            if(dp[i] == n2) a++; //用了哪个就把哪个过了
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}
           

执行结果： 通过

显示详情 添加备注

执行用时：2 ms, 在所有 Java 提交中击败了99.24%的用户

内存消耗：37.4 MB, 在所有 Java 提交中击败了86.97%的用户

学习他人：

方法一:

宝石L2 2020-02-16 Java 题解 简单明了

这个题用三指针，第一个丑数是1，以后的丑数都是基于前面的小丑数分别乘2，3，5构成的。我们每次添加进去一个当前计算出来个三个丑数的最小的一个，并且是谁计算的，谁指针就后移一位。

public int nthUglyNumber(int n) {
        
        if (n <= 0)
            return -1;
        int[] dp = new int[n];
        dp[0] = 1;
        int id2 = 0, id3 = 0, id5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[id2] * 2, Math.min(dp[id3] *3, dp[id5] * 5));
            // 这里不用else if的原因是有可能id2(3) * 2 == id3(2) * 3
            // 这种情况两个指针都要后移
            if (dp[id2] * 2 == dp[i])
                id2 += 1;
            if (dp[id3] * 3 == dp[i])
                id3 += 1;
            if (dp[id5] * 5 == dp[i])
                id5 += 1; 
        }
        return dp[n - 1];
    }
           

方法二：

Nakangzi 2020-04-19 java

class Solution {
    public int nthUglyNumber(int n) {
        int[]nums =new int[n];
        nums[0]=1;
        int index2=0,index3=0,index5=0;
        for(int i=1;i<nums.length;i++){
            nums[i]=Math.min(nums[index2]*2,Math.min(nums[index3]*3,nums[index5]*5));
            if(nums[i]==nums[index2]*2)index2++;
            if(nums[i]==nums[index3]*3)index3++;
            if(nums[i]==nums[index5]*5)index5++;
        }
        return nums[n-1];
    }
}
           

方法三：

不是秒针L1

（编辑过）2020-10-05

我的一点理解： 在已有的丑数序列上每一个数都必须乘2， 乘3， 乘5， 这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, …, n1, n2], 如果单纯的让每个丑数乘2， 乘3， 乘5顺序排列的话肯定会有问题，

比如如果按照这样的顺序排列下去肯定有问题[1 * 2 , 1 * 3, 1 * 5 , 2 * 2, 2 * 3, 2 * 5, 3 * 2, 3 * 3, 3*5, … , n1 2, n1 * 3, n1 * 5, n2 * 2, n3 3, n2 * 5]，因为后面乘2的数据可能会比前面乘3乘5的数据要小，那这个乘2的数应该排在他们的前面， 后面乘3的数据也可能比前面乘5的数据要小，那这个乘3的数应该排在他们的前面。

那怎么办呢，每个数都必须乘2， 乘3， 乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序，这个改如何同时实现呢？

通过观察网上的各个题解，终于找到了办法，那就是记录每个丑数是否已经被乘2， 乘3， 乘5了， 具体的做法是

设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数；

对于某个状态下的丑数序列，我们知道此时第a个数还没有乘2(有没有乘3或者乘5不知道）， 第b个数还没有乘3(有没有乘2或者乘5不知道），第c个数还没有乘5(有没有乘2或者乘3不知道), 下一个丑数一定是从第a丑数乘2， 第b个数乘3， 第c个数乘5中获得，他们三者最小的那个就是下个丑数。

求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2得到的，还是某个数乘3得到的，又或是说某个数通过乘5得到的。我们可以比较一下这个新的丑数等于究竟是等于第a个丑数乘2, 还是第b个数乘3， 还是第c个数乘5， 通过比较我们肯定可以知道这个新的丑数到底是哪个数通过乘哪个数得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，下次应该乘2的是第 （a+1） 个数, 所以a++；如果新的丑数是通过第b个数乘3得到的, 说明此时第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数，此时我们可以说前 b 个数都已经乘过一次3了，下次应该乘3的是第 （b+1） 个数, 所以 b++；同理，如果这个这个新的丑数是通过第c个数乘5得到的, 那么c++;

但是注意，如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5， 说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b都应该加一， 因为此时第a个数已经通过乘2得到了一个新的丑数，第b个数已经通过乘3得到了一个新的丑数, 只不过这两个数相等而已。所以我们给计数器加一的时候不能使用 if else else if， 而应该使用if, if, if, 这样才不会把应该加一的计数器漏掉

经过n次循环，就能得到第n 个丑数了。

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];  // 使用dp数组来存储丑数序列
        dp[0] = 1;  // dp[0]已知为1
        int a = 0, b = 0, c = 0;    // 下个应该通过乘2来获得新丑数的数据是第a个， 同理b, c

        for(int i = 1; i < n; i++){
            // 第a丑数个数需要通过乘2来得到下个丑数，第b丑数个数需要通过乘2来得到下个丑数，同理第c个数
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2){
                a++; // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            }
            if(dp[i] == n3){
                b++; // 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
            }
            if(dp[i] == n5){
                c++; // 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
            }
        }
        return dp[n-1];
    }
}
           

方法四：

K神 解题思路：

丑数的递推性质： 丑数只包含因子 2, 3, 52,3,5 ，因此有 “丑数 == 某较小丑数 \times× 某因子” （例如：10 = 5 \times 210=5×2）。

作者：jyd

链接：https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/

来源：力扣（LeetCode）

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}
           

总结

以上就是本题的内容和学习过程了，基本只有一种解法，想要正确解答就得三个指针来确定下一位到底是多少，还得有求最小的过程，合理调库很重要

欢迎讨论，共同进步。