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

dark_ql

int dist = 0;
int temp = 0;
for( int i=0; i<N; i++){
    if( abs(dist+A-B) < abs(dist+B-A) ){
          dist += A-B;
    }else{
          change(A,B);
          dist += A-B;
    }
}


說明：上述程序的目標(biāo)是使交換后A數(shù)組的和減去B數(shù)組的和的絕對(duì)值最小，也就是兩者之間相差最少
最終dist保存的即為兩者之間的差
我就寫了個(gè)例子驗(yàn)證了一下上述程序
A：  2   4    5    8
B：  1   7    6    9
按照上述規(guī)則，交換5-6，8-9，最終dist==0
如有錯(cuò)誤請(qǐng)大家指出

[ 本帖最后由 dark_ql 于 2006-11-18 23:59 編輯 ]

svenwang

這個(gè)帖子有點(diǎn)無聊了。很多人都只看第一貼，自己重復(fù)了別人的錯(cuò)誤還不知道。
要是說是微軟面試題估計(jì)更火爆。

erduo100

沒想出好的算法 我的思路把2n個(gè)數(shù)放在一個(gè)數(shù)組里 然后用組合找出n個(gè)數(shù) 求和 另n個(gè)數(shù)也求和 做查
求出所有這樣的差值的最小值，故復(fù)雜度為theta（ C(2n, n)）再把原數(shù)組的值經(jīng)過有限次的交換 調(diào)整成最優(yōu)解的數(shù)組值就行了
其中C(2n, n)用的是回溯 構(gòu)架是

1. 
   
2. void select_combination(int l, int p)
   
3. {
   
4.         int i;
   
5. 
   
6.         if (l == n)
   
7.         {
   
8.                 。。。
   
9.                 return;
   
10.         }
    
11. 
    
12.         for(i=p; i<=2*n-(n-l); ++i) //上個(gè)位置填的是num[p-1]，本次從num[p]開始試探
    
13.         {
    
14.                 b[i] = true;
    
15.                 select_combination(l+1, i+1); //填下一個(gè)位置
    
16.                 b[i] = false;
    
17.         }
    
18. }
    

復(fù)制代碼

下面是整個(gè)程序

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. const int n = 3;
   
6. int num[2*n];
   
7. bool b[2*n];
   
8. bool bc[2*n];
   
9. bool first = true;
   
10. int de, sumae, sumbe;
    
11. int mins;
    
12. 
    
13. void copy(bool p[], bool q[], int n)
    
14. {
    
15.         for (int i = 0; i < n; ++i)
    
16.         {
    
17.                 q[i] = p[i];
    
18.         }
    
19. }
    
20. 
    
21. void select_combination(int l, int p)
    
22. {
    
23.         int i;
    
24. 
    
25.         if (l == n)
    
26.         {
    
27.                 int suma = 0, sumb = 0;
    
28.                 for (i=0; i<2*n; ++i)
    
29.                 {
    
30.                         if (b[i])
    
31.                                 suma += num[i];
    
32.                         else
    
33.                                 sumb += num[i];                       
    
34.                 }
    
35. 
    
36. 
    
37.                 if (first)
    
38.                 {
    
39.                         first = false;
    
40.                         mins = abs(suma - sumb);
    
41.                         de = mins;
    
42.                         sumae = suma;
    
43.                         sumbe = sumb;                       
    
44.                 }
    
45.                
    
46.                 else
    
47.                 {
    
48.                         int d = abs(suma - sumb);
    
49.                         if (d < mins)
    
50.                         {
    
51.                                 mins = d;
    
52.                                 copy(b, bc, 2*n);
    
53.                                 de = mins;
    
54.                                 sumae = suma;
    
55.                                 sumbe = sumb;
    
56.                         }
    
57.                 }
    
58. 
    
59.                 return;
    
60.         }
    
61. 
    
62.         for(i=p; i<=2*n-(n-l); ++i) //上個(gè)位置填的是num[p-1]，本次從num[p]開始試探
    
63.         {
    
64.                 b[i] = true;
    
65.                 select_combination(l+1, i+1); //填下一個(gè)位置
    
66.                 b[i] = false;
    
67.         }
    
68. }
    
