华为面试题(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;
    }
}


说明：上述程序的目标是使交换后A数组的和减去B数组的和的绝对值最小，也就是两者之间相差最少
最终dist保存的即为两者之间的差
我就写了个例子验证了一下上述程序
A：  2   4    5    8
B：  1   7    6    9
按照上述规则，交换5-6，8-9，最终dist==0
如有错误请大家指出

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

svenwang

这个帖子有点无聊了。很多人都只看第一贴，自己重复了别人的错误还不知道。
要是说是微软面试题估计更火爆。

erduo100

没想出好的算法 我的思路把2n个数放在一个数组里 然后用组合找出n个数 求和 另n个数也求和 做查
求出所有这样的差值的最小值，故复杂度为theta（ C(2n, n)）再把原数组的值经过有限次的交换 调整成最优解的数组值就行了
其中C(2n, n)用的是回溯 构架是

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) //上个位置填的是num[p-1]，本次从num[p]开始试探
    
13.         {
    
14.                 b[i] = true;
    
15.                 select_combination(l+1, i+1); //填下一个位置
    
16.                 b[i] = false;
    
17.         }
    
18. }
    

复制代码

下面是整个程序

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) //上个位置填的是num[p-1]，本次从num[p]开始试探
    
63.         {
    
64.                 b[i] = true;
    
65.                 select_combination(l+1, i+1); //填下一个位置
    
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] 一定在数组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. }
     

复制代码

wswn5456

原帖由 mike_chen 于 2006-11-13 09:34 发表
放到一个临时数组里排序后，两头取，分别存在a,b里

我同意这个

lknh17

你们还在讨论这个问题呢...题说交换，又没说要给出交换的过程。。所以完整程序很简单......变个思维想想么
呵呵

lknh17

另外，xmyth 的算法是基于贪心的，所以并不是最优的，只不过大多时候是最优的而已

lknh17

再罗嗦点.....认清此题问题本是NP问题，就不会去想一些自以为很好的算法了
老老实实回朔剪枝吧，此题剪枝才是优化的王道，目前我用了3处剪枝已经将速度加速了很多
比较遗憾的是题目没给n范围，所以不好考虑剪枝的代价，所以我认为不给出n的规模此题写起来没什么意义，
所以代码也就不贴了。。。。

tank1111

参加tyc611 的帖子
发现xmyth算法的模型还是有问题，如tyc611的例子，同时交换不能只限于一个元素

我的想法：
也许可以拓展成只要找到x在(0, A], 合集，不是开集，就进行交换

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

因为a[1] - b[1] = 2,  在(0, 2]之间,　且没有更逼近于A/2的选择，故交换之

3,3,7,8,10,17    sum = 48
1,5,6,7,13,14    sum = 46
现在a[3] - b[3] = 1, 在(0,2]之间，　交换

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

得到最佳结果

xmyth

我前面提出的算法的确是错误的，贪婪算法在这种情况下不可行。

而楼上的想法也是错误的，比如这个简单的例子就行不通了

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

动态规划算法对这个题目应该是适用的
该题等价于在2n中元素中选取n个元素，使得这n个元素的和最接近于2n个元素总和的一半

/*
* 在数组c中的n个元素中选取m个元素，使得这m个元素的和最接近y
* func(c, n, m, y) 就表示这m个元素的和
* 然后通过比较func(c, n, m, y) 和 func(c + 1, n - 1, m, y) 就可以确定选取的这m个元素是哪几个
*/

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 编辑 ]