一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 7529|回复: 36
收起左侧

[学Python/Perl] 一些刷题常用的 python 技巧

    [复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
chancidy | 显示全部楼层 |阅读模式
本楼: 👍   100% (20)
 
 
0% (0)   👎
全局: 👍   100% (123)
 
 
0% (0)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
Python 越来越多地成为大家刷题的主流语言,主要原因是它的语法非常简洁明了。因此我们能节省更多的时间,来关注算法和数据结构本身。

而用好 Python 自身独有的一些语法特性,不仅能更节省时间,也能让代码看起来更加优雅。这里我总结了一些我自己刷题过程中用到的一些常用的功能。以下以 python3 为例, python2 略有差异。

List
Python 的列表 List 基本就是其它语言的 Array.

Initialization 初始化
List 的初始化一般用 List comprehension,往往能一行解决问题

[Python] 纯文本查看 复制代码
# 1d array
l = [0 for _ in range(len(array)]
# or
l = [0] * len(array)

# 2d
l = [[0] for i in range(cols) for j in range(rows)]


# or
l = [0] * len(array)[/mw_shl_code]
l = [0 for _ in range(len(array)]
# or
l = [0] * len(array)[/mw_shl_code]


# 2d
l = [[0] for i in range(cols) for j in range(rows)]
Start from the behind
你可以轻松从后往前访问:

lastElement = l[-1]

lastTwo = l[-2:]

for i in range(0, -10, -1)
# 0, -1, -2, -3, -4, -5, -6, -7, -8, -9

copy 复制

shallow copy 浅拷贝

l2 = l1[:]
# or
l2 = l1.copy()
浅复制的问题在于,如果 l1 内部还有 list,那么这种嵌套的索引不能被复制,比如:

[Python] 纯文本查看 复制代码
a = [1, 2, [3, 4]]
b = a[:]
a[2].append(5)
print(b)
# [1, 2, [3, 4, 5]]


deep copy 深拷贝

所以如果要做深拷贝,要节制自带库 copy

import copy

copy.deepcopy()

enumerate 枚举

当我们需要枚举一个数组并同时获得值与 index 的时候可以使用:

l = ["a", "b", "c"]

for i, v in enumerate(l):
    print(i, v)
# 0 a
# 1 b
# 2 c

zip

zip 本意就是拉链,可以想象成将两个数组像拉链一样挨个聚合:

[Python] 纯文本查看 复制代码
>>> x = [1, 2, 3]
>>> y = [4, 5, 6]
>>> zipped = zip(x, y)
>>> list(zipped)
[(1, 4), (2, 5), (3, 6)]


reduce

reduce 可以分别对相邻元素使用同一种计算规则,同时每一步结果作为下一步的参数,很典型的函数式编程用法。
[Bash shell] 纯文本查看 复制代码
# importing functools for reduce()
import functools
# initializing list
lis = [ 1, 3, 5, 6, 2, ]

# using reduce to compute sum of list
print ("The sum of the list elements is : ",end="")
print (functools.reduce(lambda a,b : a+b,lis))

# The sum of the list elements is : 17


map

可以将参数一一映射来计算, 比如

date = "2019-8-15"
Y, M, D = map(int, date.split('-'))
# Y = 2019, M = 8, D = 15

deque

list 删除末尾的操作是O(1)的,但是删除头操作就是O(n),这时候我们就需要一个双端队列 deque。首尾的常规操作为:

append,添加到末尾
appendleft, 添加到开头
pop, 剔除末尾
popleft,移除开头

sorted

list 自身有自带的 sort(), 但是它不返回新的 list. sorted 能返回一个新的 list, 并且支持传入参数reverse。

比如我们有一个 tuple 的数组,我们想按照 tuple 的第一个元素进行排序:

l1 = [(1,2), (0,1), (3,10) ]

l2 = sorted(l1, key=lambda x: x[0])

# l2 = [(0, 1), (1, 2), (3, 10)]
这里的 key 允许传入一个自定义参数,也可以用自带函数进行比较,比如在一个 string 数组里只想比较小写,可以传入key=str.lower

l1 = ["banana","APPLE", "Watermelon"]
l2 = sorted(l1, key=str.lower)
print(l2)

# ['APPLE', 'banana', 'Watermelon']
lambda
你注意到我们在上面使用了 lambda 来定义一个匿名函数,十分方便。如果你熟悉其它语言类似 JS 的话,可以把它理解成一个 callback 函数,参数名一一对应就行。

cmp_to_key

在 python3 中,sorted 函数取消了自带的cmp函数,需要借助functools 库中的 cmp_to_key来做比较。
比如如果要按照数组元素的绝对值来排序:

[Bash shell] 纯文本查看 复制代码
from functools import cmp_to_key
def absSort(arr):
    newarr = sorted(arr, key = cmp_to_key(sortfunc))
    return newarr
def sortfunc(a, b):
    if abs(a) < abs(b):
      return -1
    elif abs(a) > abs(b):
      return 1
    else:
      return a - b


set

set 的查找操作复杂度为O(1),有时候可以替代dict 来存储中间过程。

add : set 的添加是 add 不是append
remove vs discard: 都是删除操作,区别在于remove不存在的元素会报错,discard不会。
union, intersection: 快速获得并集和交集,方便一些去重操作。

dict

字典,相当于其它语言中的map, hashtable, hashmap之类的,读取操作也是O(1) 复杂度

keys(), values(), items()
这三个方法可以分别获得key, value, {key: value}的数组。

setdefault

这个函数经常在初始化字典时候使用,如果某个key在字典中存在,返回它的value, 否则返回你给的 default 值。比如在建一个 trie 树的时候

[Python] 纯文本查看 复制代码
node = self.root
for char in word:
     node = node.setdefault(char, {})


OrderedDict

OrderedDict 能记录你 key 和 value 插入的顺序,底层其实是一个双向链表加哈希表的实现。我们甚至可以使用move_to_end这样的函数:

>>> d = OrderedDict.fromkeys('abcde')
>>> d.move_to_end('b')
>>> ''.join(d.keys())
'acdeb'
# 放开头
>>> d.move_to_end('b', last=False)
>>> ''.join(d.keys())
'bacde'

defaultdict

defaultdict可以很好地来解决一些初始化的问题,比如 value 是一个 list,每次需要判断 key 是否存在的情况。这时我们可以直接定义

d = defaultdict(list)

s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
for k, v in s:
     d[k].append(v)
sorted(d.items())
# [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

heapq

heapq 就是 python 的 priority queue,heapq[0]即为堆顶元素。

heapq 的实现是小顶堆,如果需要一个大顶堆,常规的一个做法是把值取负存入,取出时再反转。
以下是借助 heapq 来实现 heapsort 的例子:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

bisect

python 自带二分查找的库,在一些不要求实现 binary search,但是借助它能加速的场景下可以直接使用。

bisect.bisect(a, x, lo=0, hi=len(a))
这里的参数分别为 数组,要查找的数,范围起始点,范围结束点
相似函数还有

bisect.bisect_left
bisect.bisect_right
分别返回可以插入 x 的最左和最右 index

Counter

Counter 接受的参数可以是一个 string, 或者一个 list, mapping

>>> c = Counter()                           # a new, empty counter
>>> c = Counter('gallahad')                 # a new counter from an iterable
>>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
>>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args
most_common(n)
可以得到出现次数最多的 n 个数:
>>> Counter('abracadabra').most_common(3)  # doctest: +SKIP
[('a', 5), ('r', 2), ('b', 2)]

strings

ord, char

ord 返回单个字符的 unicode:

>>> ord('a')
97
char 则是反向操作:

>>> chr(100)
'd'

strip

移除 string 前后的字符串,默认来移除空格,但是也可以给一个字符串,然后会移除含有这个字符串的部分:

>>> '   spacious   '.strip()
'spacious'
>>> 'www.example.com'.strip('cmowz.')
'example'

split

按照某个字符串来切分,返回一个 list, 可以传入一个参数maxsplit来限定分离数。

>>> '1,2,3'.split(',')
['1', '2', '3']
>>> '1,2,3'.split(',', maxsplit=1)
['1', '2,3']
>>> '1,2,,3,'.split(',')
['1', '2', '', '3', '']

int/ float

最大, 最小 number
有时候初始化我们需要设定 Math.max() 和 Math.min(), 在 python 中分别以 float('inf') 和 float('-inf')表示

我们也可以这么做:

[Python] 纯文本查看 复制代码
import sys

#maxint
Max = sys.maxint


除法

在 python3 中, / 会保留浮点,相当于 float 相除,如果需要做到像 pyhton2 中的 int 相除,需要 //:

>>> 3 / 2
1.5
>>> 3 // 2
1
次方
在 python 中为 **:

>>> 2 ** 10
1024

conditions

在 python 的三项表达式(ternary operation) 与其它语言不太一样:

res = a if condition else b
它表示如果 condition 满足,那么 res = a, 不然 res = b,在类 c 的语言里即为:

res = condition ? a : b;

any, all

any(), all()很好理解,就是字面意思,即参数中任何一个为 true 或者全部为 true 则返回 true。经常可以秀一些骚操作:
比如 36. Valid Sudoku 这题:

[Python] 纯文本查看 复制代码
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[x for x in y if x != '.'] for y in board]
        col = [[x for x in y if x != '.'] for y in zip(*board)]
        pal = [[board[i+m][j+n] for m in range(3) for n in range(3) if board[i+m][j+n] != '.'] for i in (0, 3, 6) for j in (0, 3, 6)]
        return all(len(set(x)) == len(x) for x in (*row, *col, *pal))


itertools
这是 python 自带的迭代器库,有很多实用的、与遍历、迭代相关的函数。

permutations 排列

permutations('ABCD', 2)
# AB AC AD BA BC BD CA CB CD DA DB DC

combinations 组合

combinations('ABCD', 2)
# AB AC AD BC BD CD

groupby 合并

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355852/Python-Groupby/322898

[k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
[list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D

functools

这个库里有很多高阶函数,包括前面介绍到的cmp_to_key 以及 reduce,但是比较逆天的有 lru_cache,即 least recently used cache. 这个 LRU Cache是一个常见的面试题,通常用 hashmap 和双向链表来实现,python 居然直接内置了。

用法即直接作为 decorator 装饰在要 cache 的函数上,以变量值为 key 存储,当反复调用时直接返回计算过的值,例子如下:

lru_cache
https://leetcode.com/problems/stone-game-ii/discuss/345230/Python-DP-Solution

[Python] 纯文本查看 复制代码
def stoneGameII(self, A: List[int]) -> int:
    N = len(A)
      for i in range(N - 2, -1, -1):
    A += A[i + 1]
      from functools import lru_cache
    @lru_cache(None)
    def dp(i, m):
        if i + 2 * m >= N: return A
        return A - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
    return dp(0, 1)


resource


这是一个大神用各种 Python trick 解题的 repo,可供娱乐:

https://github.com/cy69855522/Shortest-LeetCode-Python-Solutions

当然 Leetcode 讨论区还会经常见到 StefanPochmann 或者 lee215这样的大神 Po 一些很秀技的 python 代码,都是学习范本

评分

参与人数 94大米 +257 收起 理由
isabella_h + 1 很有用的信息!
gralance + 1 很有用的信息!
jerrys0 + 2 很有用的信息!
wzxywzl + 1 给你点个赞!
qrune + 1 赞一个
ysd2503 + 2 很有用的信息!
duanj99 + 2 谢谢分享!
jump22jump + 2 gooood
sherry715 + 1 很有用的信息!
Jie0826 + 2 很有用的信息!

查看全部评分


上一篇:学习算法的一本免费电子书《初等算法》国人写的
下一篇:各位面试的时候,碰到位运算的多吗
我的人缘0
juggernaught 2019-8-18 06:43:22 | 显示全部楼层
本楼: 👍   100% (8)
 
 
0% (0)   👎
全局: 👍   94% (314)
 
 
5% (17)    👎
Python 3没有sys.maxint了,这个可能返回64位最大整数了。
可以用sys.maxsize 这个返回 2147483647
如果想要负无穷 要用 -sys.maxsize - 1

另外开list的时候 *都是浅拷贝第一个, for _ in range(x) 是每次new一个
a = [[]] * 3
a
[[], [], []]
a[0].append(1)
a
[[1], [1], [1]]


a = [[] for _ in range(3)]
a
a[0].append(1)
a
[[1], [], []]

这点一定要注意,最好就是都用for 的方法开,避免错误

评分

参与人数 13大米 +32 收起 理由
qrune + 1 赞一个
rainbowzly + 1 赞一个
Kiriaki + 1 赞一个
wdlzz926 + 1 赞一个
starzero + 2 给你点个赞!
yyldzxx + 2 非常对,我以前用python时这块也出过错
wwwayne + 1 赞一个
new_wing + 1 赞一个
kiawe + 2 欢迎分享你知道的情况,会给更多积分奖励!
jane19930412 + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
torez 2019-8-18 08:05:42 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (83)
 
 
0% (0)    👎
我也添砖加瓦一下:https://github.com/brennerm/PyTricks

另外强烈安利一个地里比较冷门的语言Ruby,语法和Python某些程度上很像,实用的helper method巨多的一个语言

评分

参与人数 4大米 +6 收起 理由
starzero + 2 给你点个赞!
一亩菠萝地 + 1 给你点个赞!
jane19930412 + 2 很有用的信息!
cecilianxf + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| chancidy 2019-8-18 09:48:15 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (123)
 
 
0% (0)    👎
torez 发表于 2019-8-18 08:05
我也添砖加瓦一下:https://github.com/brennerm/PyTricks

另外强烈安利一个地里比较冷门的语言Ruby,语 ...

顶一下,这个不错。确实之前在尝试 ruby on rails 的时候是有这个感觉,实现同一个功能有各种不同的方法,不过目前除了一些startup,用rails的公司越来越少,不知道面试的可接受度怎么样
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (30)
 
 
3% (1)    👎
学习了学习了
回复

使用道具 举报

我的人缘0
 楼主| chancidy 2019-8-18 06:52:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (123)
 
 
0% (0)    👎
juggernaught 发表于 2019-8-18 06:43
Python 3没有sys.maxint了,这个可能返回64位最大整数了。
可以用sys.maxsize 这个返回 2147483647
如果 ...

谢谢指正,这个知识点很有用
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
nice,谢谢了
回复

使用道具 举报

我的人缘0
kuboy 2019-8-18 09:33:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (394)
 
 
6% (26)    👎
juggernaught 发表于 2019-8-18 06:43
Python 3没有sys.maxint了,这个可能返回64位最大整数了。
可以用sys.maxsize 这个返回 2147483647
如果 ...

python不都是用 float("inf")来表示最大值了吗
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-9-21 06:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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