資訊專欄INFORMATION COLUMN
摘要：題目描述把只包含質(zhì)因子和的數(shù)稱作丑數(shù)。習(xí)慣上我們把當做是第一個丑數(shù)。求按從小到大的順序的第個丑數(shù)。分析首先從題目可以知道，對于一個丑數(shù)，都是丑數(shù)。
題目描述
把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因為它包含質(zhì)因子7。 習(xí)慣上我們把1當做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)。
分析首先從題目可以知道，對于一個丑數(shù)p，p*2、p*3、p*5都是丑數(shù)。
那么從第一個丑數(shù)1開始，1*2、1*3、1*5都是丑數(shù)，最小的2是第二個丑數(shù)；
對于第二個丑數(shù)2來說，又多出來三個需要被比較的數(shù)字，即2*2、2*3、2*5，再加上第一輪挑剩下的1*3、1*5，但是這里顯然可以看出來，1*3<2*3，1*5<2*5，所以其實只需要比較2*2、1*3、1*5即可。
......
按照這樣的節(jié)奏比下去即可。
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];
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/108092.html
摘要：題目地址題目描述編寫一個程序判斷給定的數(shù)是否為丑數(shù)。輸入不會超過位有符號整數(shù)的范圍。如果最后的結(jié)果不是也就是說該數(shù)不僅包含這三個質(zhì)因數(shù)那么它就不是丑數(shù)，否則是丑數(shù)。代碼小于等于的一定不是丑數(shù)。。。 題目地址：https://leetcode-cn.com/probl...題目描述：編寫一個程序判斷給定的數(shù)是否為丑數(shù)。 丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。 示例 1: 輸入:...
摘要：這題可以使用暴力遍歷法，從開始，對每一個數(shù)都進行判斷，直到找到第個丑數(shù)為止。優(yōu)先隊列可以很好的滿足該情況。因此每個素數(shù)持有的信息包括當前對應(yīng)的丑數(shù)的下標。 前言 這一篇博客把ugly numbers系列的題目做一個整理。這三道題正好是一個思路的循序漸進，所以放在一篇博客當中。 Ugly Number Write a program to check whether a given nu...
摘要：每次出一個數(shù)，就把這個數(shù)的結(jié)果都放進去。，指針從個變成個。的做法參考還是復(fù)雜度的問題，回頭再看看 264. Ugly Number II 題目鏈接：https://leetcode.com/problems... dp的方法參考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...
摘要：劍指在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。其中負數(shù)用補碼表示。 本文為8月牛客網(wǎng)《劍指 offer》刷題做得，現(xiàn)整理出來作為參考。雖然是算法題，但本文用 JavaScript 編寫，看了《劍指 offer》以后發(fā)現(xiàn)很多問題處理的過程并不是最好的，所以本文僅供參考。以前全部代碼 A...
閱讀 1698·2019-08-30 15:54
閱讀 3347·2019-08-26 17:15
閱讀 3541·2019-08-26 13:49
閱讀 2592·2019-08-26 13:38
閱讀 2307·2019-08-26 12:08
閱讀 3067·2019-08-26 10:41
閱讀 1381·2019-08-26 10:24
閱讀 3390·2019-08-23 18:35