69. 
    
70. bool find(int a[], int n, int va, int& pos)
    
71. {
    
72.         for (int i = 0; i < n; ++i)
    
73.         {
    
74.                 if (va == a[i])
    
75.                 {
    
76.                         pos = i;
    
77.                         return true;
    
78.                 }
    
79.         }
    
80. 
    
81.         return false;
    
82. }
    
83. void swap(int& a, int& b)
    
84. {
    
85.         int tem = a;
    
86.         a = b;
    
87.         b = tem;
    
88. }
    
89. 
    
90. int main()
    
91. {
    
92.         int a[n] = {1,4, 7};
    
93.         int c[n] = {2,5,12};
    
94.         int i, suma = 0, sumc = 0;
    
95.         for (i = 0; i < 2*n; ++i)
    
96.         {
    
97.                 if (i < n)
    
98.                 {
    
99.                         num[i] = a[i];
    
100.                         suma += a[i];
     
101.                 }
     
102. 
     
103.                 else
     
104.                 {
     
105.                         num[i] = c[i-n];
     
106.                         sumc += c[i-n];
     
107.                 }
     
108.                
     
109.                 b[i] = false;
     
110.         }
     
111.         select_combination(0, 0);
     
112. 
     
113.         // 下面是追蹤交換的順序
     
114.         int ac[n], cc[n], p = 0, q = 0;
     
115.         for (i = 0; i < 2*n; ++i)
     
116.         {
     
117.                 if (bc[i])
     
118.                         ac[p++] = num[i];
     
119. 
     
120.                 else
     
121.                         cc[q++] = num[i];
     
122.         }
     
123. 
     
124.         p = 0;
     
125.         int pos;
     
126.        
     
127.         // 使a中的值與ac中的值相同
     
128.         while (p < n)
     
129.         {
     
130.                 if (a[p] == ac[p])
     
131.                 {
     
132.                         ++p;
     
133.                         continue;
     
134.                 }
     
135. 
     
136.                 else
     
137.                 {
     
138. 
     
139.                         if (find(c, n, ac[p], pos))
     
140.                         {
     
141.                                 printf("swap %d in a[%d] and %d in c[%d]\n",
     
142.                                                  a[p],   p,      c[pos],  pos);
     
143.                                 swap(a[p], c[pos]);
     
144.                         }
     
145. 
     
146.                         // a[p] 一定在數(shù)組a里 需交換3次
     
147.                         else
     
148.                         {
     
149.                                 find(a, n, ac[p], pos);
     
150. 
     
151.                                 printf("swap %d in a[%d] and %d in c[%d]\n",
     
152.                                                  a[p],   p,      c[0],  0);
     
153.                                 swap(a[p], c[0]);
     
154. 
     
155.                                 printf("swap %d in a[%d] and %d in c[%d]\n",
     
156.                                                  a[pos],   pos,      c[0],  0);
     
157.                                 swap(a[pos], c[0]);
     
158. 
     
159.                                 printf("swap %d in a[%d] and %d in c[%d]\n",
     
160.                                                  a[p],   p,      c[0],  0);
     
161.                                 swap(a[p], c[0]);
     
162.                         }
     
163.                 }
     
164.        
     
165.                 ++p;
     
166.         }
     
167. 
     
168.         // 使c中的值與cc中的值相同
     
169.         q = 0;
     
170.         while (q < n)
     
171.         {
     
172.                 if (c[q] == cc[q])
     
173.                 {
     
174.                         ++q;
     
175.                         continue;
     
176.                 }
     
177. 
     
178.                 else
     
179.                 {
     
180.                         find(c, n, cc[q], pos);
     
181. 
     
182.                         printf("swap %d in c[%d] and %d in a[%d]\n",
     
183.                                              c[q],   q,      a[0],  0);
     
184.                         swap(c[q], a[0]);
     
185. 
     
186.                         printf("swap %d in c[%d] and %d in a[%d]\n",
     
187.                                              c[pos],   pos,      a[0],  0);
     
188.                         swap(c[pos], a[0]);
     
189. 
     
190.                         printf("swap %d in c[%d] and %d in a[%d]\n",
     
191.                                              c[q],   q,      a[0],  0);
     
192.                         swap(c[p], a[0]);
     
193. 
     
194.                 }
     
195.                 ++q;
     
196.         }
     
197.         printf("\n交換前suma: %d, sumb: %d\n", suma, sumc);
     
198. 
     
199.         printf("交換后suma: %d, sumb: %d\n", sumae, sumbe);
     
200. 
     
201.         return 0;
     
202. }
     

