Python 刷题指南
# 前言
本文主要介绍 Python 刷题的一些技巧,以提高刷题效率,希望可以对大家有帮助
注:本文比较适合对于其他语言刷题有一定经验,想要快速熟悉 Python 刷题要点的读者。需要注意的是,本文采用
Python3
,与Python2
有一定区别,请注意使用
# 数据结构
# 有序序列
# 不可变序列
# str
- len() - 返回字符串的长度。
string_example = "Hello, World!"
length = len(string_example)
2
- lower() - 将字符串转换为小写。
string_example = "Hello, World!"
lowercase_string = string_example.lower()
2
如果是将首字母转化为小写,我们可以如下步骤,将首字母小写,然后在进行拼接
注意:Python 中的字符串是不可变的,因此我们不能直接修改字符串的某个字符,所以需要通过上述方式实现首字母小写
string_example = "Hello, World!"
lowercased_first_letter = string_example[0].lower() + string_example[1:]
2
- upper() - 将字符串转换为大写。
string_example = "Hello, World!"
uppercase_string = string_example.upper()
2
实现首字母大写,除了可以使用上面方式 Python 也有对应内置函数 capitalize()
string_example = "hello, world!"
capitalized_string = string_example.capitalize()
print("Capitalized string:", capitalized_string)
2
3
- strip() - 移除字符串两端的空格或指定字符。
string_example = " Hello, World! "
stripped_string = string_example.strip()
print("Stripped string:", stripped_string)
2
3
- replace() - 替换字符串中的子串。
string_example = "Hello, World!"
new_string = string_example.replace("World", "Python")
print("Updated string:", new_string)
2
3
- split() - 将字符串分割成列表。
string_example = "Hello, World!"
word_list = string_example.split(", ")
print("List of words:", word_list)
2
3
- join() - 将字符串列表连接成一个字符串。
word_list = ["Hello", "World!"]
joined_string = ", ".join(word_list)
print("Joined string:", joined_string)
2
3
- find() - 查找子串在字符串中的位置。
string_example = "Hello, World!"
position = string_example.find("World")
print("Position of 'World':", position)
2
3
常用功能
- 拼接:s 1 + s2
- 切片:s[start: end: space]
- 重复:s * 10
# tuple
元组(Tuple)是 Python 中的一种有序、不可变的数据类型。它由一系列元素组成,元素可以是不同的数据类型,例如整数、浮点数、字符串等。与列表不同,元组一旦创建,其内容就不能被修改,因此是不可变的,因此元组也被叫做静态列表
创建元组方式
# 使用小括号创建元组
my_tuple = (1, 2, 'three')
# 使用 tuple() 函数创建元组
another_tuple = tuple([4, 5, 6])
2
3
4
虽然元组元素数量不是固定的,但是需要注意,如果元组元素数量只有一个的时候,需要在元素后面添加一个逗号,示例如下
my_tuple = (1,)
如果我们是写作 my_tuple = (1)
的话,会发现 my_tuple 已经变成 int 整型,因为 python 认为 ()
为数学符号
访问方式和不可变性
注:因为元组是不可变的,无法对元组的元素进行修改、添加或删除,如果进行上述操作,将会导致 TypeError
my_tuple = (1, 2, 'three')
# 访问
print(my_tuple[0]) # 输出 1
print(my_tuple[2]) # 输出 'three'
# 以下操作会引发 TypeError
# my_tuple[0] = 0
# my_tuple.append(4)
# del my_tuple[1]
2
3
4
5
6
7
8
9
10
长度、包含判断和拆包
my_tuple = (1, 2, 'three')
print(len(my_tuple)) # 输出 3
print('three' in my_tuple) # 输出 True
print(4 in my_tuple) # 输出 False
my_tuple = (1, 2, 'three')
a, b, c = my_tuple
print(a) # 输出 1
print(b) # 输出 2
print(c) # 输出 'three'
2
3
4
5
6
7
8
9
10
11
12
同样支持上面的 拼接, 切片, 重复 功能
内置函数仅有:index
和count
# 可变序列
# list
经常使用的数据结构, 可以实现简单的队列, 栈等(经常用来实现单调栈)
常用功能: 拼接, 重复, 切片
强大的切片功能, 可用于取值, 替换, 删除等
lst[i:j] = t
, 其中 t 是可迭代序列del lst[i:j]
, 相当于lst[i:j] = []
.
常用函数
创建列表
my_list = [1, 2, 'three', 4.0]
another_list = list(range(5))
2
添加、删除元素
# 添加元素
my_list = [1, 2, 'three', 4.0]
my_list.append(5)
my_list.insert(2, 'new_element')
# 删除元素
my_list.remove('three')
popped_value = my_list.pop(1)
del my_list[0]
2
3
4
5
6
7
8
9
我们可以使用列表推导式创建列表,简化了列表的创建过程
squares = [x**2 for x in range(10)]
排序函数,不过sort()
方法是就地排序,它会直接修改原始列表,如果想要保留原始列表的顺序,可以使用 sorted()
函数
# 就地排序
my_list.sort(key=len(),reverse=True)
# 保留原列表
sorted(my_list, key=len(), reverse=True)
2
3
4
如果是元素为对象,需要自定义排序
# 根据对象的 age 属性进行排序
people.sort(key=lambda person: person.age)
2
其他函数
lst.clear() # 清空列表
lst.count(val) # val 个数
lst.extend(t) # 相当于 lst += t
lst.reverse() # 反转
2
3
4
# deque
一种链表的双向队列数据结构, 从该队列的头部或尾部插入或者删除一个元素, 时间复杂度是O(1). 可以用来表示先进先出的队列 (FIFO)
from collections import deque
# 创建
my_deque = deque([1, 2, 3, 4, 5])
my_deque.append(6)
my_deque.appendleft(0)
print(my_deque)
# 输出: deque([0, 1, 2, 3, 4, 5, 6])
right_element = my_deque.pop()
left_element = my_deque.popleft()
print(right_element, left_element)
# 输出: 6 0
my_deque.extend([6, 7, 8])
my_deque.extendleft([0, -1, -2])
print(my_deque)
# 输出: deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8])
# 将 deque 向右循环移动 `n` 步。如果 `n` 是负数,就向左移动
my_deque.rotate(2)
print(my_deque)
# 输出: deque([7, 8, -2, -1, 0, 1, 2, 3, 4, 5, 6])
# 清空队列
my_deque.clear()
# 返回指定元素的出现次数
my_deque.count(val)
# 在索引为 2 的位置插入元素 10
my_deque.insert(2, 10)
# 队列反转
my_deque.reverse()
# 删除指定元素
my_deque.remove(val)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# bisect
一种高效的折半搜索算法的类. 在 list 上用index
来查找某个元素, 所消耗的时间会与列表长度呈线性比例. 而 bisect 提供的bisect
等函数, 使用了二分折半搜索算法, 能够在排序之后的元素中查找某个值, 由bisect
函数所返回的索引, 表示待搜索的值在序列中的插入点.
import bisect
lst = list(range(10**6))
index1 = lst.index(654321)
index2 = bisect.bisect(lst, 987654)
2
3
4
二分查找法的复杂度是对数级别的. 也就是说, 用bisect
搜索100,000个元素的列表, 与用index
搜索14个元素的列表用的时间差不多.
常用函数
和折半查找一样, 使用这个模块的函数前先确保操作的列表是已排序的
import bisect
# 返回将x插入a后的位置索引
bisect.bisect(a, x, lo=0, hi=len(a))
# 将变量x插入到a中,并保持a升序
bisect.insort(a, x, lo=0, hi=len(a))
2
3
4
5
6
7
8
这里面 bisect 函数还有变种 bisect_right
表示返回插入位置(元素值相同则插入右侧,与 bisect 相同 ),同理也有 bisect_left
。同样,insort 也有对应变种函数,不过这些都不常用
bisect 操作不可以用于乱序或是逆序
# 无序序列
# 字典
字典一般是无序的(有序的为 OrderedDict
),键不可变, 值可变
# dict
创建字典
my_dict = {'key1': 'value1', 'key2': 'value2', 'key3': 'value3'}
my_dict = dict(key1='value1', key2='value2', key3='value3')
my_dict = dict([('key1', 'value1'), ('key2', 'value2'), ('key3', 'value3')])
# 字典推导式
my_dict = {key: f'value-{key}' for key in range(1, 4)}
# 创建具有指定键和相同默认值的字典
keys = ['key1', 'key2', 'key3'] default_value = 'default_value' my_dict = dict.fromkeys(keys, default_value)
2
3
4
5
6
7
8
9
10
11
12
修改,删除字典
# 访问
tinydict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
# 如果没有对应键则会报错
print(tinydict['Name'])
# 如果没有对应键,输出默认值 None
print(tinydict.get('Age'))
# 删除
# 删除键是'Name'的条目
# 没有该键会报错
del tinydict['Name']
# 清空字典所有条目
tinydict.clear()
# 删除字典
del tinydict
2
3
4
5
6
7
8
9
10
11
12
13
14
15
设置默认值
# 并没有改变源原字典
tinydict.get('Nam', None)
# 已经改变原字典,字典中如果有该键则没有改动
# 没有该键则会添加该键,值为默认值
tinydict.setdefault('Nam', None)
2
3
4
5
其他函数
keys() # 将字典的键组成新的可迭代对象
values() # 将字典中的值组成新的可迭代对象
items() # 将字典的键值对凑成一个个元组, 组成新的可迭代对象
update([other]) # 批量添加字典
pop(key[,default]) # 删除键,返回对应值,键不存在返回默认值
2
3
4
5
# defaultdict
在dict
中取值时, 如果 key 不存在, 那么会报KeyError
这样的错, 这时候可以使用get
方法来解决, 或者捕获异常. 但是这样会感觉很麻烦, 易错, 而且没有体现出 python 的简洁风格.
这时候就该defaultdict
登场了, 当试着去取不存在的值时, 就不会报错.
defaultdict 没有特殊的方法, 所以一下是它的简单用法
from collections import defaultdict
d = defaultdict(lambda : value)
# 当取一个不存在的 key 时, 会返回 value.
# 示例,默认值为 0
dict1 = defaultdict(int)
2
3
4
5
继承于dict
, 所以它拥有dict
一样的方法
# Counter
Counter 是 dict 字典的子类,Counter 拥有类似字典的 key 键和 value 值,只不过 Counter 中的键为待计数的元素,而 value 值为对应元素出现的次数 count,为了方便介绍统一使用元素和 count 计数来表示。虽然 Counter 中的 count 表示的是计数,但是 Counter 允许 count 的值为 0 或者负值
from collections import Counter
# 从可迭代对象中实例化 Counter
b = Counter("chenkc") # string
b2 = Counter(['c', 'h', 'e', 'n', 'k', 'c']) # list
b3 = Counter(('c', 'h', 'e', 'n', 'k', 'c')) # tuple
>>> print(b)
Counter({'c': 2, 'h': 1, 'e': 1, 'n': 1, 'k': 1})
>>> print(b2)
Counter({'c': 2, 'h': 1, 'e': 1, 'n': 1, 'k': 1})
>>> print(b3)
Counter({'c': 2, 'h': 1, 'e': 1, 'n': 1, 'k': 1})
2
3
4
5
6
7
8
9
10
11
12
13
# OrderedDict
有序字典, 使得插入的顺序有序
OrderedDict是记住键首次插入顺序的字典。如果新条目覆盖现有条目,则原始插入位置保持不变
from collections import OrderedDict
od=OrderedDict()
od['name'] = 'egon'
od['age'] = 18
od['gender'] = 'male'
print(od) # OrderedDict([('name', 'egon'), ('age', 18), ('gender', 'male')])
od['age']=19
print(od) # OrderedDict([('name', 'egon'), ('age', 19), ('gender', 'male')])
2
3
4
5
6
7
8
9
10
11
如果是普通字典,虽然输出一样,但是字典内部排序如下
# OrderedDict([('name', 'egon'), ('age', 18), ('gender', 'male'), ('age', 19)])
# 集合
集合 set ,主要是用于去重
注意:如果集合元素为空,不可以使用
{}
创建,否则 python 将会认为这是字典,需要使用s = set()
这样定义
add(elem) # 向集合中添加数据
update(*others) # 迭代着增加
clear() # 清空集合
discard(elem) # 删除集合中指定的值(不存在则不删除)
2
3
4
# 堆队列
可实现优先级队列的数据结构(优先队列). 可以解决 top n
问题, 如从1亿个数里面找出最大或最小的100个数
默认为最小堆/小根堆,堆数据结构最重要的特征是 heap[0] 永远是最小的元素
import heapq
heap = [] # 建堆
heapq.heappush(heap, item) # 往堆中插入新值
item = heapq.heappop(heap) # 弹出最小的值
item = heap[0] # 查看堆中最小的值, 不弹出
heapq.heapify(x) # 以线性时间将一个列表转为堆
item = heapq.heapreplace(heap, item) # 弹出一个最小的值, 然后将 item 插入到堆当中. 堆的整体的结构不会发生改变.
heapq.heappoppush(heap, item) # 弹出最小的值.并且将新的值插入其中.
heapq.merge(*iterables, key=None, reverse=False) # 将多个堆进行合并
heapq.nlargest(n, iterable, key=None) # 从堆中找出最大的 n 个数,key的作用和sorted( )方法里面的key类似, 用列表元素的某个属性和函数作为关键字
heapq.nsmallest(n, iterable, key=None) # 从堆中找出最小的 n 个数, 与 nlargest 相反
2
3
4
5
6
7
8
9
10
11
12
创建堆的方法可以是空列表使用 heapq.heappush
添加元素,添加之后自然就是最小堆,也可以使用已经有元素的列表,然后使用 heapq.heapify
转化为最小堆
python 中没有默认最大堆的实现方式,最简单的方法就是反转键值,例如将1000.0变成-1000.0,5.0变成-5.0,相当于就可以实现最大堆
# 其他
有些本身就是专用于排序的类,比如说: SortedList、SortedDict、SortedSet
from sortedcontainers import SortedList, SortedSet, SortedDict
单独讲下 SortedList ,其基本操作和列表基本相同,不同的就是其内部元素永远是排好序的,默认是顺序,如果想要逆序可以使用如下操作
from sortedcontainers import SortedList
from operator import neg
sl = SortedList([3, 5, 1, 2, 7, 6, 4], key=neg)
print(sl)
# output:
SortedKeyList([7, 6, 5, 4, 3, 2, 1], key=<built-in function neg>)
2
3
4
5
6
7
# 常用函数
enumerate(sequence, [start=0])
- sequence -- 一个序列、迭代器或其他支持迭代对象
- start -- 下标起始位置
for i, element in enumerate(seq):
print(i, element)
2
zip([iterable, ...])
- iterabl -- 一个或多个迭代器
zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的对象,这样做的好处是节约了不少的内存
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b) # 返回一个对象
>>> zipped
<zip object at 0x103abc288>
>>> list(zipped) # list() 转换为列表
[(1, 4), (2, 5), (3, 6)]
>>> list(zip(a,c)) # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> a1, a2 = zip(*zip(a,b)) # 与 zip 相反,zip(*) 可理解为解压,返回二维矩阵式
>>> list(a1)
[1, 2, 3]
>>> list(a2)
[4, 5, 6]
>>>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
reduce(function, iterable[, initializer])
- function -- 函数,有两个参数
- iterable -- 可迭代对象
- initializer -- 可选,初始参数
reduce() 函数会对参数序列中元素进行累积。
函数将一个数据集合(链表,元组等)中的所有数据进行下列操作:用传给 reduce 中的函数 function(有两个参数)先对集合中的第 1、2 个元素进行操作,得到的结果再与第三个数据用 function 函数运算,最后得到一个结果
# importing functools for reduce()
from functools import reduce
# initializing list
l = [1, 3, 5, 6, 2]
# using reduce to compute sum of list
print("The sum of the list elements is : ", end="")
print(reduce(lambda a, b: a + b, l))
# The sum of the list elements is : 17
2
3
4
5
6
7
8
9
10
range(start, stop[, step])
- start: 计数从 start 开始。默认是从 0 开始。例如 range(5) 等价于 range(0, 5)
- stop: 计数到 stop 结束,但不包括 stop。例如:range(0, 5) 是 [0, 1, 2, 3, 4] 没有 5
- step:步长,默认为 1。例如:range (0, 5) 等价于 range (0, 5, 1)
n = 10
print([x for x in range(n - 1, -1, -1)])
# output:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
2
3
4
all(iterable)
- iterable -- 元组或列表。
all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE,如果是返回 True,否则返回 False
元素除了是 0、空、None、False 外都算 True
注意:空元组、空列表返回值为 True,这里要特别注意
mat = [1, 2, 4, 5, 3]
lis = list(2 == i for i in mat)
print(lis)
print(all(lis))
# output:
[False, True, False, False, False]
False
2
3
4
5
6
7
8
chr(i)
- i -- 可以是 10 进制也可以是 16 进制的形式的数字
chr() 用一个范围在 range(256)内的(就是0~255)整数作参数,返回值是当前整数对应的 ASCII 字符
print(chr(48), chr(49), chr(97)) # 十进制
0 1 a
2
ord(c)
- c -- 字符
ord() 函数是 chr() 函数(对于8位的ASCII字符串)或 unichr() 函数(对于Unicode对象)的配对函数,它以一个字符(长度为1的字符串)作为参数,返回对应的 ASCII 数值,或者 Unicode 数值,如果所给的 Unicode 字符超出了你的 Python 定义范围,则会引发一个 TypeError 的异常
c = 'c'
# 字符前移一位
t = chr(ord(c) - 1)
print(t)
# output:
b
2
3
4
5
6
7
# 补充说明
# 最大 / 最小值
python2 最大整数值:sys.maxint,最小整数值:-sys.maxint-1
python3 最大整数值:sys.maxsize,最小整数值:-sys.maxsize-1
python3 最大浮点数值:float('inf'),最小浮点数值:-float('inf')
最大值也可以写成 inf,对应的最小值就是 -inf (推荐)
# 开方 / 乘方
import math
# 开方
a = math.sqrt(16)
# 乘方
# 方法一
res = math.pow(4, 3)
# 或 res = pow(4, 3)# 方法二
res = 4 ** 3
2
3
4
5
6
7
8
9
10
# 前缀和
import itertools
import operator
data = [1, 2, 3, 4, 5]
# 计算前缀和
print(list(itertools.accumulate(data, initial=0)))
# 计算到当前位置累积相乘得结果
data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
print(list(itertools.accumulate(data, operator.mul, initial=2)))
# 计算到当前位置的最大值并且输出
print(list(itertools.accumulate(data, max)))
# output:
[0, 1, 3, 6, 10, 15]
[2, 6, 24, 144, 288, 288, 2592, 0, 0, 0, 0]
[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 前缀最大值
分别记录前缀和后缀最大值
height = [1, 3, 6, 3, 6, 9, 3, 5, 3, 4]
n = 10
pre_max = [0] * n # pre_max[i] 表示从 height[0] 到 height[i] 的最大值
pre_max[0] = height[0]
for i in range(1, n):
pre_max[i] = max(pre_max[i - 1], height[i])
suf_max = [0] * n # suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值
suf_max[-1] = height[-1]
for i in range(n - 2, -1, -1):
suf_max[i] = max(suf_max[i + 1], height[i])
print(pre_max)
print(suf_max)
# output:
[1, 3, 6, 6, 6, 9, 9, 9, 9, 9]
[9, 9, 9, 9, 9, 9, 5, 5, 4, 4]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
这里介绍些关于后缀最大值的奇技淫巧,推荐看下
import itertools
data = [1, 2, 4, 2, 3]
# 后缀最大值
# 时间 O(n**2)
print([max(data[i:]) for i in range(len(data))])
# 时间 O(n)
print(list(reversed(list(itertools.accumulate(reversed(data), max)))))
print(list(itertools.accumulate(data[::-1], max))[::-1])
2
3
4
5
6
7
8
9
# 全局变量
我们可以使用 global
声明全局变量,作用域是全局的
可以在闭包中使用 nonlocal
声明变量,作用域在闭包里面
下面是没有使用 nonlocal
和 global
的例子
x = 0
def outer():
x = 1
def inner():
x = 2
print("inner:", x)
inner()
print("outer:", x)
outer()
print("global:", x)
# inner: 2
# outer: 1
# global: 0
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
使用 nonlocal
(常用)
x = 0
def outer():
x = 1
def inner():
nonlocal x
x = 2
print("inner:", x)
inner()
print("outer:", x)
outer()
print("global:", x)
# inner: 2
# outer: 2
# global: 0
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
使用 global
x = 0
def outer():
x = 1
def inner():
global x
x = 2
print("inner:", x)
inner()
print("outer:", x)
outer()
print("global:", x)
# inner: 2
# outer: 1
# global: 2
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
注意:本地的变量声明为
global
,就不能在再声明为nonlocal