r**u
发帖数: 1567 | 1 Design an algorithm to find the kth number divisible by only 3 or 5 or 7 i.e
the only factors of these numbers should be 3,5 and 7. |
g*******y
发帖数: 1930 | 2 this one is very classical, and good
hint: use three queues
.e
【在 r**u 的大作中提到】
: Design an algorithm to find the kth number divisible by only 3 or 5 or 7 i.e
: the only factors of these numbers should be 3,5 and 7.
|
H*M
发帖数: 1268 | 3 just a combination of 3,5,7 ba..can be multiple copies
.e
【在 r**u 的大作中提到】
: Design an algorithm to find the kth number divisible by only 3 or 5 or 7 i.e
: the only factors of these numbers should be 3,5 and 7.
|
H*M
发帖数: 1268 | 4 we can use a min_heap, push 3, 5, 7 first, then pop, multiply the popped one
with 3, 5, 7 each time and push the results.
But how to deal with the duplicates in the min_heap... seems there is a patt
ern of the repitition..
【在 H*M 的大作中提到】
: just a combination of 3,5,7 ba..can be multiple copies
:
: .e
|
H*M
发帖数: 1268 | 5 geniusxsy say say ba
how to use three queues
【在 g*******y 的大作中提到】
: this one is very classical, and good
: hint: use three queues
:
: .e
|
g*******y
发帖数: 1930 | 6 q1:{3}
q2:{5}
q3:{7}
如果q1的队首是当前最小的，出队，分别乘以3，5，7扔进q1 q2 q3
如果q2的队首是当前最小的，出队，分别乘以5，7扔进q2 q3
如果q3的队首是当前最小的，出队，乘以7扔进q3
【在 H*M 的大作中提到】
: geniusxsy say say ba
: how to use three queues
|
H*M
发帖数: 1268 | 7 very nice a! to avoid dups.
how did u come up with this idea...
【在 g*******y 的大作中提到】
: q1:{3}
: q2:{5}
: q3:{7}
: 如果q1的队首是当前最小的，出队，分别乘以3，5，7扔进q1 q2 q3
: 如果q2的队首是当前最小的，出队，分别乘以5，7扔进q2 q3
: 如果q3的队首是当前最小的，出队，乘以7扔进q3
|
r**u
发帖数: 1567 | 8 very clear. 谢谢
【在 g*******y 的大作中提到】
: q1:{3}
: q2:{5}
: q3:{7}
: 如果q1的队首是当前最小的，出队，分别乘以3，5，7扔进q1 q2 q3
: 如果q2的队首是当前最小的，出队，分别乘以5，7扔进q2 q3
: 如果q3的队首是当前最小的，出队，乘以7扔进q3
|
g*******y
发帖数: 1930 | 9 to be honest, I did this problem with a hint of using queue. My initial attempt w/o this hint ended up in a wrong direction (spatial lattice)
Besides, this problem is quite classical, I've seen it at least twice before (now it makes at least three times)
【在 H*M 的大作中提到】
: very nice a! to avoid dups.
: how did u come up with this idea...
|
H*M
发帖数: 1268 | 10 cool..where did u see it? just curious.
I am starting to look at questions in zhiyebei
any other websites we can get trained?
attempt w/o this hint ended up in a wrong direction (spatial lattice)
before (now it makes at least three times)
【在 g*******y 的大作中提到】
: to be honest, I did this problem with a hint of using queue. My initial attempt w/o this hint ended up in a wrong direction (spatial lattice)
: Besides, this problem is quite classical, I've seen it at least twice before (now it makes at least three times)
|
|
|
g*******y
发帖数: 1930 | 11 职业杯上应该是有这题的。
本版精华区上很多题也应该做一遍
【在 H*M 的大作中提到】
: cool..where did u see it? just curious.
: I am starting to look at questions in zhiyebei
: any other websites we can get trained?
:
: attempt w/o this hint ended up in a wrong direction (spatial lattice)
: before (now it makes at least three times)
|
H*M
发帖数: 1268 | 12 duo xie geniusxsy!
【在 g*******y 的大作中提到】
: 职业杯上应该是有这题的。
: 本版精华区上很多题也应该做一遍
|
m******g
发帖数: 5 | 13
these are very good ones. Would you please tell me what the ZHiyebei is? I
am also looking for some training exercises...
thanks, HNM
【在 H*M 的大作中提到】
: cool..where did u see it? just curious.
: I am starting to look at questions in zhiyebei
: any other websites we can get trained?
:
: attempt w/o this hint ended up in a wrong direction (spatial lattice)
: before (now it makes at least three times)
|
n******r
发帖数: 1247 | 14 www.careercup.com
【在 m******g 的大作中提到】
:
: these are very good ones. Would you please tell me what the ZHiyebei is? I
: am also looking for some training exercises...
: thanks, HNM
|
f******h
发帖数: 122 | 15 题目都没有看懂，能不能麻烦哪位大侠把题目详细解释一下...:P
.e
【在 r**u 的大作中提到】
: Design an algorithm to find the kth number divisible by only 3 or 5 or 7 i.e
: the only factors of these numbers should be 3,5 and 7.
|
r**u
发帖数: 1567 | 16 such nums can be represented as: 3^i * 5^j * 7^k,
e.g., 3, 5, 7, 9, 15, 21, 25, ......
find the kth in this list.
【在 f******h 的大作中提到】
: 题目都没有看懂，能不能麻烦哪位大侠把题目详细解释一下...:P
:
: .e
|
h***r
发帖数: 726 | 17 catch the boazi from me!
【在 g*******y 的大作中提到】
: q1:{3}
: q2:{5}
: q3:{7}
: 如果q1的队首是当前最小的，出队，分别乘以3，5，7扔进q1 q2 q3
: 如果q2的队首是当前最小的，出队，分别乘以5，7扔进q2 q3
: 如果q3的队首是当前最小的，出队，乘以7扔进q3
|
m******g
发帖数: 5 | 18
Thanks, novaster
【在 n******r 的大作中提到】
: www.careercup.com
|
b***e
发帖数: 1419 | 19 You are playing a nice trick here. But still, the time complexity is O(n).
That is, you need O(2^k) time complexity assuming n is of k binary bits.
This is not nearly good enough.
I believe there's an algorithm polynomial to k, as laied out in the
following:
For illustration purpose, and without losing (too much) generality, let's
reduce the problem to 2 numbers: 2 and 3.
Given any n, where can try to see how many qualified numbers are smaller
than n. To do this, consider the lattice for the |
g*******y
发帖数: 1930 | 20 The three-queue algo. can achieve O(k), where k stands for k-th qualified
number.
but I'm kinda confused by your notation of 'n', 'k'. The problem is to find
kth qualified number --> does this k have same meaning as yours?
.
【在 b***e 的大作中提到】
: You are playing a nice trick here. But still, the time complexity is O(n).
: That is, you need O(2^k) time complexity assuming n is of k binary bits.
: This is not nearly good enough.
: I believe there's an algorithm polynomial to k, as laied out in the
: following:
: For illustration purpose, and without losing (too much) generality, let's
: reduce the problem to 2 numbers: 2 and 3.
: Given any n, where can try to see how many qualified numbers are smaller
: than n. To do this, consider the lattice for the
|
g*******y
发帖数: 1930 | 21 其实我最初做这题，也是考虑的lattice，考虑空间整数点阵
一个斜面 with ln3*x + ln5*y + ln7*z = n
逐渐增大n，直观上就是把这个斜面向远离原点的地方平移，
所有被该斜面所包围在内的点数就是： 所有小于某个值(e^n)的符合条件的数的个数。
这样，当k很大的时候，容易很快的给出一个近似估计(令k=斜面包围的空间的体积=1/3*x_0*y_0*z_0，x_0为该斜面和x轴交点)，因为lattice一个单位体积中有一个点。解出x_0,y_0,z_0，n，那么近似估计值就是e^n
x_0，y_0，z_0的量级都是k^(1/3)
要求精确解的话，需要在近似解(截面)附近搜索了，而截面的面积是O(k^(2/3))，所以我估计
最后算法能优化到 k^(2/3)
不过还是queue的方法elegant很多
.
【在 b***e 的大作中提到】
: You are playing a nice trick here. But still, the time complexity is O(n).
: That is, you need O(2^k) time complexity assuming n is of k binary bits.
: This is not nearly good enough.
: I believe there's an algorithm polynomial to k, as laied out in the
: following:
: For illustration purpose, and without losing (too much) generality, let's
: reduce the problem to 2 numbers: 2 and 3.
: Given any n, where can try to see how many qualified numbers are smaller
: than n. To do this, consider the lattice for the
|
b***e
发帖数: 1419 | 22 My time complexity calculation is wrong. Yours is right. Basically, I am
saying that we probably should start somewhere from the middle rather than
test from the beginning. That may boost the converge rate.
数。
=1/3*x_0*y_0*z_0，x_0为该斜面和x轴交点)，因为lattice一个单位体积中有一个点。
解出
x_0,y_0,z_0，n，那么近似估计值就是e^n
以我估计
【在 g*******y 的大作中提到】
: 其实我最初做这题，也是考虑的lattice，考虑空间整数点阵
: 一个斜面 with ln3*x + ln5*y + ln7*z = n
: 逐渐增大n，直观上就是把这个斜面向远离原点的地方平移，
: 所有被该斜面所包围在内的点数就是： 所有小于某个值(e^n)的符合条件的数的个数。
: 这样，当k很大的时候，容易很快的给出一个近似估计(令k=斜面包围的空间的体积=1/3*x_0*y_0*z_0，x_0为该斜面和x轴交点)，因为lattice一个单位体积中有一个点。解出x_0,y_0,z_0，n，那么近似估计值就是e^n
: x_0，y_0，z_0的量级都是k^(1/3)
: 要求精确解的话，需要在近似解(截面)附近搜索了，而截面的面积是O(k^(2/3))，所以我估计
: 最后算法能优化到 k^(2/3)
: 不过还是queue的方法elegant很多
:
|
