0

我经历了一次面试，我被要求为第 i 位添加 2 个具有 -2 索引的整数，即 (-2) 幂 i。我给出了以下答案，但被告知此答案无效且错误。我不同意效率低下的评论，但可能同意错误。

如果 2 位的总和大于等于 2，我添加的方式是进位 -1，因为相邻位的符号相反。如果添加 2 位是 -1，我将其设为 1，并将 1 进位到相邻位。

有人看到代码有任何问题吗？

struct Results solution ( int A[], int M, int B[], int N ) {
    struct Results result;

    int min =M;
    int max = M;

    int i=0;
    int sum;
    int carry = 0;

    if(N<M)min = N;
    if(N>M)max = N;

    result.C = (int*) malloc(sizeof(int) * max);

    for(i=0;i<min;i++){
        sum = A[i] +  B[i] + carry;
        if(sum >= 2 ){
            if(carry == 0 ) 
                carry = -1;
            else 
                carry = -carry;
            sum = sum-2;
        }
        else if(sum == -1){
            sum = 1;
            carry = 1;  
        }
        else{
            carry=0;
        }
        result.C[i] = sum;
    }

    if( M > N){
        result.L = M;
        for(i=N;i<M;i++){
            sum = A[i]+carry;
            if(sum >= 2 ){
                if(carry == 0 ) carry = -1;
                else carry = 1;
                sum = sum-2;
            }
            else if(sum == -1){
                sum = 1;
                carry = - carry;  
            }
            else{carry=0;}
            result.C[i] = sum;
        }
    }

    if( N > M){
        result.L = N;
        for(i=M;i<N;i++){
            sum = B[i]+carry;
            if(sum >= 2 ){
                if(carry == 0 ) carry = -1;
                else carry = -carry;
                sum = sum-2;
            }
            else if(sum == -1){
                sum = 1;
                carry = 1;  
            }
            else{carry=0;}
            result.C[i] = sum;
        }
    }

    return result;
}

int main(int argc, char* argv[])
{
    int A[]  = {0,1,1,0,0,1,0,1,1,1,0,1,0,1,1};
    int B[]  = {0,0,1,0,0,1,1,1,1,1,0,1};
    solution (A,15,B ,12 );
}
4

2 回答 2

1

问题 1

如果 2 位的总和大于等于 2，您说您使用-1 进位，但在您的一种情况下，您有以下代码：

        if(sum >= 2 ){
            if(carry == 0 ) carry = -1;
            else carry = 1;
            sum = sum-2;
        }

这会将进位设置为 1，而不是 -1。

您还可以争辩说，这段代码可以更有效地编写为：

        if(sum >= 2 ){
            carry = -1;
            sum = sum-2;
        }

问题 2

如果我们添加 {1} 和 {1} 会发生什么？您将返回 1 的长度和 {0} 的结果，但答案应该是 {0,1,1}。(1+1=-2+4) 换句话说，您可能需要返回比输入的最大值更多的位。

于 2013-05-29T18:18:47.237 回答
1

O(1) 解决方案：查表。

如果您知道每个输入的位数，那么 2D 查找表会非常快。如果没有，你仍然可以一次做一堆位。

于 2013-05-29T18:30:05.443 回答