笔试题整理1-腾讯笔试-白红宇

笔试题整理1-腾讯笔试

阅读量：5245 次

发布时间：2019-06-14

本文共 2067 字，大约阅读时间需要 6 分钟。

2013 腾讯实习生笔试题

题目：给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。

在构造过程：不允许使用除法；

要求：O(1)空间复杂度和O(n)时间复杂度；

除遍历计数器与a[N] b[N]外，不可使用新的变量(包括栈临时变量、对空间和全局静态变量等)；

请用程序实现并简单描述。

解法1：

不能使用新的变量，利用收尾元素作为中间变量，第一次迭代b[0] = a[0], for (i 1->n-1) b[i] = b[0]，b[0] *= a[i]。

使b[] = {1, a[0]，a[0]*a[1]，...，a[0]*a[1]*a[2]*...*a[i-1]},第二次迭代 b[0] = 1, for (i n-1->1) b[i] *= b[0],

b[0] *= b[i];得到b数组。

代码：

//解法1class Solution {public:    /**     * @param A: Given an integers array A     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]     */    vector
     
       productExcludeItself(vector
      
        &a) {        // write your code here        vector
       
         b;        b.resize(a.size());        b[0] = a[0];        int num = a.size();        for (int i=1; i
        
         0; --i) {            b[i] *= b[0];            b[0] *= a[i];        }        return b;    }};

解法2：

三次循环，第一次，b[0] = 1, for （int i=1; i<num; ++i） b[i] = b[i-1] * a[i-1];使b[] = {1, a[0], ...，a[0]*...*a[i-1]...}

第二次，a[n-1] = a[n-2], a[n-2] = a[n-1](异或实现交换), for (int i=n-3; i>=0; --i) a[n-1] *= a[i+1], a[i] = a[n-1], a[n-1] = a[i];

使a[] = {a[1]*...*a[n-1]，.... , a[n-1]*a[n-2]*...*a[i+1]，...}.第三次循环使b[i] *= a[i].

附代码:

//解法2class Solution {public:    /**     * @param A: Given an integers array A     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]     */    vector
     
       productExcludeItself(vector
      
        &a) {        // write your code here        vector
       
         b;        b.resize(a.size());        int num = a.size();        b[0] = 1;        for (int i=1; i
        
         =0; --i) { // a[i] = a[num-1...i+1]            a[num-1] *= a[i+1];            a[i] = a[num-1] ^ a[i];            a[num-1] = a[i] ^ a[num-1];            a[i] = a[i] ^ a[num-1];        }        a[num-1] = 1;        for (int i=0; i