<ul id="2ggqi"></ul>

【刷算法】丑數

harriszh 發布于2019-08-26 12:08 / 2290人閱讀

摘要：題目描述把只包含質因子和的數稱作丑數。習慣上我們把當做是第一個丑數。求按從小到大的順序的第個丑數。分析首先從題目可以知道，對于一個丑數，都是丑數。

題目描述

把只包含質因子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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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