近些年随着 python 的越来越火, python 也渐渐成为了很多程序员的喜爱. 许多程序员已经开始使用 python 作为第一语言来刷题.
最近我在用 python 刷题的时候想去找点 python 的刷题常用库 API 和刷题技巧来看看. 类似于 C++ 的 STL 库文档一样, 但是很可惜并没有找到, 于是决定结合自己的刷题经验和上网搜索做一份文档出来, 供自己和大家观看查阅.
1. 输入输出:
1.1 第一行给定两个值 n,m, 用空格分割, 第一个 n 决定接下来有 n 行的输入, m 决定每一行有多少个数字, m 个数字均用空格分隔.
解决办法: python 的 input 函数接收到的输入默认都是字符串, 所以我们使用 字符串切割, 强制类型转换, 列表生成器就可以完美解决输入问题. 代码如下:
- # 接收两个值, 使用 n,m 分别接收列表中的两个值
- n, m = [int(x) for x in input().split()]
- # 构造输入列表的列表
- num_list = []
- for i in range(n):
- # python 可以不用在意 m 的值, 将所有数值接收进来然后使用 len 判断长度
- tmp_list = [int(x) for x in input().split()]
- num_list.append(tmp_list)
同理, 若是用逗号 (,) 分隔的话, split 函数中传入相同的值就行.
1.2 输出一行数字
由于 python 的 print 函数默认利用换行作为结束符, 所以我们需要将它修改成我们需要的间隔, 代码如下:
- for i in range(10):
- print(i, end=' ')
end 是 print 函数中的一个参数, 决定输出的结束字符, 这里修改成空格代表输出一行数字, 用空格间隔, 其它字符可以自行修改.
2. 空列表生成, 字符串修改, 列表遍历
2.1 代码编写过程中, 有时候会需要一个带有长度的, 有初始值的空列表, 生成方式如下:
- # 1. 用乘法生成一个初始值为 False 的长度为 100 的一维列表
- visited = [False] * 100
- # 2. 利用列表生成器生成一个 n*m 的二维的初始值为 0 的列表
- visited = [[0 for i in range(m)] for j in range(n)]
2.2 在 python 当中字符串是无法原地修改的, 如果每次修改都生成一个新字符串, 那么对修改次数很多且字符串很当的情况, 开销是很大的. 所以一般是把字符串转为列表进行修改最后再转回来.
- string = 'I love to eat chicken'
- # 将字符串转换成列表
- string_list = list(string)
- # ....... 对字符串列表进行修改
- # Code
- # 将字符串列表重新拼接成字符串
- #string = ''.join(string_list)
2.3 python 中列表遍历有许多种不同的方式, 最直接的办法是直接对列表进行迭代遍历, 但是因为我们往往是基于索引对数组进行操作且需要修改数组的值, 所以更推荐用以下代码中的第二三中办法:
- num_list = [i for i in range(10)]
- # 1. 直接迭代列表
- for item in num_list:
- # Code
- pass
- # 2. 通过索引进行迭代
- for i in range(len(num_list)):
- print(num_list[i])
- # 3. 通过 enumerate 函数进行迭代
- for index, value in enumerate(num_list):
- # index 为当前元素的索引, value 为当前元素的值
- print(index, value)
3. collections 库的使用
3.1 deque 队列
deque 是 python 中的队列(FIFO 先进先出), 队列在进行队首弹出的时候会比 list 要快.
尤其在使用 BFS(深度优先搜索)的时候, 队列是必须要使用到的. 部分 deque 使用代码如下:
- from collections import deque
- # 初始化一个最大长度为 3 的队列
- d = deque([1,2,3], maxlen=3)
- # 因为初始化队列最大长度为 3, 再添加元素会把队头元素挤出
- d.append(4)
- # 初始化一个不限制长度的队列
- d = deque()
- # 添加元素到队尾部
- d.append(1)
- d.append(2)
- d.append(3)
- # 将队首的元素弹出返回
- print(d.popleft())
- # 弹出队尾元素并返回值
- print(d.pop())
- # 在队首插入元素
- d.appendleft(0)
3.2 Counter 计数器
Counter 是一个计数器, 可以对一个序列计数, 计算序列中某个元素出现的数量.
以下是示例代码:
- import collections
- # 一共有三种初始方法
- # 1. 传入一个序列
- print(collections.Counter(['a', 'b', 'c', 'a', 'b', 'b']))
- # 2. 传入一个字典
- print(collections.Counter({'a':2, 'b':3, 'c':1}))
- # 3. 直接利用 = 传参
- print(collections.Counter(a=2, b=3, c=1))
- # 也可以无参数构造, 利用 update 函数更新
- c = collections.Counter()
- print('Initial :', c)
- # Initial: Counter()
- c.update('abcdaab')
- print('Sequence:', c)
- # Sequence: Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})
- c.update({'a':1, 'd':5})
- print('Dict:', c)
- # Dict: Counter({'d': 6, 'a': 4, 'b': 2, 'c': 1})
- # 可以通过访问字典的访问方式访问 Counter 对象
- for letter in 'abcde':
- print('%s : %d' % (letter, c[letter]))
- # elements()方法可以返回一个包含所有 Counter 数据的迭代器
- c = collections.Counter('extremely')
- c['z'] = 0
- print(list(c.elements()))
- # ['e', 'e', 'e', 'm', 'l', 'r', 't', 'y', 'x']
- # most_common()返回前 n 个最多的数据
- c=collections.Counter('aassdddffff')
- for letter, count in c.most_common(2):
- print('%s: %d' % (letter, count))
- # f: 4
- # d: 3
- # Counter 对象可以进行加减交并, 直接使用运算符 +,-,&,|
- # + 会将两个字典中相同字符的出现次数相加,- 会给出第一个 Counter 相对于第二个的差集. 交集给出两个计数器当中都有的元素, 且计数被赋值为较小的那个, 并集为两个计数器的元素出现最多的那个.
- c1 = collections.Counter(['a', 'b', 'c', 'a', 'b', 'b'])
- c2 = collections.Counter('alphabet')
- print ('C1:', c1)
- print ('C2:', c2)
- print ('\nCombined counts:')
- print (c1 + c2)
- print ('\nSubtraction:')
- print (c1 - c2)
- print ('\nIntersection (taking positive minimums):')
- print (c1 & c2)
- print ('\nUnion (taking maximums):')
- print (c1 | c2)
- # 以下为输出:
- C1: Counter({'b': 3, 'a': 2, 'c': 1})
- C2: Counter({'a': 2, 'l': 1, 'p': 1, 'h': 1, 'b': 1, 'e': 1, 't': 1})
- Combined counts:
- Counter({'a': 4, 'b': 4, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})
- Subtraction:
- Counter({'b': 2, 'c': 1})
- Intersection (taking positive minimums):
- Counter({'a': 2, 'b': 1})
- Union (taking maximums):
- Counter({'b': 3, 'a': 2, 'c': 1, 'l': 1, 'p': 1, 'h': 1, 'e': 1, 't': 1})
3.3 defaultdict-- 带有默认值的字典
一般情况下创建的字典 dict 是不含有默认值的, 即若是字典中不包含 a 这个 key, 调用 dct{a}的话就会报错.
在进行算法设计和数据结构设计的时候我们希望任意给定一个 key 都能从字典中取出值来, 哪怕只是一个默认值, 这个时候我们就需要用到 defaultdict.
例如在用字典表示图中一个节点的相连节点的时候, 我们希望将这个节点作为一个 key, 然后与它相连的节点组成一个列表作为它的 value, 这个时候我们就可以使用 defaultdict(list)来创建一个默认值为列表的字典.
- # list 的默认值为空列表
- list_dict = collections.defaultdict(list)
- # int 的默认值为 0
- int_dict = collections.defaultdict(int)
- print(list_dict['a'])
- print(int_dict['a'])
- # 输出:[]
- # 输出: 0
3.4 小结
collection 中常被用来写算法和数据结构的就是这几个, 其它比如排序字典和命名元组很少会用上.
4. 排序
4.1 对列表排序
对列表排序有两种方法, 一种是使用列表内置的 sort 函数, sort 函数直接在列表原地修改, 无返回值, 可以通过参数 key 自定义比较的 key 和比较函数.
第二种就是使用 python 的 sorted 函数, 这个函数自由度比较高, 可以自己设定比较函数和比较的 key, 返回一个新的列表.
如果需要自定义比较的函数, 需要从库 functools 导入函数 cmp_to_key 函数, 将比较函数转为 key, 使用代码如下:
- def custom_sort(x,y):
- if x>y:
- # 返回 - 1 代表需要排在前面
- return -1
- if x<y:
- # 返回 1 代表需要排在后面
- return 1
- return 0
- lst = [i for i in range(10, -1, -1)]
- print(lst)
- lst.sort()
- print(lst)
- print(sorted(lst, key=cmp_to_key(custom_sort)))
- # 输出如下:
- # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
- # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
4.2 对字典 / 元组列表排序
若是需要对字典 (将字典利用 item 函数转化成元组列表) 或者元组列表这种每一个 item 有两个值的序列进行排序, 这个时候就需要利用 sorted 函数中的 key 来决定取哪个值排序. 代码如下:
- # 利用字符串创建计数器字典
- d = dict(collections.Counter('Hello World'))
- print(d)
- # 排序
- print(sorted(d.items(), key=lambda x: x[1], reverse=True))
- # 输出如下:
- # {
- 'H': 1, 'e': 1, 'l': 3, 'o': 2, '': 1,'W': 1,'r': 1,'d': 1}
- # [('l', 3), ('o', 2), ('H', 1), ('e', 1), ('', 1), ('W', 1), ('r', 1), ('d', 1)]
5. 排列组合
python 内置的模块 itertools 中集成了一些与迭代有关的函数, 其中就有排列组合函数.
5.1 排列
排列函数 permutations 接收一个列表, 返回这个列表内所有元素的全排列列表.
- from itertools import permutations
- print(list(permutations([1,2,3])))
- # 输出如下:
- # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
5.2 组合
组合函数 combinations 接收两个参数, 第一个为一个需要进行组合的列表, 第二个参数为一个正整数, 代表从列表中抽取多少个元素进行组合, 返回一个组合列表.
- from itertools import combinations
- print(list(combinations([1,2,3],2)))
- # 输出如下:
- # [(1, 2), (1, 3), (2, 3)]
6. 小技巧
6.1 在 python 中分了可变类型和不可变类型, 当函数传参的时候:
若是不可变类型如字符串, 则传递参数的时候会深拷贝一份, 在新的数据上修改并不改变原数据
若是可变类型如列表, 则传递参数的时候传递的是引用, 属于浅拷贝, 在函数中对新列表进行操作会影响到原来的列表.
若是确实需要传递可变类型进入函数, 则可以在函数内部第一行进行一次深拷贝如:
- def test(num_list:list):
- # 进行深拷贝
- num_list = num_list[:]
6.2 当删除列表中的元素的时候, 列表后面的元素会自动往前移动, 导致出错
例如, 列表为[1,2,3,4,5,6], 想要删除列表中的偶数, 如果直接找到一个偶数然后利用其索引删除, 如下代码所示(错误示范), 那么很抱歉, 出问题了.
- # 此处为错误示范!!!!!!!!
- lst = [1, 2, 3, 4, 5, 6]
- for i in range(len(lst)):
- if lst[i] % 2 == 0:
- lst.pop(i)
- print(lst)
- # 上面这段代码没有输出, 因为报索引越界错误了.
下面的代码才是正确示范:
- lst = [1, 2, 3, 4, 5, 6]
- lst = [i for i in lst if i % 2 != 0]
- print(lst)
- # 输出如下:
- # [1, 3, 5]
若是需要更复杂的筛选手段, 可以在 if i%2 !=0 那里更改成一个函数判断, 函数内部就实现筛选方法.
6.3 访问字典元素要使用 get 方法
前文说过, 普通的 dict 字典是没有默认值的, 所以这个时候如果直接利用中括号放置 key 来查找 value 的话是有可能会报错的.
那么为了避免这种情况, 在利用字典的 key 来取 value 的时候, 需要利用字典的 get 函数.
get 函数的第一个参数为 key, 第二个参数为可选(默认为 None), 当字典中找不到传入的 key 的时候, 会返回第二个参数所赋的值.
7. 小结
以上是本人在使用 python 刷题的时候作的一些总结, 若有不到位的地方请指出.
本文旨在为自己做一个文档, 同时也为大家提供一些便利.
关注我的公众号[程序小员] , 收货一大波福利知识.
我是落阳, 谢谢你的到访.
来源: https://segmentfault.com/a/1190000037505191