leetcode264丑数

2023-03-14 21:20 11阅读 0赞

丑数就是质因数只包含 2, 3, 5 的正整数  
输入: n = 10  
输出: 12  
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

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

思想：
    1.三指针法，p2,p3,p5保存2，3，5的乘积位置
    2.min=min_three(nums[p2]*2,nums[p3]*3,nums[p5]*5)
    当min=(nums[p2]*2,nums[p3]*3,nums[p5]*5)时，相应的指针增加，
    3.注意增加指针的时候，如果相同的话，全部都要增加，即if,if,if 非if,else if, else

class Solution {
    public:
        int min_three(int a,int b,int c)
        {
            int temp;
            temp=a>b?b:a;
            temp=temp<c?temp:c;
            return temp;
        } 
        int nthUglyNumber(int n) {
            int dp[n+1];
            dp[1]=1;
            int p2=1,p3=1,p5=1,i;
            for(i=2;i<=n;i++)
            {
                dp[i]=min_three(dp[p2]*2,dp[p3]*3,dp[p5]*5);
                cout<<i<<" "<<dp[i]<<endl;
                if(dp[i]==dp[p2]*2) p1++;
                if(dp[i]==dp[p3]*3) p2++;
                if(dp[i]==dp[p5]*5) p3++;
            }
            return dp[n];   
        }
    };

2 2
    3 3
    4 4
    5 5
    6 6
    7 8
    8 9
    9 10
    10 12

文章版权声明：注明蒲公英云原创文章，转载或复制请以超链接形式并注明出处。

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关丑数

列表res按序存储丑数 res\[0\] = 1，下一个丑数产生规则： 1.找出res所有数\2 中第一个大于 res \[-1\] 的数：res\[n2\] 2

迷南。/ 2022年01月30日 15:43/ 0 赞/ 62 阅读

相关丑数

时间限制：1秒空间限制：32768K 热度指数：223966 本题知识点：数组算法知识视频讲解题目描述把只包含质因子2、3和5的数称作丑数（Ugly

本是古典何须时尚/ 2022年03月09日 18:50/ 0 赞/ 83 阅读

相关 LeetCode——丑数

题目：编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 `2, 3, 5` 的正整数。示例 1: 输入: 6 输出: true 解

╰+哭是因爲堅強的太久メ/ 2022年03月27日 21:42/ 0 赞/ 64 阅读

相关【LeetCode】263. 丑数

题目链接：[https://leetcode-cn.com/problems/ugly-number/description/][https_leetcode-cn.com_p

骑猪看日落/ 2022年04月22日 07:26/ 0 赞/ 17 阅读

相关【LeetCode】264. 丑数 II

题目链接：[https://leetcode-cn.com/problems/ugly-number-ii/description/][https_leetcode-cn.co

小鱼儿/ 2022年04月22日 07:26/ 0 赞/ 22 阅读

相关丑数

求第1500个丑数。丑数是不能被2.3.5之外的其他素数整除的数，把丑数从小到大排起来，然后打印第1500个先写一个典例，我写的， //这是我写的，运行了大概15

你的名字/ 2022年05月18日 18:55/ 0 赞/ 34 阅读

相关丑数

把只包含因子2、3和5的数称作丑数，例如6，8都是丑数，但14不是，因为它包含因子7，习惯上我们把1当作第一个丑数，求按从小到大的顺序的第N个丑数。输入描述：整数N

小咪咪/ 2022年06月08日 16:52/ 0 赞/ 42 阅读

相关 Leetcode 264. 丑数 II(最小堆)

题目重述给你一个整数 n ，请你找出并返回第 n 个丑数。丑数就是只包含质因数 2、3 和/或 5 的正整数。示例 1：输入：n = 10

怼烎@/ 2022年09月11日 22:22/ 0 赞/ 14 阅读

相关丑数

\\题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

r囧r小猫/ 2022年10月27日 21:48/ 0 赞/ 27 阅读

相关 leetcode264丑数

丑数就是质因数只包含 2, 3, 5 的正整数输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10

朱雀/ 2023年03月14日 21:20/ 0 赞/ 12 阅读