華為面試題(8分鐘寫出代碼)

banboy

我想刪除這個回復(fù)，我的完整回復(fù)在前面，我不知道但是刪除不掉，

大家不要看這個了，

我上面有個回復(fù)，大家可以看一下了，

我很久沒寫代碼了，都在做網(wǎng)頁，你們把代碼寫下吧

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

splitflag

樓上的，解釋一下，為什么這么��？

cuicp

大俠們看這樣可不可以：

1。先把兩個數(shù)組相加，求平均數(shù)（a）。
2。在數(shù)組中取出和平均數(shù)差最小的一個或多個，如果是一個就分在一組，如果是多個就平均分（奇數(shù)個和偶數(shù)個一樣）。
3。把剩下的元素排序，一次取兩個元素（升序或降序），算一下兩個元素的和（b）與差（c），�。╞－a）和（c－a）絕對值小的那個，如果（b－a）小，把兩個元素都加到和小的那個組中去，如果（c－a）小，把b和c中大的那個加到元素和小的那一組，把b和c中小的那個加到數(shù)組和大的那一組。

例如：
1，3，5
平均數(shù)：3
取3，分為第一組，
取1，5,因為（（1＋5）－3） > （（5－1）－3）,把1分給和大的那組，也就是第一組，把5分給和小的那組，也就是第二組，因為其和為零。
這樣，5－（1＋3）＝1

又例如：
1，5，10，15
平均數(shù)：7。75，
先取10，分為第一組，
然后取1，5，因為（7。75－（1＋5）） < （7。75－（5－1））,所以把1與5都分給數(shù)組和小的那組，也就是第二組，然后取15分給和小的那組，（因為只剩15了）
最后得到：（10＋1＋5）－15 ＝ 1
差最小。

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

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

差為：1

不知道這種分法怎么樣？
大家參考一下��！

有不對的地方請高手指正！
謝謝��！

cMEr

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

論證中。。。。

ccjjhua

想想2個原始人，他們一起采集了一些土豆2n個，他們之前有一個協(xié)議，就是采集到的東西都要平分，最好他們會怎么分，會比較公平呢？土豆不進行切割。你拿一個，我拿一個，個數(shù)一樣，要求分到的總重量差要最小。那他們應(yīng)該先把所有的土豆按大小排序，某個人先拿最小的，另一個拿次小的放進自己的筐中。接著就是掂一下2個筐，覺得重些的那個人，先拿還沒分掉的土豆中最小的。如此反復(fù)，直到土豆分完。
大家看看這個法子是不是最公平？

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

cuicp

原帖由 cMEr 于 2006-11-14 10:18 發(fā)表
取出所有，大小排序，
最大減最小，
取最接近差值的元素，
放在較小的一組，
直到最后。

論證中。。。。

這樣好像不行，
比如：
1，2，3，4，5，6

結(jié)果是不是：
3，5，1
4，2，6

可是不是最佳方案。

chzht001

先將數(shù)組排序（全排序，兩個數(shù)組一起排），然后類似如下處理

#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

類似背包問題，用二叉樹來表示，搜索一條從根到葉結(jié)點的權(quán)最小的路徑，時間復(fù)雜度是2的n次方

cMEr

原帖由 cuicp 于 2006-11-14 10:34 發(fā)表



這樣好像不行，
比如：
1，2，3，4，5，6

結(jié)果是不是：
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 發(fā)表



相等時讓原最小一組成為最大，不知可行嗎？
1,4,7,8,9,11,18,19

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

那是因為還沒有全排序，全排序時再結(jié)合我的處理方法才能得出結(jié)果
兩數(shù)組和之差最小不一定是零，因為有兩數(shù)組的數(shù)個數(shù)相同的約束

正確的處理應(yīng)是先找出最大的和第二大的分別放入兩個數(shù)組，然后再找除去這兩個后的最大的和第二大的，再依據(jù)前一次
的差值確定第二次取的最大和第二大的數(shù)放進哪一個數(shù)組，依次類推

[ 本帖最后由 chzht001 于 2006-11-14 11:13 編輯 ]