华为面试题(8分钟写出代码)

蚊见蚊爱

int current_list[n];
int best_list[n];
int b = INT_MAX;

void best(int *A, int *B, int n, int current)
{
        if (n == current){
            int sum = 0;
            for(int i = 0; i < n; ++i) sum += A[ i ] - B[ i ];
            if (abs(sum) < b){
                b = abs(sum);
                for(int i = 0; i < n; ++i) best_list[ i ] = current_list[ i ];
            }
        }
        
        best(A, B, n, current + 1);
        swap(A[current], B[current]);
        current_list[current] = 1;
        best(A, B, n, current + 1);
        current_list[current] = 0;
        swap(A[current], B[current]);
}

[ 本帖最后由 蚊见蚊爱 于 2008-1-7 21:23 编辑 ]

zgongjin

牛人多了

vafls_scott

基本思路：尝试更换两个数组中的值，直到更换任何一个都不能使它们的差的绝对值更小的时候。

#include <iostream>

int sun(int in[], int n)
{
        int sun = 0;
        for(int i=0;i<n;i++) {
                sun += in;
        }
        return sun;
}

int trychange(int a[], int b[], int n)
{
        int i=0, j=0;
        int sub = sun(a, n) - sun(b, n);
        for(i=0;i<n;i++) {
                for(j=0;j<n;j++) {
                        int tmp;
                        tmp = a;
                        a = b[j];
                        b[j] = tmp;
                        int newsub = sun(a, n) - sun(b, n);
                        if(abs(newsub) < abs(sub)) {
                                return 1;
                        }
                        else {
                                tmp = a;
                                a = b[j];
                                b[j] = tmp;
                        }
                }
        }
        return 0;
}

void printnum(int in[], int n)
{
        for(int i=0;i<n;i++) {
                printf("%d ", in);
        }
}

void init(int in[], int n)
{
        for(int i=0;i<n;i++) {
                in = rand()%100;
        }
}

main(int argc, char* argv[])
{
        int n=8;
        if(1 == argc) {
                n=8;
        }
        else {
                n = atoi(argv[1]) % 100 +1;
        }
        srand(time(NULL));

        int a[100];
        int b[100];
        init(a, n);
        init(b, n);

        while(sun(a, n) != sun(b, n)) {
                if(0 == trychange(a, b, n)) {
                        break;
                }
        }

        printf("\na: ");
        printnum(a, n);
        printf("\t\tsun a: %d\n", sun(a, n));

        printf("b: ");
        printnum(b, n);
        printf("\t\tsun b: %d\n", sun(b, n));
}

havey

不知道是眼睛不好,还是脑袋生锈,这个题目需要八分钟吗?

AlbertAnne

从数学方面考虑；2n个数分为两组，A组和B组的差最小，即A组和B组的每个元素存在最小差
先找出两元素差值最小的一对，分到A和B组，再找到次小的一对，依次类推，分完之后A和B的差最小

天下洪荒

什么时候帖子呀 有上来啦

icylord

很久没上了，居然看到这贴被挖出来。
明显回溯或者动态规划才能得出最有解
回溯加上一个强烈的剪枝比动态规划快，我试过的了

私人杀手

这题太简单了.你们都不会......

私人杀手

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

大家请看题目
试问a[] = { 1,2,3,4 };
b[] = { 3,4,5,6};

他们的和是固定数.那么无论怎么排序......差都一样.

私人杀手

这题主要考的是眼力和智力.你们都太次了.哈哈.