c**********e
发帖数: 2007 | 1 Design an algorithm to find the kth number such that the only prime factors
are 3, 5 and 7. | w****x
发帖数: 2483 | 2 迭代法:
//Find the nth number which is composed by factor 2, 3 and 5
void PrintSerials(int n)
{
assert(n > 0);
vector vec;
vec.push_back(1);
int nI2 = 0;
int nI3 = 0;
int nI5 = 0;
int nCount = 1;
while(nCount < n)
{
int nTmp2 = vec[nI2]*2;
int nTmp3 = vec[nI3]*3;
int nTmp5 = vec[nI5]*5;
int nMin = min(min(nTmp2, nTmp3), nTmp5);
if (vec.back() != nMin)
{
vec.push_back(nMin);
nCount++;
}
if (nMin == nTmp2)
nI2++;
else if (nMin == nTmp3)
nI3++;
else nI5++;
}
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
cout<<*it<
} | c*********t
发帖数: 2921 | 3 ding
【在 c**********e 的大作中提到】
: Design an algorithm to find the kth number such that the only prime factors
: are 3, 5 and 7.
| l******e
发帖数: 149 | 4 wwwyhx 的解法还是很牛的，简化了一下
static List getNth235(int k){
int i2 = 0, i3 = 0, i5 = 0;
List list = new ArrayList();
list.add(1);
while(list.size() < k){
int n2 = list.get(i2)*2;
int n3 = list.get(i3)*3;
int n5 = list.get(i5)*5;
int tmp = Math.min(Math.min(n2, n3), n5);
list.add(tmp);
if(tmp == n2) i2++;
if(tmp == n3) i3++;
if(tmp == n5) i5++;
}
return list;
} | c**********e
发帖数: 2007 | 5 Good solutions. Thank you both. | w****o
发帖数: 2260 | 6 wwwyhx,
没有完全看懂，能否讲讲你的idea?
你用了三个index, nI2, nI3, nI5,然后不断的调整这些index,到底每个index都指示的
是什么？
careercup 150题的哪本书上，是用了3个queue,你的做法和careercup的做法是如何等
效的？
其实这两个我都没有完全弄明白。
谢谢！
【在 w****x 的大作中提到】
: 迭代法:
: //Find the nth number which is composed by factor 2, 3 and 5
: void PrintSerials(int n)
: {
: assert(n > 0);
: vector vec;
: vec.push_back(1);
: int nI2 = 0;
: int nI3 = 0;
: int nI5 = 0;
| w****o
发帖数: 2260 | 7 好像不对的。我试了一下 2, 3, 5 的情况，是错的。
【在 w****x 的大作中提到】
: 迭代法:
: //Find the nth number which is composed by factor 2, 3 and 5
: void PrintSerials(int n)
: {
: assert(n > 0);
: vector vec;
: vec.push_back(1);
: int nI2 = 0;
: int nI3 = 0;
: int nI5 = 0;
| p*****2
发帖数: 21240 | |
|
