python刷题常用知识点

记录python刷题常用的知识点,主要针对的是leetcode,编程题的一些小技巧,常用的函数,balabala…

输入输出方法

输入

最常见的输入方法是input(),默认输入的类型为字符串,可以直接进行类型转换。

  • 单一的输入,将输入的内容转化为自己需要的类型。
1
2
n = int(input())
m = float(input())

多值输入转化为需要的类型 包括一维数组的输入,两个值,三个值的输入

1
2
3
4
5
6
7
8
9
# input().split() 默认是空白字符(若干个空格)来分割字符串  返回的是字符串的列表
'''
string.split(separator, max)
separator: 可选。规定分割字符串时要使用的分隔符。默认值为空白字符。
max: 可选。规定要执行的拆分数。默认值为 -1,即“所有出现次数”。
'''
list1 = list(map(int, input().split()) #map处理结束后转化为列表类型
m1, m2 = map(int, input().split()) #使用map对字符串列表中的元素int操作 后直接赋值到两个变量中
a, b, c = map(float, input().split())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
str.strip([chars])
chars -- 移除字符串头尾指定的字符序列。
返回移除字符串头尾指定的字符生成的新字符串。
'''
import sys
n = int(sys.stdin.readline().strip()) #使用sys
#一维数组
data= [int(x) for x in stdin.readline().strip().split()]

# 二维数组
import sys
n = int(sys.stdin.readline().strip())
point = []
for i in range(n):
point.append(list(map(int, sys.stdin.readline().strip().split())))

输出

常见的输出是print(),默认每次打印之后换行符结尾,如果想要修改,可以对参数end来修改,还可以使用%填充字符串的输出方式,也可以使用str.format()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 单值打印
print('Hello')
# 多值打印
print('Hello','world',end="")
print()
# 格式化字符串
aName = 'ali'
age = 18
print('%s is %d years old.' % (aName, age))
t = 232.109223
# 使用{}和: 来代替 % 都可以用于保留有效数字
string1 = '{:.2f}'.format(t)
print(string1)
print('{0}, {1:.2f}'.format('Hehe', 20.278))
print('%s, %.2f' % ('Hehe', 20.278))

结果:
Hello
Hello world
ali is 18 years old.
232.11
Hehe, 20.28
Hehe, 20.28

常用函数

创建数组

1
2
3
4
5
# 创建一维列表
sqlist = [ x*x for x in range(1, 11)]
print(sqlist)
str2 = [ch.upper() for ch in 'Hello world!' if ch not in 'orld'] #循环和判断语句同时使用
print(str2)
1
2
3
4
5
6
7
8
9
创建二维数组 :
a = [[0 for col in range(m)] for row in range(n)]
或者[[0]*m for i in range(n)]
但是千万不要用[[0]*m]*n!!是错误的。对象被复制
# 创建一个二维列表5*5
list1 = [[0]*5 for i in range(5)]
print(list1)
# 创建一个3*3的二维数组
arr=[list(map(int,input().split())) for i in range(3)]

判断变量

isalpha() 判断字符串是否全是字母;检查一个字符串中所有的字符是否都是由字母构成的,并且至少有1个字符。

isalnum()函数判断的字符范围不仅包括字母,还包括0-9的数字。

isdigit() 判断字符串是否全是数字0-9

is_integer() 判断浮点数是否为整数

字符串操作

基本操作

join(): 用法 ‘分隔符’.join(字符串序列) 比如’ '.join([“hello”,“world”,“thank”,“you”]) 输出 “hello world thank you”

str.count(substr,start,end):计数子序列出现的次数

str.upper():字符串转成大写

str.lower():字符串转成小写

补充
  • ord(): 将ASCLL码转换为数字。ord(‘a’)返回91

  • chr(): 将数字转换为ASCLL码。chr(97) 返回字符串 ‘a’

  • str1.swapcase() : 翻转 str1 中的大小写

  • list(str1): 将字符串转化为列表

  • ‘’.join(str1): 将字符串列表,拼成字符串

  • srt1.split():将字符串按一定符号分割,分割后成列表

  • srt1.isdigit() : 检测字符串是否由十进制数 0–9组成

  • str1.isnumeric(): 检测字符串是否只由数字组成

  • srt1.isxdigit() : 检测字符串是否由十六进制数 0–9,a—f,或A–F组成

  • srt1.isalnum() : 检测字符串是否由字母数字符号 0–9,a–Z,或A–Z组成

  • srt1.isalpha() : 检测字符串是否由字母a–Z或A–Z组成

  • srt1.islower(): 检测字符串是否否由小写字母 a–Z组成

  • srt1.isupper(): 检测字符串是由 大写字母 A–Z组成

  • strip() / lstrip() / rstrip(): 用于移除字符串头尾 / 开头 / 结尾指定的字符(默认为空格)

反转

字符串反转 使用切片反转:str[::-1]

reverse()

reverse()是python中列表的一个内置方法(也就是说,在字典,字符串或者元组中,是没有这个内置方法的),用于列表中数据的反转;

1
2
3
4
lista = [1, 2, 3, 4]
lista.reverse() #原地操作 无返回值
print(lista)
[4,3,2,1]
reversed()

有返回值,是python的自带方法,经过reversed()的作用之后,返回的是一个把序列值经过反转之后的迭代器,所以,需要通过遍历,或者List,或者next()等方法,获取作用后的值;

列表操作

列表有自带的sort函数,直接对原列表进行更改。

  • list1.append(x) : 将x添加到列表末尾

  • list1.sort(): 对列表元素排序 默认升序 如果设置为降序:list1.sort(reverse=True)

  • list1.reverse() : 将列表元素逆序

  • list1.index(x) : 返回第一次出现元素x的索引值

  • list1.insert(x) : 在位置i处插入新元素x

  • list1.count(x) : 返回元素x在列表中的数量

  • list.remove(value):删除第一个匹配的值

  • list.pop(index):删除对应位置的元素

字典操作

判断是否含有该元素 :key in dict 即可

列表和字典相关技巧

字典排序

1
2
3
4
5
6
7
8
9
# python 根据 key,value 排序字典
d = {'d': 4, 'a': 1, 'b': 2, 'c':3}
# dict sort by key and reverse
#按照key
print(dict(sorted(d.items()))) # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
print(dict(sorted(d.items(),reverse=True))) # {'d': 4, 'c': 3, 'b': 2, 'a': 1}
#按照value
print(dict(sorted(d.items(),key=lambda d:d[1])))
print(dict(sorted(d.items(),key=lambda d:d[1],reverse=True)))
1
2
3
4
5
6
# 排序嵌套 list
l = [('a', 1), ('c', 2), ('b',3)]
print(sorted(l, key=lambda p:p[0])) # 根据第1个值排序,[('a', 1), ('b', 3), ('c', 2)]
print(sorted(l, key=lambda p:p[1])) # 根据第2个值排序,[('a', 1), ('c', 2), ('b', 3)]
[('a', 1), ('b', 3), ('c', 2)]
[('a', 1), ('c', 2), ('b', 3)]

获取最大值和下标

1
2
3
4
# 同时获取最大值的下标和值
lis = [1,2,5,4,3]
max_index,max_value = max(enumerate(lis),key=lambda iv:iv[1])
print('最大值的下标:',max_index,'、','最大值为:',max_value)
1
2
3
4
# 获取字典对应的最大值对应的 key,value
mydict = {'A':4,'B':10,'C':0,'D':87}
max_key, max_value = max(mydict.items(), key=lambda k: k[1])
print('最大值的key:',max_key,'、','最大值为:',max_value)

内置函数

zip(): 创建一个聚合了来自每个可迭代对象中的元素的迭代器。

1
2
3
4
5
x = [1, 2, 3]
y = [4, 5, 6]
zipped = zip(x, y)
print(list(zipped))
[(1, 4), (2, 5), (3, 6)]

zip() 与 * 运算符相结合可以用来拆解*

1
x2, y2 = zip(*zipped)

排序

对于字典,字符串等数据结构,必须用sorted函数。
sorted(iterable[, cmp[, key[, reverse]]])

  • cmp和key都是函数
  • key的输出是cmp的输入
  • cmp函数默认是升序

比如

1
2
3
4
5
6
7
dic = {‘a’:2,’b’:1} 
# 按照key排序
dict1 = sorted(dic.items(),key=lambda d:d[0])
返回[(‘a’,2),(‘b’,1)]
# 按照value排序
dict2 = sorted(dic.items(),key= lambda d:d[1])
返回元组列表[(‘b’,1),(‘a’,2)]

dic.items() 函数以列表返回可遍历的(键, 值) 元组数组。把字典中每对 key 和 value 组成一个元组,并把这些元组放在列表中返回。

数据结构

list

普通的栈和队列,使用list即可实现

  • append(value) 加入元素
  • pop() 出栈
  • pop(0) 出队列

deque

collections模块的deque(双端队列)

deque是栈和队列的一种广义实现,deque是"double-end queue"的简称;deque支持线程安全、有效内存地以近似O(1)的性能在deque的两端插入和删除元素,尽管list也支持相似的操作,但是它主要在固定长度操作上的优化,从而在pop(0)和insert(0,v)(会改变数据的位置和大小)上有O(n)的时间复杂度。

deque 是一个双端队列, 如果要经常从两端append 的数据, 选择这个数据结构就比较好了, 如果要实现随机访问,不建议用这个,请用列表. deque 优势就是可以从两边append ,appendleft 数据. 这一点list 是没有的.

1
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
import collections
d = collections.deque([])
d.append('a') # 在最右边添加一个元素,此时 d=deque('a')
d.appendleft('b') # 在最左边添加一个元素,此时 d=deque(['b', 'a'])
d.extend(['c','d']) # 在最右边添加所有元素,此时 d=deque(['b', 'a', 'c', 'd'])
d.extendleft(['e','f']) # 在最左边添加所有元素,此时 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
d.pop() # 将最右边的元素取出,返回 'd',此时 d=deque(['f', 'e', 'b', 'a', 'c'])
d.popleft() # 将最左边的元素取出,返回 'f',此时 d=deque(['e', 'b', 'a', 'c'])
d.rotate(-2) # 向左旋转两个位置(正数则向右旋转),此时 d=deque(['a', 'c', 'e', 'b'])
d.count('a') # 队列中'a'的个数,返回 1
d.remove('c') # 从队列中将'c'删除,此时 d=deque(['a', 'e', 'b'])
d.reverse() # 将队列倒序,此时 d=deque(['b', 'e', 'a'])
f=d.copy()
print(f)#deque(['b', 'e', 'a'])
f.clear()
print(f)#deque([])

#可以指定队列的长度,如果添加的元素超过指定长度,则原元素会被挤出。
e=collections.deque(maxlen=5)
e.extend([1,2,3,4,5])
e.append("a")
print(e)
#deque([2, 3, 4, 5, 'a'], maxlen=5)
e.appendleft("b")
print(e)
#deque(['b', 2, 3, 4, 5], maxlen=5)
e.extendleft(["c","d"])
print(e)
#deque(['d', 'c', 'b', 2, 3], maxlen=5)

例题:

P为给定的二维平面整数点集。定义 P 中某点x,如果x满足 P 中任意点都不在 x 的右上方区域内(横纵坐标都大于x),则称其为“最大的”。求出所有“最大的”点的集合。(所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内)

如下图:实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:

第一行输入点集的个数 N, 接下来 N 行,每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据, 1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合, 按照 X 轴从小到大的方式输出,每行两个数字分别代表点的 X 轴和 Y轴。

示例1
1
2
3
4
5
6
7
8
9
10
11
12
输入:
5
1 2
5 3
4 6
7 5
9 0

输出:
4 6
7 5
9 0

方法一:

1
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
from sys import stdin
n =int(stdin.readline().strip())
data= [int(x) for x in stdin.readline().strip().split()] #可以对每一行进行操作,会统一放进同一个列表中;注意int操作对字符串数据变换
#使用stdin.readline().strip().split() strip去掉首尾空字符串 split进行切割数据
partsum=[0]
for x in data:
partsum.append( partsum[-1]+x )

def left_bound(data):
left=[ 0 for i in range(n) ]
for i,v in enumerate( data[1:],1):
if v > data[i-1]:
left[i]=i
else:
k = i-1
while k >= 0:
if v < data[k]:
k = left[k]-1
else :
left[i] = left[k] if v == data[k] else k+1
break
return left

left = left_bound(data)
right= left_bound(data[::-1])[::-1]
right= [n-x for x in right ]

res = max([ data[i]*(partsum[right[i]]-partsum[left[i]]) for i in range(n) ])
print(res)

思路是:把每个数当做区间里的最小值,找区间左右边界,即第一个小于它的数(区间里加入小于它的数,它就不是最小值了)
优化的点有两个:
1.求和涉及大量的重复运算——可以用从0到n的部分和减法代替
2.找边界的过程涉及大量的重复比较——
以找左边界为例, 从第二个数起,
如果大于前一个数,则左边界为自身;否则:
如果等于前一个数,则左边界跟前一个数的左边界一样;
如果小于,则它的左边界小于前一个数的左边界;
这样可以跳过重复的比较。
把找左边界写成函数,求右边界把数组逆置调用下再转换就行了,不用重写

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
p = []
n = int(input())
for i in range(n):
tmp = input()
a = [int(x) for x in tmp.split(' ')]
p.append(a)
sorted(p, key=lambda x: (-x[0], -x[1]))
tmp = -1
for t in p:
if t[1] > tmp:
print('%d %d' % (t[0], t[1]))
tmp = t[1]