程序的问题:已知数组a[n],求数组b[n].要求:b[i]=a[0]*a[1]*……*a[n-1]/a[i],不能用除法。
a.时间复杂度O(n),空间复杂度O(1)。 b.除了迭代器i,不允许使用任何其它变量(包括栈临时变量等)
大家有什么解法?先不要看我下面的解法。
希望大家讨论讨论一下,留个言,一起交流一下。
下面给出我的解法一:
#include <stdio.h> #include <stdlib.h> //Author:397090770 //Bolg: // 仅供学习 #define N 10 int main(){ int a[N], b[N], i; for(i = 0; i < N; i++){ a[i] = i + 1; } b[0] = 1; for(i = 1; i < N; i++){ b[i] = b[i - 1] * a[i - 1]; } for(i = N - 2; i > 0; i--){ a[i] = a[i + 1] * a[i]; } for(i = 0; i < N - 1; i++){ b[i] = b[i] * a[i + 1]; printf("%d ", b[i]); } printf("\n"); return 0; }
这个解法把a数组里面的数据修改了,如果下次要用,就不行了。
给出修改版的:
解法二:
#include <stdio.h> #include <stdlib.h> #define N 10 //Author:397090770 //Bolg: // 仅供学习 int main(){ int a[N], b[N], i; for(i= 0; i < N; i++){ a[i]= i + 4; } b[0]= 1; for(i= 1; i < N; i++){ b[i] = b[i - 1] * a[i - 1]; } for(i = N - 2; i > 0; i--){ b[0] *= a[i + 1]; b[i]*= b[0]; } b[0] *= a[1]; for(i = 0; i < N; i++){ printf("%d ", b[i]); } return0; }本博客文章除特别声明,全部都是原创!
原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【2012年腾讯招聘实习生笔试题】(https://www.iteblog.com/archives/155.html)