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

yuxh

原帖由 zhhui2000 于 2006-11-13 07:54 發(fā)表
先各自排序,再交叉存放較大無素

這個(gè)基本可行，但不是交叉存放較大元素，而是哪邊的和小就一直放大元素，直到n，然后把剩下的扔到另一組中就ok了。

greensky_34

for (i=0; i<N; i++)
    {
        for (j=0; j<N; j++)
        {
            change(a+i, b+j);
            if (abs(sum(a)-sum(b)) > ab_diff)
            {
                change(b+j, a+i);//如果不能使差值變小，則交換回去，也就是說不交換
            }
            else
            {
                ab_diff = abs(sum(a)-sum(b));//更新差值
            }
        }
    }

TC2測試

原帖由 namtso 于 2006-11-13 17:16 發(fā)表
我相信，這個(gè)題在8分鐘內(nèi)能寫出代碼來的人，絕對是大大的牛人。

我覺得應(yīng)該這樣：
a和b 分別求出累加和，得出累加和的差c1，然后循環(huán)查找找a中的某個(gè)元素a，使得a與b中的某個(gè)元素b[j]交換之后，得出一個(gè) ...

[ 本帖最后由 greensky_34 于 2006-11-13 20:29 編輯 ]

lebk

我有個(gè)想法，利用天平的原理：

１．兩端各有n個(gè)元素．其總重分別為：W1, W2,差為diff_w(W1,W2)


２．結(jié)束條件是，diff_w(W1,W2)小于等于左右兩邊中任意元素之差的最小值．

３．如果不滿足上述條件則進(jìn)行置換，置換的規(guī)則是，將上述兩邊任意二元素之差最接近diff(w1,w2)得元素進(jìn)行置換．.再重復(fù)上述步驟．

windy2335

原帖由 hithotwinds 于 2006-11-13 10:16 發(fā)表
剛學(xué)編程兩個(gè)月，不知道思路是否正確，錯(cuò)就一定有的。

#include"stdio.h"
com(int a[2000],int n)
{int i,j,p,q,s;
for(i=0;i<2*n-1;i++)
  {
a[0]=q,p=i;
  for(j=i+1;j<2*n;j++)
   ...

才兩個(gè)月能寫出這么長的程序還是不錯(cuò)滴。。。
                                        加油！！

apzc2529

原帖由 ccjjhua 于 2006-11-13 11:42 發(fā)表
把a(bǔ),b 2數(shù)組的元素放到數(shù)組3（2n大�。� 中進(jìn)行排序，
a 先取最小的，b先取次小的，
然后根據(jù)a,b已取元素和的大小來決定誰來取剩下元素中最小的。策略是，已取得的所有元素之和大的來取C中剩下元素中的最小者。如 ...

這種方法似乎很可行

s5unty

我寫了80分鐘，未果
當(dāng)時(shí)心想，TMD，難道這是google面試題嗎

qqq112233g

小弟覺得這個(gè)題目應(yīng)用動態(tài)規(guī)化來解：

原問題與下問題應(yīng)該屬同類。

有一組數(shù)a1,a2,a3,...,an. 求出一個(gè)子串，其各元素的和總元素和的一半差值最��！設(shè)總元素和為sum，

子串和為s_sub.  差值為dis[i][j],表示第 i個(gè)元素到j(luò) 個(gè)元素之間的子串和。每個(gè)元素有兩種狀態(tài)，1為選，0為不選。  
   
         當(dāng) i==j 時(shí) dis[i][j] = a[i] = a[j]
         當(dāng) i<j  時(shí) dis[i][i] = min{sum-s_sub-a[i], sum-s_sub}

這是大概思想，如有錯(cuò)誤望請正！

s5unty

原帖由 greensky_34 于 2006-11-13 20:25 發(fā)表
for (i=0; i<N; i++)
    {
        for (j=0; j<N; j++)
        {
            change(a+i, b+j);
            if (abs(sum(a)-sum(b)) > ab_diff)
            {
                change(b+j, ...

不行阿，我理解后用c實(shí)現(xiàn)，結(jié)果不正確，可能是我理解有問題？

1. 
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void change(int* a, int* b) {
   
7.     int t = *b;
   
8.     *a = t;
   
9.     *b = *a;
   
10. }
    
11. 
    
12. int diff(int a, int b) {
    
13.     return abs(a - b);
    
14. }
    
15. 
    
16. int main() {
    
17.     const int N = 3;
    
18.     int a[] = {1, 2, 3};
    
19.     int b[] = {0, 0, 99};
    
20.     const int sum_a = 6;
    
21.     const int sum_b = 99;
    
22. 
    
23.     int ab_diff = abs(sum_a - sum_b);
    
24.     for (int i=0; i<N; i++) {
    
25.         for (int j=0; j<N; j++) {
    
26.             change(a+i, b+j);
    
27.             if (abs(sum_a - sum_b) > ab_diff)
    
28.             {
    
29.                 change(b+j, a+i);//如果不能使差值變小，則交換回去，也就是說不交換
    
30.             }
    
31.             else
    
32.             {
    
33.                 ab_diff = abs(sum_a - sum_b);//更新差值
    
34.             }
    
35.         }
    
36.     }
    
37. 
    
38.     for (int i = 0; i < N; ++i) {
    
39.         cout << a[i] << " ";
    
40.     }
    
41.     cout << endl;
    
42. 
    
43.     for (int i = 0; i < N; ++i) {
    
44.         cout << b[i] << " ";
    
45.     }
    
46.     cout << endl;
    
47. }
    

復(fù)制代碼

kongqiang

>>有兩個(gè)數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序；
>>要求：通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小

這個(gè)與下面的等效。
數(shù)組 a:  a1,  a2, a3, ... an;
        b:  b1, b2, b3, ...  bn;
先從 a 中取 x 個(gè)元素， 再和 b 中的 n-x 個(gè)元素，把他們的值相加， 得 sumi;   
再從 a 中取剩下的 n-x 個(gè)元素， 和 b 中的 x 個(gè)元素，把他們的值相加， 得 sumj;
取 |sumi - sumj| 的絕對值為 subsum;

x 從 0 開始取到 n, 每次得到一個(gè) subsum, 最小的那個(gè) subsum 即所求的情況。
：）。
大概就是這樣的，用循環(huán)，呵呵。

chouy

1.  求和并除二, 記為 AVG
2.  用短的數(shù)組長度個(gè)的數(shù)字排列組合, 找最接近 AVG 的.
3.  把這幾個(gè)數(shù)填入短數(shù)組, 其余填入長數(shù)組.

不知道這道題中是否要求輸出換的步驟, 如果需要, 小 CASE. 不說了.