j*******r
发帖数: 52 | 1 1.
f(i,j)=2^i*5^j
给出一个长度为N的(i,j)序列，使得f值递增，i>=0,j>=0
2.
f(N):
return round(reduce(lambda x,y: int(x)+int(y), list(str(N))))/len(N)
N为整数，f函数返回N各位数值的平均数，现在给出一个正整数范围[begin, end]，要
求得出该范围中符合f(N)>=7的数的集合，希望算法尽可能比end-begin+1次test快。 | s*****n
发帖数: 5488 | 2 第一题条件不全吧。否则
00, 11,22,33,to N-1,n-1.
【在 j*******r 的大作中提到】
: 1.
: f(i,j)=2^i*5^j
: 给出一个长度为N的(i,j)序列，使得f值递增，i>=0,j>=0
: 2.
: f(N):
: return round(reduce(lambda x,y: int(x)+int(y), list(str(N))))/len(N)
: N为整数，f函数返回N各位数值的平均数，现在给出一个正整数范围[begin, end]，要
: 求得出该范围中符合f(N)>=7的数的集合，希望算法尽可能比end-begin+1次test快。
| f****4
发帖数: 1359 | 3 应该是想要这么个序列
f(i,j)=2^i*5^j
00, 1
10, 2
20, 4
01, 5
30, 8
11, 10
40, 16
21, 20
02, 25
50, 32
31, 40
60, 64
03, 75
41, 90
70, 128
。。。
【在 s*****n 的大作中提到】
: 第一题条件不全吧。否则
: 00, 11,22,33,to N-1,n-1.
| b*****n
发帖数: 482 | 4 Q1: it is similar to the one in CareerCup 150
Use two queues, q1 for incrementing factor of 2, q2 for incrementing
factor of 5. Below are the steps
1. init the queues.
q1: (1,0) which means 2^1*5^0.
q2: (0,1) which means 2^0*5^1.
2. Compare front elements from the two queues, and dequeue the smaller
one: (i,j). Put (i,j) in you output sequence. If num of elements in the
output sequence reaches N, break.
3. Enqueue (i, j+1) into q2, and if (i,j) is from q1, also enqueue (i+1,
j) into q1.
4. Go back to step 2.
Q2: don't understand what the question is, can you give an example?
list(str(N))))/len(N)
【在 j*******r 的大作中提到】
: 1.
: f(i,j)=2^i*5^j
: 给出一个长度为N的(i,j)序列，使得f值递增，i>=0,j>=0
: 2.
: f(N):
: return round(reduce(lambda x,y: int(x)+int(y), list(str(N))))/len(N)
: N为整数，f函数返回N各位数值的平均数，现在给出一个正整数范围[begin, end]，要
: 求得出该范围中符合f(N)>=7的数的集合，希望算法尽可能比end-begin+1次test快。
| j*******r
发帖数: 52 | 5 谢谢第一题的解答，it works，能详细说说是怎么想到的吗？
抱歉第二题没说清楚，其实那个函数是一个python代码
def f(N):
return round(reduce(lambda x,y:int(x)+int(y),list(str(N))))/len(N)
写得太难看还是无视吧，其实就是算一个数各个位上数的平均，比如5989，平均就是(5
+9+8+9)/4=31/4>7符合条件，但5980平均就是(5+9+8+0)/4=22/4<7不符合要求。现在给
出两个正整数A,B，要求[A,B]中所有符合这个要求的数的集合。
【在 b*****n 的大作中提到】
: Q1: it is similar to the one in CareerCup 150
: Use two queues, q1 for incrementing factor of 2, q2 for incrementing
: factor of 5. Below are the steps
: 1. init the queues.
: q1: (1,0) which means 2^1*5^0.
: q2: (0,1) which means 2^0*5^1.
: 2. Compare front elements from the two queues, and dequeue the smaller
: one: (i,j). Put (i,j) in you output sequence. If num of elements in the
: output sequence reaches N, break.
: 3. Enqueue (i, j+1) into q2, and if (i,j) is from q1, also enqueue (i+1,
| m**q
发帖数: 189 | 6 Didn't find a similar one in CareerCup 150, could you help
point me to the related question?
Also, seems the algorithm below isn't correct, as numbers like
10, 20, 40 .etc are not included in either queues. I thought
a while but only have a not-so-good approach for this. Hope
someone has a clever method.
【在 b*****n 的大作中提到】
: Q1: it is similar to the one in CareerCup 150
: Use two queues, q1 for incrementing factor of 2, q2 for incrementing
: factor of 5. Below are the steps
: 1. init the queues.
: q1: (1,0) which means 2^1*5^0.
: q2: (0,1) which means 2^0*5^1.
: 2. Compare front elements from the two queues, and dequeue the smaller
: one: (i,j). Put (i,j) in you output sequence. If num of elements in the
: output sequence reaches N, break.
: 3. Enqueue (i, j+1) into q2, and if (i,j) is from q1, also enqueue (i+1,
| s*****y
发帖数: 897 | 7 http://www.careercup.com/question?id=9314280
【在 m**q 的大作中提到】
: Didn't find a similar one in CareerCup 150, could you help
: point me to the related question?
: Also, seems the algorithm below isn't correct, as numbers like
: 10, 20, 40 .etc are not included in either queues. I thought
: a while but only have a not-so-good approach for this. Hope
: someone has a clever method.
:
| b*****n
发帖数: 482 | 8 CareerCup 150, 10.7, it is about 3 factors of 3, 5, 7.
【在 m**q 的大作中提到】
: Didn't find a similar one in CareerCup 150, could you help
: point me to the related question?
: Also, seems the algorithm below isn't correct, as numbers like
: 10, 20, 40 .etc are not included in either queues. I thought
: a while but only have a not-so-good approach for this. Hope
: someone has a clever method.
:
| b*****n
发帖数: 482 | 9 I have got a semi-baked solution. It deals with input [A, B] if A = 10^n
and B= 10^(n+1) - 1, e.g. [10, 99], or [100, 999].
Starting with B, store B into a vector(vBEnd) for easy processing.
Set CurSumB to the sum of each digits in B;
Set SumNeededB to 7 * number of digits in B;
Set extra = CurSumB - SumNeededB. Here extra means how much we can
decrease for the digits in B and still make the average >= 7;
e.g. if B=999, CurSumB = 27, SumNeededB = 7*3 = 21, extra = 6.
Let i = index of LSB of B, decreasing to the index of MSB of B (e.g. if
B=999, i=2, 1, 0)
call function: Solve(A, vBEnd, i, extra)
The main thing Solve does is: (please look at the example couple of
lines below, I know I may not express this clearly)
set digit to the ith item of vBEnd;
Let j = digit, decreasing to max(digit-extra, 0)
set ith item in vBEnd to j;
if i == index of LSB of B
print current number (from vBEnd);
else
call Solve(A, vBEnd, i+1, extra-(digit-j));
end
What Solve really does is to decrease the digit at index i from its
current value all the way to digit-extra or 0. That way it guarantees
the average >= 7. When the index i is the LSB, we can immediately print
out the number. If the index i is not the LSB, we have to recursively
call the function to decrease the digits from i+1 to LSB till extra
reaches 0.
For example for B=99
When i = 1, extra=4, we print out 99, 98, 97, 96, 95(where 9-4 = 5).
When i = 0, extra=4,
first: we decrease the 10-digit to 8, now the vector vBEnd has item
of 8, and 9.
Now we call Solve(A, vBEnd, 1，3), here i=1, extra = 3.
So it goes back to the basic case of i=1, and we print out 89,
88, 87, 86(where 9-3=6).
Second: we decrease the 10-digit to 7, vBEnd now has 7 and 9
Now we call Solve with i=1, extra =2.
We print out 79, 78, 77
....
At the end, we decrease the 10-digit to 5, and print out 59.
Comparing to the brutal force method, for [10000, 99999], my solution
took about 187ms, the brutal force took 7.657s | m**q
发帖数: 189 | |
|
