【刷算法】丑数

harriszh 发布于2019-08-26 12:08 / 2289人阅读

摘要：题目描述把只包含质因子和的数称作丑数。习惯上我们把当做是第一个丑数。求按从小到大的顺序的第个丑数。分析首先从题目可以知道，对于一个丑数，都是丑数。

题目描述

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

分析

首先从题目可以知道，对于一个丑数p，p*2、p*3、p*5都是丑数。

那么从第一个丑数1开始，1*2、1*3、1*5都是丑数，最小的2是第二个丑数；

对于第二个丑数2来说，又多出来三个需要被比较的数字，即2*2、2*3、2*5，再加上第一轮挑剩下的1*3、1*5，但是这里显然可以看出来，1*3<2*3，1*5<2*5，所以其实只需要比较2*2、1*3、1*5即可。

......

按照这样的节奏比下去即可。

代码实现

function GetUglyNumber_Solution(index)
{

if(index < 7)   
    return index;
var res = [];
res[0] = 1;
var t2 = 0, t3 = 0, t5 = 0;

for(var i = 1;i < index;i++){
    res[i] = Math.min(res[t2]*2, Math.min(res[t3]*3, res[t5]*5));
    if(res[i] === res[t2]*2)
        t2++;
    if(res[i] === res[t3]*3)
        t3++;
    if(res[i] === res[t5]*5)
        t5++;
}

return res[index-1];

}

云服务器 GPU云服务器找丑数 c语言刷应用刷VPS 刷cdn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/108092.html

力扣(LeetCode)263

摘要：题目地址题目描述编写一个程序判断给定的数是否为丑数。输入不会超过位有符号整数的范围。如果最后的结果不是也就是说该数不仅包含这三个质因数那么它就不是丑数，否则是丑数。代码小于等于的一定不是丑数。。。题目地址：https://leetcode-cn.com/probl...题目描述：编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例 1: 输入:...

AnthonyHan 2019-08-16 14:28 评论0 收藏0
leetcode263,264,313 ugly numbers

摘要：这题可以使用暴力遍历法，从开始，对每一个数都进行判断，直到找到第个丑数为止。优先队列可以很好的满足该情况。因此每个素数持有的信息包括当前对应的丑数的下标。前言这一篇博客把ugly numbers系列的题目做一个整理。这三道题正好是一个思路的循序渐进，所以放在一篇博客当中。 Ugly Number Write a program to check whether a given nu...

everfly 2019-08-16 11:02 评论0 收藏0
264. Ugly Number II & 313. Super Ugly Number

摘要：每次出一个数，就把这个数的结果都放进去。，指针从个变成个。的做法参考还是复杂度的问题，回头再看看 264. Ugly Number II 题目链接：https://leetcode.com/problems... dp的方法参考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

hiyang 2019-08-16 10:29 评论0 收藏0
剑指offer--JavaScript版

摘要：剑指在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。其中负数用补码表示。本文为8月牛客网《剑指 offer》刷题做得，现整理出来作为参考。虽然是算法题，但本文用 JavaScript 编写，看了《剑指 offer》以后发现很多问题处理的过程并不是最好的，所以本文仅供参考。以前全部代码 A...

MarvinZhang 2019-08-23 11:52 评论0 收藏0