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

ywj1225

1. #!/usr/bin/python
   
2. # -*- coding: utf-8 -*-
   
3. 
   
4. # 有两个数组a,b，大小都为n,数组元素的值任意，无序；
   
5. # 要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小
   
6. 
   
7. 
   
8. a = [1, 2, 3, 4, 5, 50]
   
9. b = [9, 8 ,7, 6, 100, 25 ]
   
10. 
    
11. c = a + b
    
12. 
    
13. c.sort()
    
14. c.reverse()
    
15. 
    
16. a = []
    
17. b = []
    
18. a.append(c[0])
    
19. b.append(c[1])
    
20. 
    
21. lenth = len(c)
    
22. i = 2
    
23. 
    
24. while i < lenth:
    
25.     if sum(a) > sum(b):
    
26.         if i+1 < lenth and sum(a) > sum(b) + c[i] + c[i+1]:
    
27.             b.append(c[i])
    
28.             a.append(c[lenth-1])
    
29.             i += 1
    
30.             lenth -= 1
    
31.             b.append(c[i])
    
32.             a.append(c[lenth-1])
    
33.             i += 1
    
34.             lenth -= 1
    
35.         elif sum(a) > sum(b):
    
36.             b.append(c[i])
    
37.             i += 1
    
38.             a.append(c[i])
    
39.             i += 1
    
40.         else:
    
41.             a.append(c[i])
    
42.             i += 1
    
43.             b.append(c[i])
    
44.             i += 1
    
45.     else:
    
46.         if i+1 < lenth and sum(b) > sum(a) + c[i] + c[i+1]:
    
47.             a.append(c[i])
    
48.             b.append(c[lenth-1])
    
49.             i += 1
    
50.             lenth -= 1
    
51.             a.append(c[i])
    
52.             b.append(c[lenth-1])
    
53.             i += 1
    
54.             lenth -= 1
    
55.         elif sum(a) > sum(b):
    
56.             a.append(c[i])
    
57.             i += 1
    
58.             b.append(c[i])
    
59.             i += 1
    
60.         else:
    
61.             b.append(c[i])
    
62.             i += 1
    
63.             a.append(c[i])
    
64.             i += 1
    
65. 
    
66.             
    
67. print a
    
68. print b
    
69.         
    
70. print sum(a)-sum(b)
    

复制代码

总体由大到小排序放入c中，最大的两个数分别放两个数组a和b里，如果a的和比b的和加上c里面剩余数字最大的两个还大的话，把c里面最大的两个数放入b中，最小的两个数放入a中；如果a的和单单比b的和大的话，把c中两个最大的数中大的放入b中，小的放入a中。。。
只是进行一些测试，不知道完全行得通不，还望指点。

发现问题很大了。

zhaofusun

回复 24# windy2335
不合适;;碱值扯淡




如果给你1, 2,3 ,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 的话永远不平衡

   

zhaofusun

《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉
《〈〈〈中国难道没有程序员了？？？？？！！！！！！！！！！！！！！！！〉〉吗？！


                       看来我是不能再低调了

还是我来讲讲吧

1:     首先将两个数组合并并排序,,,由大到小..
a[n] ; b[n]   -----> union[2n];

2; 清空a , b;并定义 变量addtoa; addtob;  diffe_ab;//diffe_ab是addtoa;addtob; 之差，

3: 暂且把union[0]---放addtoa-〉a[0]
         union[1] --->放addtob-〉b[0]
判断diffe_ab = addtoa -addtob//diffe_ab 可是个关键因素阿      问题的突破点都在这里，，，，//每一步具体算的时候还得分正负讨论。
diffe_ab 〉union[2n]-1]；
next cycle
addtoa-〉union[2n]-1]}/////最大程度的减小差距 每次都如此直到第n次循环
addtob-〉union[2]       }////


因为每次循环以后数组a[n]， b[n]，差距最小，最后一次亦是如此

如是此题得解；；；；

lovai

回复 431# vbs100

类似如下解法的：首先随机划分出两个子集，然后交换能使得和差降低(最多)的两个元素，直到找不到能降低的。
这是典型的爬山法，需要考虑有没有可能极值不是最值的情况。

当a和b长度不一样时，极值可能不是最值，如极值局面{1, 101, 50}和{70, 80}，这时需要一次性选择并交换两对元素才能达到最优解delta=0。
当a和b长度一样时[本题]，极值仍可能不是最值，不过得由于存在对称解，这种情况只可能出现在N>3的情况，如{2 , 3, 101, 50}和{0 , 4, 80, 70}，这时也需要一次性选择并交换两对元素才能达到最优解delta=0(sum(a)=155)。而上述算法的输出是sum(A)=156 sum(B)=154 sum(A)-sum(B)=2，显然是陷入局部极小值了。

下面给出“低效”但正确的DP解法：
抽象为问题：集合S划分为大小为n和n-|S|的两个子集，使得子集和之差最小。
DP：f(w, i)：到i为止，和为w的所有子集的长度的列表，
Ans = minw{abs(sum(S)/2 – w) | n in f(w, |S|)}
最坏复杂度O(W*|S|*|S|)

vbs100

回复 443# lovai


    你说的错误我看懂了，这样看来我那个确实是错误的解法。你说的算法没看懂，回去我研究下，谢谢指正，学习了

grassofsky

回复 442# zhaofusun


    没看明白，希望能把回复的内容整理下，谢谢。


    原谅我的低俗～～～～～～～～～～～

zhangtongjian

同求  这个题有意思

好吃的terry

8分钟解出来，纠结了8年还没答案，哎..

caihanwu8888

这是背包问题啊


   

路上风声

同意楼上的，这是背包问题的一种。八分钟能想到思路，但是我本人很难写出代码。
不过背包解法的思路不是很清晰，写另外一个思路供参考。
1.将a,b数组中的元素合并，按从大到小的顺序存储在一个线性链表c中;
2.设置标志变量flag,初始值为0;
3.在链表中从前往后每相邻两个元素做差值运算，找出差值最小的两个元素（当只有两个元素时，就取两个元素）.当flag==0的时候，比较的较大值放a,较小值放b,flag置1;当flag==1的时候,比较的较小值放a,较大值放b，flag置0.并在线性链表c中删除这两个元素.
4.重复步骤三直至链表所有元素取完，链表为空.
主要原因就是我每一步插入都保证了插入到a和b的两个元素差值最小，然后交叉的话，正好可以最大程度上的相互抵消，也算是背包思想了。