今天腾讯笔试的一道题目,大家表达下自己的想法,该怎么处理
今天腾讯笔试的一道题目,大家表达下自己的想法
原题大概是:
两个数组a[N],b[N],其中A[N]的各个元素值已知,现给b[i]赋值,b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i];
要求:
1.不准用除法运算
2.除了循环计数值,a[N],b[N]外,不准再用其他任何变量(包括局部变量,全局变量等)
3.满足时间复杂度O(n),空间复杂度O(1)
------解决方案--------------------
b[0] = 1;
for (int i = 1; i < N; i++)
{
b[0] *= a[i-1];
b[i] = b[0];
}
b[0] = 1;
for (i = N-2; i > 0; i--)
{
b[0] *= a[i+1];
b[i] *= b[0];
}
b[0] *= a[1];
------解决方案--------------------
void Zero(int a[], int b[], int N) {
int i;
b[N - 1] = a [N - 1];
for(i = N - 2; i >= 0; --i) { //construct backward array in b array
b[i] = b[i + 1] * a[i];
}
b[N - 1] = 1; //use as forward
for(i = 0; i < N - 2; ++i) {
b[i] = b[N - 1] * b[i + 1];
b[N - 1] *= a[i];
}
b[N - 2] = b[N - 1] * a[N - 1];
b[N - 1] = b[N - 1] * a[N - 2];
}
------解决方案--------------------
b[N-1] = 1;
for(int i = 0; i < N; i++)
{
b[N-1] *= a[i];
}
for(int i = 0; i < N; i++)
{
b[i] = b[N-1] ^ a[i];
}
原题大概是:
两个数组a[N],b[N],其中A[N]的各个元素值已知,现给b[i]赋值,b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i];
要求:
1.不准用除法运算
2.除了循环计数值,a[N],b[N]外,不准再用其他任何变量(包括局部变量,全局变量等)
3.满足时间复杂度O(n),空间复杂度O(1)
------解决方案--------------------
b[0] = 1;
for (int i = 1; i < N; i++)
{
b[0] *= a[i-1];
b[i] = b[0];
}
b[0] = 1;
for (i = N-2; i > 0; i--)
{
b[0] *= a[i+1];
b[i] *= b[0];
}
b[0] *= a[1];
------解决方案--------------------
void Zero(int a[], int b[], int N) {
int i;
b[N - 1] = a [N - 1];
for(i = N - 2; i >= 0; --i) { //construct backward array in b array
b[i] = b[i + 1] * a[i];
}
b[N - 1] = 1; //use as forward
for(i = 0; i < N - 2; ++i) {
b[i] = b[N - 1] * b[i + 1];
b[N - 1] *= a[i];
}
b[N - 2] = b[N - 1] * a[N - 1];
b[N - 1] = b[N - 1] * a[N - 2];
}
------解决方案--------------------
b[N-1] = 1;
for(int i = 0; i < N; i++)
{
b[N-1] *= a[i];
}
for(int i = 0; i < N; i++)
{
b[i] = b[N-1] ^ a[i];
}