一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 756|回复: 10
收起左侧

[学Python/Perl] Python刷题的一些技巧分享

[复制链接] |试试Instant~ |关注本帖
OO0OO 发表于 2016-10-25 06:49:57 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
有的时候

**用Python解题经常可以作弊,Python 处理string非常方便, python内置模块非常多,比如排列组合啥的各种....**

有的时候

**Python大法好,就是偶尔慢**


Python也是可以追求运行速度的,除了算法方面的提升,也有些常见函数之间的区别

还有我刷的Python 2 和 3 已经迷茫了,如果有说错的地方敬请指出


===========初级技巧=================


-  排序

用lst.sort() 而不是nlst = sorted(lst)

区别在于lst.sort()是 in-place sort,改变lst, sorted会创建新list,成本比较高。


- 用xrange

xrangge 和 range的区别是在于 range会产生list存在memory中,xrange更像是生成器,generate on demand

所以有的时候xrange会更快

-  三目运算符

python 的三目运算符是这么写的 x if y else z

考虑这种list of list: matrix = [ [1,2,3] , [4,5,6] ]

row  = len(matrix)
col = len(matrix[0]) if row else 0

这样写通用的原因是, 当matrix = [], row = 0, col =0

- list 填 0

lst = [0 for i in range(3)] # lst = [0,0,0]

lst  = [[0 for i in range(3)] for j in range(2)]  # lst =  [[0, 0, 0], [0, 0, 0]]


下面这种写法危险:

lst1 = [ 0, 0, 0 ]
lst2  = [lst1] * 2  # lst2 = [ [0,0,0] , [0,0,0] ]
lst2[0][0] = 1  # lst2 = [ [1,0,0], [1,0,0]]

因为lst1是object,这样写会踩坑


- D.get(key, default)

如果这个key 没有在dict里面,给它一个默认值:

D = {}
if 1 in D:
  val = D[1]
else :
  val = 0

等同于这样写:

val = D.get(1, 0)


- reverse list

lst = [1,2,3]

print lst[::-1] #[3,2,1]

lst 也有reverse函数

这也也适用于str, str可是没有reverse 函数的,str[::-1] 可用 √


=================进阶一下=====================

Python 也是有自己的数据结构的!!!!

- deque
  还在用list来做queue么? deque,当求快queue的时候,你值得拥有

- Counter
  Counter做啥就顾名思义了

- yield
  用yield不用return ( 我也还在学习阶段




import collections就可以用了,参见  collections — High-performance container datatypes



===============举个当时我就震惊了的例子===============


看到在stackoverflow上看到有人求这样一个数据结构:



  • Close to O(1) performance for as many of the following four operations.
  • Maintaining sorted order while inserting an object into the container.
  • Ability to peek at last value (the largest value) contained in the object.
  • Allowing for pops on both sides (getting the smallest or largest values).
  • Capability of getting the total size or number of objects being stored.
  • Being a ready made solution like the code in Python's standard library.


然后真的可以implement出来
  1. import collections
  2. import bisect

  3. class FastTable:

  4.     def __init__(self):
  5.         self.__deque = collections.deque()

  6.     def __len__(self):
  7.         return len(self.__deque)

  8.     def head(self):
  9.         return self.__deque.popleft()

  10.     def tail(self):
  11.         return self.__deque.pop()

  12.     def peek(self):
  13.         return self.__deque[-1]

  14.     def insert(self, obj):
  15.         index = bisect.bisect_left(self.__deque, obj)
  16.         self.__deque.rotate(-index)
  17.         self.__deque.appendleft(obj)
  18.         self.__deque.rotate(index)
复制代码
对此我只想表示牛,并且我硬生生的用它来解过人家不是要这种思路的题目。


有想到的再补充,也欢迎任何技巧分享





补充内容 (2016-10-28 00:40):
Python有built-inheap,是min heap.  heapq,如何来用它实现max heap呢,看到过一个有意思的方法是把key取负,比如把100变成-100,5变成-5。

评分

3

查看全部评分

elvenxzy 发表于 2016-10-25 09:18:27 | 显示全部楼层
赞一个楼主的分享,我也是刚入门。实在没什么能分享的。楼主把我能想到的都已经说了。
回复 支持 反对

使用道具 举报

渣渣程序员 发表于 2016-10-25 09:42:24 | 显示全部楼层
数据结构还有heapq这样的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sy10017667 发表于 2016-10-25 10:30:11 | 显示全部楼层
求python书推荐!看到多少函数算够?
回复 支持 反对

使用道具 举报

jedihy 发表于 2016-10-25 23:44:00 | 显示全部楼层
最后那个插入是o(n)的
回复 支持 反对

使用道具 举报

 楼主| OO0OO 发表于 2016-10-26 01:23:49 | 显示全部楼层
jedihy 发表于 2016-10-25 23:44
最后那个插入是o(n)的

是最后那个数据结构么? 所以是题主也写的是 Close  to,毕竟真心O(1)不太现实
回复 支持 反对

使用道具 举报

 楼主| OO0OO 发表于 2016-10-26 01:27:14 | 显示全部楼层
sy10017667 发表于 2016-10-25 10:30
求python书推荐!看到多少函数算够?

市面上的各种书入门都不错,比如 Learn Python the hard way

其实我觉得过一遍基础的语法就可以开始用起来,然后边用边学吧

然后如果你已经学过,只是要再熟悉语法的话,我推荐刚看到的这个 千行代码入门Python

回复 支持 反对

使用道具 举报

mayuki 发表于 2016-10-26 01:41:33 | 显示全部楼层
那个填list填0的陷阱我就犯过,debug了半天,我只要改一个value连着一串全被改了
回复 支持 反对

使用道具 举报

justin 发表于 2016-10-26 02:18:26 | 显示全部楼层
印象中python 3里range就是generator了,不需要特别指定xrange。

另外collections是神器,就像C++的stl还有Java的collections一样,极大提高效率
回复 支持 反对

使用道具 举报

jedihy 发表于 2016-10-26 04:20:22 | 显示全部楼层
justin 发表于 2016-10-26 02:18
印象中python 3里range就是generator了,不需要特别指定xrange。

另外collections是神器,就像C++的stl ...

是的,py3 没有xrange的
回复 支持 反对

使用道具 举报

jedihy 发表于 2016-10-26 04:22:04 | 显示全部楼层
2维dp初始化还可以写成dp = [[0] * n for _ in xrange(n)]更短
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 01:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表