免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2009-08-05 14:11 |显示全部楼层
动态规划
Python会有这样的面试, 还是10分钟, 还是广告...

论坛徽章:
0
发表于 2009-08-24 00:57 |显示全部楼层
本帖最后由 starfuck 于 2019-11-26 23:48 编辑












论坛徽章:
0
发表于 2009-08-26 11:33 |显示全部楼层
十分钟怎么可能做出来,蒙人

论坛徽章:
0
发表于 2009-08-28 17:27 |显示全部楼层
穷举好了,又没要求算法的最优,反正也就是o(N^3)的复杂度

论坛徽章:
0
发表于 2009-08-29 00:41 |显示全部楼层
都有几个月没看python的代码了,看到这个题目还真的搞不出...

论坛徽章:
0
发表于 2009-08-31 08:56 |显示全部楼层

回复 #1 天魔封神霸 的帖子

#!/usr/bin/env python
# python 2.4+

a = [20,5,3]
b = [2,1,1]

def sum(lst):
    return reduce(lambda x,y: x+y,lst)

def do(d):
    global a,b
    x = -1

    for i in xrange(a):
        for j in xrange(b):
            c = a[ i] - b[j]
            if c > 0 and c <= d/2:
                if x == -1 or  c > x:
                    x = c
                    ai = i
                    bj = j

    if x == -1:
        return False
    else:
        a[ai],b[bj] = b[bj],a[ai]
        return True

def main():
    global a,b
    while True:
        if sum(a) < sum(b):
            a,b = b,a
        a.sort(reverse=True)
        b.sort(reverse=True)
        Diff = sum(a) - sum(b)

        if do(Diff):
            continue
        else:
            print a
            print b
            break

if __name__ == '__main__':
    main()


[root@web ~]# python test.py
[20, 1, 1]
[2, 5, 3]

虽然代码比较臃肿,但基本功能能实现。

[ 本帖最后由 toakee 于 2009-9-8 10:42 编辑 ]

论坛徽章:
0
发表于 2009-09-02 00:39 |显示全部楼层
本帖最后由 starfuck 于 2019-11-26 23:48 编辑












论坛徽章:
0
发表于 2009-09-07 09:56 |显示全部楼层
负数不比0小的吗?

论坛徽章:
0
发表于 2009-09-10 15:42 |显示全部楼层
我觉得楼主很无聊 大家每说一个他就说也不对 比如。。。。你干脆给出答案得了 卖什么关子 你说成ibm的面试题得了

论坛徽章:
0
发表于 2010-01-29 20:55 |显示全部楼层
解法思路在此:

http://blog.csdn.net/tangboyun/archive/2010/01/29/5270785.aspx
                                                                                      
为什么我说我的解法是这个问题的最优解?

依赖于三个特性:

一、就是交换a1和b1中的元素后,得到的新的a'和b'序列,它们依旧是从大到小排列的。无需再sort!!

二、得到的a1和b1序列,其下标,和之后用以操作swap函数的下标及求最合适石块(最合适的数值差),存在一个简单的转换关系。

三、 $smallRock[0]一定是原先2n个元素中,任意两元素差值的最小值!!!这个对用来测试最后还要不要交换,是至关重要的,没有这个概念的解法,不可能得到正确答案!!!!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP