Archive for July, 2011

2011/07/22

学习python已经有2个月了,当然,是那种断断续续式的学习,囫囵吞枣的把《A byte of Python》看完了,大概知道了python的几个数据类型,了解了一些语法,然后又开始看《Dive into Python3》。 忘了提一句,我学的是Python3.X 而不是2.X。当初也是为了追求“最新”而选的,3.x和2.x的差别还是比较大的,很多时候遇到问题google一下发现网上的解决方法是2.x的,并不适用于3.x,无奈之下只好去翻官方手册。但是3.x的规范毕竟是以后Python语言的发展趋势,唯一的遗憾是目前很多第三方库还不支持3.x,比如图形库wxPython只支持2.x。 由于经常泡在豆瓣上,突然想起玩玩豆瓣的api,也顺便拿python练练手,学了这么长时间的python还没写过什么程序呢。于是就有了本文。 程序原理很简单,无非是通过api获取一些数据,然后在豆瓣返回的数据中提取有用的信息。输入豆瓣ID,然后显示昵称、个人简介等等。代码和截图如下。 Python老手以及熟悉网络开发的同学请无视~             import httplib2import xml.etree.ElementTree as etree h=httplib2.Http()name=input('Douban ID:') response,content=h.request('http://api.douban.com/people/'+name)string=bytes.decode(content) root=etree.fromstring(string) title=root.find('{http://www.w3.org/2005/Atom}title')bio=root.find('{http://www.w3.org/2005/Atom}content')links=root.findall('{http://www.w3.org/2005/Atom}link') for child in links:    if child.attrib['rel']=='homepage':        hp=child.attrib['href']print('[江湖人称]: {0}'.format(title.text))print('[自我简介]: {0}'.format(bio.text))print('[个人主页]: {0}'.format(hp))

Tags: . 12,388 views
2011/07/19

问题:有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。 比如,31,-41,59,26是它的一个连续的子串,他们的和为75。但是75并不是最大值,有一个子串 59,26,-53,58,97它们的和187才是最大的。 求解:《Programming Pearls》第77页开始一共给出了4种解法,前两种非常简单,是大多数人思考几分钟就能想出的方法,但是复杂度却很高,分别为O(n^3)和O(n^2)。后两种解法则非常巧妙,更神奇的是第四种方法居然只有线性复杂度O(n)! 解法1、解法2略。 解法3:分治法,复杂度为O(nlogn)。 分治法在结构上是递归的,在保证不改变原问题的条件下,将问题的规模减小,生成多个子问题,并多次递归调用自身来解决子问题,之后再将子问题的求解结果合并成原问题的解。

10,469 views