復(fù)制代碼

wswn5456

原帖由 mike_chen 于 2006-11-13 09:34 發(fā)表
放到一個(gè)臨時(shí)數(shù)組里排序后，兩頭取，分別存在a,b里

我同意這個(gè)

lknh17

你們還在討論這個(gè)問題呢...題說交換，又沒說要給出交換的過程。。所以完整程序很簡(jiǎn)單......變個(gè)思維想想么
呵呵

lknh17

另外，xmyth 的算法是基于貪心的，所以并不是最優(yōu)的，只不過大多時(shí)候是最優(yōu)的而已

lknh17

再羅嗦點(diǎn).....認(rèn)清此題問題本是NP問題，就不會(huì)去想一些自以為很好的算法了
老老實(shí)實(shí)回朔剪枝吧，此題剪枝才是優(yōu)化的王道，目前我用了3處剪枝已經(jīng)將速度加速了很多
比較遺憾的是題目沒給n范圍，所以不好考慮剪枝的代價(jià)，所以我認(rèn)為不給出n的規(guī)模此題寫起來沒什么意義，
所以代碼也就不貼了。。。。

tank1111

參加tyc611 的帖子
發(fā)現(xiàn)xmyth算法的模型還是有問題，如tyc611的例子，同時(shí)交換不能只限于一個(gè)元素

我的想法：
也許可以拓展成只要找到x在(0, A], 合集，不是開集，就進(jìn)行交換

例子如下：
3,5,6,7,13,14   sum = 48
1,3,7,8,10,17   sum = 46

因?yàn)閍[1] - b[1] = 2,  在(0, 2]之間,　且沒有更逼近于A/2的選擇，故交換之

3,3,7,8,10,17    sum = 48
1,5,6,7,13,14    sum = 46
現(xiàn)在a[3] - b[3] = 1, 在(0,2]之間，　交換

3,3,6,8,10,17　 sum = 47
1,5,7,7,13,14    sum = 47

得到最佳結(jié)果

xmyth

我前面提出的算法的確是錯(cuò)誤的，貪婪算法在這種情況下不可行。

而樓上的想法也是錯(cuò)誤的，比如這個(gè)簡(jiǎn)單的例子就行不通了

a = {11,12,8,91}
b = {1,2,17,100}

動(dòng)態(tài)規(guī)劃算法對(duì)這個(gè)題目應(yīng)該是適用的
該題等價(jià)于在2n中元素中選取n個(gè)元素，使得這n個(gè)元素的和最接近于2n個(gè)元素總和的一半

/*
* 在數(shù)組c中的n個(gè)元素中選取m個(gè)元素，使得這m個(gè)元素的和最接近y
* func(c, n, m, y) 就表示這m個(gè)元素的和
* 然后通過比較func(c, n, m, y) 和 func(c + 1, n - 1, m, y) 就可以確定選取的這m個(gè)元素是哪幾個(gè)
*/

func(int *c, int n, int m, int y) {
  if (m == 0)
    return 0;
  if (n == m)
    return sum(c, n);
  a = func(c + 1, n - 1, m, y);
  b = func(c + 1, n - 1, m - 1, y - *c) + *c;
  return abs(y - a) <= abs(y - b) ? a:b;
}

[ 本帖最后由 xmyth 于 2006-11-21 21:01 編輯 ]