免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: 天魔封神霸

【华为公司Python面试题】,要求10分钟写出代码。。。 [复制链接]

论坛徽章:
0
发表于 2009-07-02 12:29 |显示全部楼层
贴一个试试

#l = range(1, 11)
l = [10001,10000,100,90,50,1]
#l = [1,2,3,4,5,6,700,800]
l.sort(reverse = True)

def sl(l):
    s = 0
    for i in l:
        s += i
    return s

avg = sl(l) / 2 # 求和的平均
print avg

r = []
for i in l: # 从大到小遍历
    s = sl(r + [i])
    if s < avg:
        r.append(i)
    elif s == avg:
        r.append(i)
        break
    else:
        # 当新加入的i大于avg时,需要特殊处理。
        if not r:
            r.append(i)
            continue
        t1 = s - i
        t2 = sl(r[:-1]) + i
        if abs(t1 - avg) > abs(t2 -avg): # 看新的i是否比上一个i为优
            r = r[:-1] + [i]

print r


[ 本帖最后由 nkchenz 于 2009-7-2 12:34 编辑 ]

论坛徽章:
0
发表于 2009-07-02 14:05 |显示全部楼层

回复 #11 nkchenz 的帖子

如果:
l = [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]

# ur answer:
12551 = [12312, 232, 3, 2, 1, 1]  
12580 = [12311, 210, 30, 29]      
差 29


12559 = [12312, 210, 30, 3, 2, 1, 1]
12572 = [12311, 232, 29]
差13
gdh 该用户已被删除
发表于 2009-07-02 16:22 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2009-07-02 17:28 |显示全部楼层

回复 #12 eookoo 的帖子

理解上也有偏差,题目要求最后的两个列表还是等长

论坛徽章:
0
发表于 2009-07-03 14:12 |显示全部楼层

回复 #13 gdh 的帖子

Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
Result List:    [1, 4, 5, 800] [2, 3, 6, 700]
Distance:       99

应该是

Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
Result List:    [1,2,3,800] [4,5,6,700]
Distance:       91

另外
Source List:    [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List:    [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance:       21
也不对

应该是
a=[1,1,29,232,12311]
b=[2,3,30,210,12312]
差为17

[ 本帖最后由 weizhe86 于 2009-7-3 15:10 编辑 ]
gdh 该用户已被删除
发表于 2009-07-03 16:19 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2009-07-03 22:36 |显示全部楼层

回复 #11 nkchenz 的帖子

sl可以直接使用sum函数嘛
另外你少考虑一些东西

论坛徽章:
0
发表于 2009-07-04 16:41 |显示全部楼层

大家可以用这个程序检测自己的结果是不是正确

#coding=utf-8
souce=[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
souce.sort(reverse=True)
l=len(souce)
avg=sum(souce)/2.0
def changeone(n,liu):
    li=liu
    lis=[[v for v in li]]
    for i in range(l):
        if not i in liu:
            li[n]=i
            lis.append([v for v in li])
    lin=[]
    if n<l/2-1:
        for lii in lis:
            lin+=(changeone(n+1,lii))
    return lin+lis
li=changeone(1,range(l/2))
mincha=sum([souce[x] for x in li[0]])
for i in li:
    s=sum([souce[x] for x in i])
    if abs(s-avg)<abs(avg-mincha):
        mincha=s
        print mincha*2-sum(souce),[souce[x] for x in i]

将所有分组方法的结果都计算出来,输出差值最小的那种分法。效率最慢(华为不会使用这种方法的),能保证准确性,随意推荐给大家做检查用。

论坛徽章:
0
发表于 2009-07-05 04:05 |显示全部楼层
把两个序列合并,然后排序,然后索引奇分一个列,索引偶数再分一个列就行了.

论坛徽章:
0
发表于 2009-07-06 17:16 |显示全部楼层

回复 #19 needspeedboy 的帖子

你觉得华为会出这么幼稚的题目吗
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP