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

banboy

我想删除这个回复，我的完整回复在前面，我不知道但是删除不掉，

大家不要看这个了，

我上面有个回复，大家可以看一下了，

我很久没写代码了，都在做网页，你们把代码写下吧

[ 本帖最后由 banboy 于 2006-11-14 10:04 编辑 ]

splitflag

楼上的，解释一下，为什么这么取？

cuicp

大侠们看这样可不可以：

1。先把两个数组相加，求平均数（a）。
2。在数组中取出和平均数差最小的一个或多个，如果是一个就分在一组，如果是多个就平均分（奇数个和偶数个一样）。
3。把剩下的元素排序，一次取两个元素（升序或降序），算一下两个元素的和（b）与差（c），取（b－a）和（c－a）绝对值小的那个，如果（b－a）小，把两个元素都加到和小的那个组中去，如果（c－a）小，把b和c中大的那个加到元素和小的那一组，把b和c中小的那个加到数组和大的那一组。

例如：
1，3，5
平均数：3
取3，分为第一组，
取1，5,因为（（1＋5）－3） > （（5－1）－3）,把1分给和大的那组，也就是第一组，把5分给和小的那组，也就是第二组，因为其和为零。
这样，5－（1＋3）＝1

又例如：
1，5，10，15
平均数：7。75，
先取10，分为第一组，
然后取1，5，因为（7。75－（1＋5）） < （7。75－（5－1））,所以把1与5都分给数组和小的那组，也就是第二组，然后取15分给和小的那组，（因为只剩15了）
最后得到：（10＋1＋5）－15 ＝ 1
差最小。

类推：
1，2，3，4，5，6

分为：
3，1，2，5
4，6

差为：1

不知道这种分法怎么样？
大家参考一下！！

有不对的地方请高手指正！
谢谢！！

cMEr

取出所有，大小排序，
最大减最小，
取最接近差值的元素，
放在较小的一组，
直到最后。

论证中。。。。

ccjjhua

想想2个原始人，他们一起采集了一些土豆2n个，他们之前有一个协议，就是采集到的东西都要平分，最好他们会怎么分，会比较公平呢？土豆不进行切割。你拿一个，我拿一个，个数一样，要求分到的总重量差要最小。那他们应该先把所有的土豆按大小排序，某个人先拿最小的，另一个拿次小的放进自己的筐中。接着就是掂一下2个筐，觉得重些的那个人，先拿还没分掉的土豆中最小的。如此反复，直到土豆分完。
大家看看这个法子是不是最公平？

[ 本帖最后由 ccjjhua 于 2006-11-14 10:52 编辑 ]

cuicp

原帖由 cMEr 于 2006-11-14 10:18 发表
取出所有，大小排序，
最大减最小，
取最接近差值的元素，
放在较小的一组，
直到最后。

论证中。。。。

这样好像不行，
比如：
1，2，3，4，5，6

结果是不是：
3，5，1
4，2，6

可是不是最佳方案。

chzht001

先将数组排序（全排序，两个数组一起排），然后类似如下处理

#include    <iostream>

using namespace std;

void    swap(int &x, int &y)
{
    x = x ^ y;
    y = y ^ x;
    x = y ^ x;
}

int main()
{
    int a[] = {1, 13, 34, 44, 54, 58};
    int b[] = {3, 23, 45, 56, 67, 77};

    int i, sub;
    static  int total = 0;

    for(i = 5; i >=0 ; i--)
    {   
        sub = b - a;
        if(total)
        {
            if((total > 0 && sub > 0) || (total < 0 && sub < 0))
            {
                swap(a, b);
                total -= sub;
            }
            else if((total >0 && sub < 0) || (total < 0 && sub > 0))
                total += sub;

        }
        else
        {
            total = sub;
        }
    }

    cout << "a: " << endl;
    for(i = 0; i < 6; i++)
        cout << a << " " ;
    cout << endl;

    cout << "b: " << endl;
    for(i = 0; i < 6; i++)
        cout << b << " " ;
    cout << endl;

    cout << "total: " << total << endl;
}

[ 本帖最后由 chzht001 于 2006-11-14 10:49 编辑 ]

btdm

类似背包问题，用二叉树来表示，搜索一条从根到叶结点的权最小的路径，时间复杂度是2的n次方

cMEr

原帖由 cuicp 于 2006-11-14 10:34 发表



这样好像不行，
比如：
1，2，3，4，5，6

结果是不是：
3，5，1
4，2，6

可是不是最佳方案。

相等时让原最小一组成为最大，不知可行吗？
1,4,7,8,9,11,18,19

1,18,11,7
19,9,8,4

chzht001

原帖由 cMEr 于 2006-11-14 10:57 发表



相等时让原最小一组成为最大，不知可行吗？
1,4,7,8,9,11,18,19

1,18,11,7
19,9,8,4

那是因为还没有全排序，全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零，因为有两数组的数个数相同的约束

正确的处理应是先找出最大的和第二大的分别放入两个数组，然后再找除去这两个后的最大的和第二大的，再依据前一次
的差值确定第二次取的最大和第二大的数放进哪一个数组，依次类推

[ 本帖最后由 chzht001 于 2006-11-14 11:13 编辑 ]