c***2
发帖数: 838 | 1 1) Given an array A, output another array B such that B[k]=product
of all elements in A but A[k]. You are not allowed to use division.
How to do without division?
2) 给你三根棍子，每根都需要一个小时才烧完，但每根燃烧的速度都不一样，也不均
匀。问只有这三根棍子和火柴，如何精确的得到1小时45分钟的计时？
Burn both sides to get 30 mins, how to get 15mins?
(burning from both sides plus middle point won't do the trick)
Thanks, | x*****p
发帖数: 1707 | 2 Question #2
Burn two sticks at the same time, first one burns both sides, second one
burns one side. After 30 minutes, first one is gone, then burn another side
of the second stick, 15 minutes later, this one is gone. So you get 45
minutes. Then burn the third stick from one side, you get 1 hr 45 minuts. | c********n
发帖数: 26 | 3 两道题确实都挺常见的。
1. 设置两个数组，A1[i] = A1[0]*A1[1]*...A1[i], A2[i] = A2[n]*A2[n-1]*...A2[i
] 那么B[i] = A[i-1]*A[i+1]
2. 第二个网上例子很多，解释也很详细，可以去搜搜 | c***2
发帖数: 838 | 4 Thanks!
side
【在 x*****p 的大作中提到】
: Question #2
: Burn two sticks at the same time, first one burns both sides, second one
: burns one side. After 30 minutes, first one is gone, then burn another side
: of the second stick, 15 minutes later, this one is gone. So you get 45
: minutes. Then burn the third stick from one side, you get 1 hr 45 minuts.
| c***2
发帖数: 838 | 5 This is O(n^2), (brute-force)
I am asking for O(n)
product=a[0]*...a[n-1]
b[i]=product/a[i]
[i
【在 c********n 的大作中提到】
: 两道题确实都挺常见的。
: 1. 设置两个数组，A1[i] = A1[0]*A1[1]*...A1[i], A2[i] = A2[n]*A2[n-1]*...A2[i
: ] 那么B[i] = A[i-1]*A[i+1]
: 2. 第二个网上例子很多，解释也很详细，可以去搜搜
| i**********e
发帖数: 1145 | 6 http://www.ihas1337code.com/2010/04/multiplication-of-numbers.html
You could use DP to solve it, with an extra table to prevent the same
calculation over and over again, O(N) time and O(N) space.
Define array B where element B[i] = multiplication of numbers from A[0] to A
[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then
, we scan the array A from right to left, and have a temporary variable
called product which stores the multiplication from right to left so far.
Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.
There's one trick though. You can actually solve it with O(N) time and O(1)
space, without any extra table. The hint is to use two variables.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***2 的大作中提到】
: 1) Given an array A, output another array B such that B[k]=product
: of all elements in A but A[k]. You are not allowed to use division.
: How to do without division?
: 2) 给你三根棍子，每根都需要一个小时才烧完，但每根燃烧的速度都不一样，也不均
: 匀。问只有这三根棍子和火柴，如何精确的得到1小时45分钟的计时？
: Burn both sides to get 30 mins, how to get 15mins?
: (burning from both sides plus middle point won't do the trick)
: Thanks,
| L*******e
发帖数: 114 | 7 This is a small program I wrote for DP solution.
/*
* DP: B[j] = product[0,j-1] * product[j+1, n-1]
* product[1,j] = product[1,j-1] * A[j]
* product[j,n-1] = product[j+1,n-1] * A[j]
*/
#include
using namespace std;
void convertArray( const vector& in, vector& out )
{
vector::size_type sz = in.size();
vector< vector > product(sz, vector(sz));
product[0][0] = in[0];
product[sz-1][sz-1] = in[sz-1];
// calcuate product[0,j] = product[0][j-1]*A[j]
for( int j = 1; j < sz; j++ )
product[0][j] = product[0][j-1]*in[j];
for( int j = sz -2; j >= 0; j-- )
product[j][sz-1] = product[j+1][sz-1] * in[j];
out[0] = product[1][sz-1];
out[sz-1] = product[0][sz-2];
for( int i = 1; i < sz -1; i++ )
out[i] = product[0][i-1] * product[i+1][sz-1];
} | c***2
发帖数: 838 | 8 That's an elegant solution.
A
Then
)
【在 i**********e 的大作中提到】
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.html
: You could use DP to solve it, with an extra table to prevent the same
: calculation over and over again, O(N) time and O(N) space.
: Define array B where element B[i] = multiplication of numbers from A[0] to A
: [i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then
: , we scan the array A from right to left, and have a temporary variable
: called product which stores the multiplication from right to left so far.
: Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.
: There's one trick though. You can actually solve it with O(N) time and O(1)
: space, without any extra table. The hint is to use two variables.
| r****o
发帖数: 1950 | 9
dynamic programming
burn the first stick from one end, you get one hour.
then burn the second stick from both sides, and at the same time, burn the
third stick from one end,
When the second stick finished you get 30 minutes, then immediately burn the
third stick from the other side you will get additional 15 minutes.
【在 c***2 的大作中提到】
: 1) Given an array A, output another array B such that B[k]=product
: of all elements in A but A[k]. You are not allowed to use division.
: How to do without division?
: 2) 给你三根棍子，每根都需要一个小时才烧完，但每根燃烧的速度都不一样，也不均
: 匀。问只有这三根棍子和火柴，如何精确的得到1小时45分钟的计时？
: Burn both sides to get 30 mins, how to get 15mins?
: (burning from both sides plus middle point won't do the trick)
: Thanks,
| c***2
发帖数: 838 | 10 Very good tricks, thanks all. | | | j***y
发帖数: 2074 | 11
[i
A1[], A2[]怎么和A[]挂上钩啊？
【在 c********n 的大作中提到】
: 两道题确实都挺常见的。
: 1. 设置两个数组，A1[i] = A1[0]*A1[1]*...A1[i], A2[i] = A2[n]*A2[n-1]*...A2[i
: ] 那么B[i] = A[i-1]*A[i+1]
: 2. 第二个网上例子很多，解释也很详细，可以去搜搜
| s*******r
发帖数: 47 | 12 nice
[i
【在 c********n 的大作中提到】
: 两道题确实都挺常见的。
: 1. 设置两个数组，A1[i] = A1[0]*A1[1]*...A1[i], A2[i] = A2[n]*A2[n-1]*...A2[i
: ] 那么B[i] = A[i-1]*A[i+1]
: 2. 第二个网上例子很多，解释也很详细，可以去搜搜
| y*****a
发帖数: 221 | 13 那个可以做到O(n)吧，
从1到n build A1,每个entry都是一个乘法，---- n
从n到1 build A2,每个entry也是一个乘法，---- n
最后又遍历一次B[i] = A1[i] * A2[i]，也是n
【在 c***2 的大作中提到】
: This is O(n^2), (brute-force)
: I am asking for O(n)
: product=a[0]*...a[n-1]
: b[i]=product/a[i]
:
: [i
| y*****a
发帖数: 221 | 14 哦，我这个说的是A1[1] = 1， A1[k] = A[1]*..*A[k-1]， ...
A2[n] = 1, A2[n-k] = A[n]*..*A[n-k+1]，...
最后A[k] = A1[k]*A2[k]
刚被ld指出可以直接把A1写在输出B上，然后继续在B上乘相应的A2的数，这样可以达到
O(1)空间，2n的时间
【在 y*****a 的大作中提到】
: 那个可以做到O(n)吧，
: 从1到n build A1,每个entry都是一个乘法，---- n
: 从n到1 build A2,每个entry也是一个乘法，---- n
: 最后又遍历一次B[i] = A1[i] * A2[i]，也是n
| y*****a
发帖数: 221 | 15 我觉得他意思是 B[i] = A1[i-1]*A2[i+1]把
【在 j***y 的大作中提到】
:
: [i
: A1[], A2[]怎么和A[]挂上钩啊？
|
|
