必备import
# 默认值dict
# 双端队列
from colections import deque, defaultdict
# 优先队列
from queue import PriorityQueue
# 函数参数类型
from typing import List, Set, Dict, Tuple
# 堆
from heapq import heappush, heapify, heappop
# 全排列
from itertools import permutations,combinations
import bisect
import functools
# functools.lru_cache(None)
# functools.reduce
import math
from typing import *
import sys
sys.setrecursionlimit(8000)
from sortedcontainers import SortedList
python标准数据类型
print()
printf(s,end=" ")
Number（数字）
Python3 支持 int、float、bool、complex（复数）。
String（字符串）
单引号双引号都一样，重复1、2、3个，1、2的话，\作为续行符，也是转义字符，三引号的就不用续行符了。
不想转义，字符串前加r/R
左起0开始，右起-1开始，
print (str[0:-1]) # 输出第一个到倒数第二个的所有字符
print (str[0]) # 输出字符串第一个字符
print (str[2:5]) # 输出从第三个开始到第五个的字符
print (str[2:]) # 输出从第三个开始的后的所有字符
print (str * 2) # 输出字符串两次
print (str + "TEST") # 连接字符串
print( r'\n' ) # 原始字符串
len(str)获取长度，str.strip()去除所有首尾的空格，也可以多参数，比如str.strip(“T “)，去除T或空格; str.title()让所有单词的首字母大写; str.upper()，str.lower();
unicode前加u
count(str, beg= 0,end=len(string))
encode(encoding='UTF-8',errors='strict')
endswith(suffix, beg=0, end=len(string))
find(str, beg=0 end=len(string))
isalnum(),isalpha(),isdigit(),islower(),isupper()
len(list)返回长度
lower(),upper()
max(),min()
split(str="", num=string.count(str))
print(source_string.find("day"));//none return -1
str=source_string.replace("day","time");
print(str);
print(str.split(" "));
# str判断类型的方法:
s = ""
s.isalnum()
s.isalpha()
s.isdigit()
s.islower()
字符串变量拼接 f开头， {}引用变量
f'My name is {name}, my age next year is {age+1}, my anniversary is {anniversary:%A, %B %d, %Y}.'
'My name is Fred, my age next year is 51, my anniversary is Saturday, October 12, 1991.'
List（列表）
0开头，-1结尾, 也可以list[start
span]
声明：list = [ ‘abcd’, 786 , 2.23, ‘runoob’, 70.2 ]
print(list[0:])输出[…..]
可以用+拼接,可以嵌套列表
del list[0]
list[1]=3
len(list)
max(list),min(list)
list(tuple)
list.append(), list.count(), list.extend(sequence)
list.index(obj), list.insert(index,obj), list.pop()
list.remove(obj), list.reverse(), list.sort(func)
list.clear, list.copy()
Tuple（元组）
不能修改，但可以包含可变的对象，如List
声明： tuple = ( ‘abcd’, 786 , 2.23, ‘runoob’, 70.2 )
如果一个元素的话，tup2 = (20,) # 一个元素，需要在元素后添加逗号
print输出(…)
del tuple
tuple(seq)
Sets（集合）
可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。
student = {‘Tom’, ‘Jim’, ‘Mary’, ‘Tom’, ‘Jack’, ‘Rose’}或者b = set(‘alacazam’)//这是字符做一个元素
print输出{…}
Dictionary（字典）
是无序的
声明
dict = {}
dict['one'] = "1 - 菜鸟教程"
dict[2] = "2 - 菜鸟工具"
或者
tinydict = {'name': 'runoob','code':1, 'site': 'www.runoob.com'}
dict.clear() # 清空字典
key in dict 如果键在字典dict里返回true，否则返回false
list.items() 以列表返回可遍历的(键, 值) 元组数组
dict.keys(),dict.values() 以列表返回
for k, v in knights.items():
print(k, v)
{}有个方法setdefault(a,b)方法，当a不在{}里时x[a]=a
# 对{} append
{}.setdefault(a,[]).append(x) # value为list。
defaultdict
importcollections
w=collections.defaultdict(tuple)
这样可以避免{}的key不存在然后报错
w=collections.defaultdict(lambda:-1) # 需要传个函数进去
# 对{}+=1
from _collections import defaultdict
c = defaultdict(lambda :0)
c['k'] += 2
print(c.items())
defaultdict还可以作为id生成器。
# 参考: https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode/
trees = collections.defaultdict()
trees.default_factory = trees.__len__
SortedSet, SortedDict
首先，leetcode支持sortedcontainers的
为什么需要呢，因为这个按o(logn)的性能有序查找和删除很有用。。。
from sortedcontainers import SortedSet, SortedDict
a = SortedDict()
a[1] = 2
a[2] = 3
print(a)
print(a[2])
del a[1]
print(a)
a = SortedSet()
a.add(3)
a.add(5)
print(a)
数据类型转换
int(), float(), complex(real,imag),str(),tupel(),list(),set(),
dict(d) d必须是序列元祖，如[(a,b),[c,d]]
chr(), ord() char转化为它的整数
hex(), oct()
list转string:
str1=''.join(str)
ascii表：
A：65
a:97
0:48
python的变量比较
is和==
is比较的是引用
==比较的是内容
if对变量的判断
if语句不仅判断None，也判断是否为0，是否len==0
if x is not None是最好的写法，不会出现错误
使用if not x这种写法的前提是：必须清楚x等于None, False, 空字符串”“, 0, 空列表[], 空字典{}, 空元组()时对你的判断没有影响才行。
isinstance和type
type可以只接收一个参数，打印其未知的所属的类型；而isinstance只能判断是否属于某个已知类型。
isinstance可以判断子类对象是否继承于父类；而type不可以。
用type和isinstance分别判断{‘s’}是否属于set类型
def a():return type({'s'})is set
def b():return isinstance({'s'},set)
def c():return type({'s'})==set
语法
注释
单行：# 多行：3个单引号或者双引号
运算符
- **：乘幂
- //：四舍五入的除法
- 逻辑操作符： and or not
- 成员运算符: in， not in
- is 引用同一对象?
- is not 引用不同对象？
- == 判断是否相等
- isinstance, 其中isinstance会认为子类和父类相等
- // 取整除 - 向下取接近商的整数 注意/不是返回整数
- 阶乘: a**b
位运算
^异或
~取反
&与
| 或
if
if condition_1:
statement_block_1
elif condition_2:
statement_block_2
else:
statement_block_3
循环
while 判断条件：
语句
or
while count < 5:
print (count, " 小于 5")
count = count + 1
else:
print (count, " 大于或等于 5")
for site in sites:
for i in range(len(a)): 0到len(a)-1
print(i, a[i])
迭代器
iter(seq)和next(iter)函数
next(iter)用户获取迭代器iter的下一个值
it = iter(list) # 创建迭代器对象
for x in it:
print (x, end=" ")
for x in [1, 2, 3, 4, 5]:
pass
实际上完全等价于：
# 首先获得Iterator对象:
it = iter([1, 2, 3, 4, 5])
# 循环:
while True:
try:
# 获得下一个值:
x = next(it)
except StopIteration:
# 遇到StopIteration就退出循环
break
yield生成器
返回一个动态list
def fibonacci(n): # 生成器函数 - 斐波那契
a, b, counter = 0, 1, 0
while True:
if (counter > n):
return
yield a
a, b = b, a + b
counter += 1
f = fibonacci(10) # f 是一个迭代器，由生成器返回生成
while True:
try:
print (next(f), end=" ")
except StopIteration:
sys.exit()
函数
计算面积函数
def area(width, height):
return width * height
不可变类型值传递，可变类型引用传递
- 数字及string，tuple都是不可变对象
- list,dict,set都是可变对象
- 要改为值传递，需要copy.deepcopy(obj)
- 我也不知道怎么改为引用传递啊，好像不支持&的
可以参数名匹配
#调用printme函数
printme( str = "菜鸟教程");
默认参数
def printinfo( name, age = 35 ):
return;
不定长参数，加*
def printinfo( arg1, *vartuple ):
return;
__name__属性
一个模块被另一个程序第一次引入时，其主程序将运行。如果我们想在模块被引入时，模块中的某一程序块不执行，我们可以用__name__属性来使该程序块仅在该模块自身运行时执行。
#!/usr/bin/python3
# Filename: using_name.py
if __name__ == '__main__':
print('程序自身在运行')
else:
print('我来自另一模块')
输入输出
str = input("请输入：");
print (x, end=" ")
a= map(int, inpurt().split()) # 按空格分隔后再转成int的一个list
输入输出重定向
console = sys.stdin
file = open(r".\file\data.txt", 'r')
sys.stdin = file
文件读写
由于文件读写时都有可能产生IOError，一旦出错，后面的f.close()就不会调用。所以，为了保证无论是否出错都能正确地关闭文件，我们可以使用try … finally来实现：
try:
f = open('/path/to/file', 'r')
print f.read()
finally:
if f:
f.close()
但是每次都这么写实在太繁琐，所以，Python引入了with语句来自动帮我们调用close()方法：
with open('/path/to/file', 'r') as f:
print f.read()
这和前面的try … finally是一样的，但是代码更佳简洁，并且不必调用f.close()方法。
调用read()会一次性读取文件的全部内容，如果文件有10G，内存就爆了，所以，要保险起见，可以反复调用read(size)方法，每次最多读取size个字节的内容。另外，调用readline()可以每次读取一行内容，调用readlines()一次读取所有内容并按行返回list。因此，要根据需要决定怎么调用。
如果文件很小，read()一次性读取最方便；如果不能确定文件大小，反复调用read(size)比较保险；如果是配置文件，调用readlines()最方便：
for line in f.readlines():
print(line.strip()) # 把末尾的'\n'删掉
f = open("/tmp/foo.txt", "r")
f.read()所有内容
f.readLine()一行
f.write(str)
如果要改变文件当前的位置, 可以使用 f.seek(offset, from_what) 函数
f.close()
python无限输入
while True:
try:
x = raw_input()
if not x:
break
except:
break;
print x, type(x)
字符编码
要读取非ASCII编码的文本文件，就必须以二进制模式打开，再解码。比如GBK编码的文件：
f = open('/Users/michael/gbk.txt', 'rb')
u = f.read().decode('gbk')
如果每次都这么手动转换编码嫌麻烦（写程序怕麻烦是好事，不怕麻烦就会写出又长又难懂又没法维护的代码），Python还提供了一个codecs模块帮我们在读文件时自动转换编码，直接读出unicode：
import codecs
with codecs.open('/Users/michael/gbk.txt', 'r', 'gbk') as f:
f.read() # u'\u6d4b\u8bd5'
//和/
要是保留整数部分，只能用int(a/b) 不能用a//b，涉及到a是负数就有问题了。
因为a//b是向下取整，这块在求%的时候也有问题，因为求模是r=a-n*[a//n]
global和nonlocal
https://www.programiz.com/python-programming/global-local-nonlocal-variables
全局变量update需要global
嵌套函数更新函数外的函数内变量需要nonlocal
高级函数api
列表生成器
[[row[i] for row in matrix] for i in range(4)]
注意[]*5这种只能最里层使用，而且是初始化使用带常量，因为复制的引用。
counter
import collections
counter = collections.Counter()
a = {"a", "a", "b"}
counter = collections.Counter(a)
counter.most_common(3)
counter.values()
sorted(counter.elements())
counter.keys()
sorted
除了sorted(seq)方法还有list.sort()…等
升序和降序
list.sort()和sorted()都接受一个参数reverse（True or False）来表示升序或降序排序。
sorted(student_tuples, key=itemgetter(2), reverse=True)
默认sorted([True, False])==[False, True] (False=0 < True=1)
一个字符串排序，排序规则：小写<大写<奇数<偶数
#元组内(e1, e2, e3)的优先级排列为: e1 > e2 > e3
sorted(s, key=lambda x: (x.isdigit(),x.isdigit() and int(x) % 2 == 0,x.isupper(),x)
#input: 'asdf234GDSdsf23'
#output: 'addffssDGS33224'
- x.isdigit()的作用是把数字放在后边（True）,字母放在前面（False）.
- x.isdigit() and int(x) % 2 == 0的作用是保证数字中奇数在前（False），偶数在后（True）。
- x.isupper()的作用是在前面基础上,保证字母小写（False）在前大写在后（True）. 最后的x表示在前面基础上,对所有类别数字或字母排序。
cmp_to_key
- 使用 key 比使用 cmp 的性能更快，对于有 N 个元素的列表，在排序过程中如果调用 cmp 进行比较，那么 cmp 的调用次数为 Nlog(N) 量级（基于比较的排序的最快时间复杂度），如果使用 key 参数，那么只需要在每个元素上调用一次 key 函数，只有 N 次调用，虽然使用 key 参数也要进行 O(Nlog(N)) 量级比较次数，但这些比较是在 C 语言层，比调用用户自定义的函数快。
import functools
num_list = [4, 2, 8, -9, 1, -3]
# x是否在y后面，如果正数表示x在y后面
def custom_cmp(x, y):
# 返回正数表示x应该排在y后面
return abs(x) - abs(y)
sorted_num_list = sorted(num_list, key=functools.cmp_to_key(custom_cmp))
print(sorted_num_list)
lambda
Lambda函数，是一个匿名函数，创建语法：
lambda parameters:express
parameters：可选，如果提供，通常是逗号分隔的变量表达式形式，即位置参数。
expression：不能包含分支或循环（但允许条件表达式），也不能包含return（或yield）函数。如果为元组，则应用圆括号将其包含起来。
使用sorted()方法和list.sort()方法进行排序
elements=[(2,12,"A"),(1,11,"N"),(1,3,"L"),(2,4,"B")]
>>> sorted(elements)
[(1, 3, 'L'), (1, 11, 'N'), (2, 4, 'B'), (2, 12, 'A')]
根据elements每个元组后两项进行排序，e表示列表中每个三元组元素
在表达式是元组，且lambda为一个函数的参数时，lambda表达式的圆括号是必需的
>>> elements.sort(key=lambda e:(e[1],e[2]))
>>> elements
[(1, 3, 'L'), (2, 4, 'B'), (1, 11, 'N'), (2, 12, 'A')]
分片方式得到同样的效果
>>> elements.sort(key=lambda e:e[1:3])
>>> elements
[(1, 3, 'L'), (2, 4, 'B'), (1, 11, 'N'), (2, 12, 'A')]
>>> elements.sort(key=lambda e:(e[2].lower(),e[1]))
以下两种方法等价，都可以通过调用area(5,3)，结果相同
>>> area=lambda b,h:0.5*b*h
>>> def area(b,h):
return 0.5*b*h
默认字典使用，存取不不在的键时，创建一个新项，键为这个不存在的键，值为lambda函数的值
>>> import collections
>>> one_dict = collections.defaultdict(lambda:-1)
>>> two_dict = collections.defaultdict(lambda:(0,0))
>>> three_dict = collections.defaultdict(lambda:"No message avaliable")
map()函数——作用于list每一个元素
map()是 Python 内置的高阶函数，它接收一个函数 f() 和一个 list，并通过把函数 f 依次作用在 list 的每个元素上，得到一个新的 list 并返回。(这个函数与 R 中的 lapply 非常相似)
用法map(function, sequence)
l = ['1','2','3','4']
list(map(int,l))
Out[2]: [1, 2, 3, 4]
filter()函数——筛选函数
按照 function 函数的规则在列表 sequence 中筛选数据
用法：filter(function, sequence)
筛选 list 中符合条件的值
l =[1,2,3,4]
filter(lambda x: x>2, l)
Out[6]: [3, 4]
reduce()——求积累运算
reduce函数功能是将 sequence 中数据，按照 function 函数操作，如将列表第一个数与第二个数进行 function 操作，得到的结果和列表中下一个数据进行 function 操作，一直循环下去…
用法reduce(function, sequence):
求积累和
l =[1, 2, 3, 4]
reduce(lambda x,y: x+y, l)
Out[10]: 10
zip()打包函数
zip()是 Python 的一个内建函数，它接受一系列可迭代的对象作为参数，将对象中对应的元素打包成一个个tuple（元组），然后返回由这些tuples组成的list（列表）。若传入参数的长度不等，则返回 list 的长度和参数中长度最短的对象相同。利用*号操作符，可以将list unzip（解压）。
用法: zip(list,list)
zip()基本用法
l1 = [1, 2, 3, 4]
l2 = ['a', 'b', 'c', 'd']
zip(l1,l2)
Out[12]: [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
旋转矩阵zip挺好用的
顺时针：matrix[:] = list(zip(*matrix[::-1]))
逆时针：matrix[:] = list(zip(*matrix))[::-1]
转置：matrix[:] = list(zip(*matrix))
max, min, sum, any, all
max([1,2,3])
sum(L) 返回序列的元素的和（只有数字型才可以）
any(L) 返回布尔值，序列中有一个为真就返回True，都为假的时候才返回False
all(L) 返回布尔值，序列中全部为真时返回True，只要有一个假就返回False
dict排序遍历
d = {}
after = dict(sorted(before.items(), key=lambda e: e[1]))
d.iterms() = [('key1', 5), ('key2', 6), ('key3', 4), ('key4', 3), ('key5', 7), ('ky0', 9)]
list倒序
原始元素的倒序排列
arr = [1,2,3,4,3,4]
(1)print arr[::-1] ---->[4, 3, 4, 3, 2, 1]
(2)arr.reverse()
print arr ---->[4, 3, 4, 3, 2, 1]
(3)reversed(arr) #返回一个倒序可遍历对象，需序遍历出
arr = [1,2,3,4,3,4]
reversed_arr = []
for i in reversed(arr):
reversed_arr.append(i)
print reversed_arr ---->[4, 3, 4, 3, 2, 1]
最大值
float('inf'), float('-inf')
最大值+x不会溢出。还是最大值
栈和队列
栈：list.append list.pop
队列
>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry") # Terry arrives
>>> queue.append("Graham") # Graham arrives
>>> queue.popleft() # The first to arrive now leaves
'Eric'
>>> queue.popleft() # The second to arrive now leaves
'John'
>>> queue # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])
堆和优先队列
优先队列
小顶堆，小的在上面
from Queue import PriorityQueue
pq = PriorityQueue()
for i in range(3,0,-1):
pq.put(i)
while not pq.empty():
print pq.get()
123
存放元组：
如果存放元组，则默认比较元组的第一个元素，小的在队列头部，如果，第一元素相同比较第二个元素，如果还相同依次往后比较。其实这应该是是内置的元组大小比较函数定义的比较方式。
from queue import PriorityQueue
pq = PriorityQueue()
pq.put((1, 2))
pq.put((1, 0))
pq.put((2, 3))
while not pq.empty():
print (pq.get())
存放自定义类型：
自定义数据类型，需要自定义__cmp__或者__lt__比价函数。
from queue import PriorityQueue
class Job(object):
def __init__(self, priority, description):
self.priority = priority
self.description = description
print('New job:', description)
return
def __lt__(self, other):
return self.priority < other.priority
''' 或者使用__cmp__函数
def __cmp__(self, other):
if self.priority < other.priority:
return -1
elif self.priority == other.priority:
return 0
else:
return 1
'''
q2 = PriorityQueue()
q2.put(Job(5, 'Mid-level job'))
q2.put(Job(10, 'Low-level job'))
q2.put(Job(1, 'Important job')) #数字越小，优先级越高
while not q2.empty():
next_job = q2.get() #可根据优先级取序列
print('Processing job', next_job.description)
('New job:', 'Mid-level job')
('New job:', 'Low-level job')
('New job:', 'Important job')
('Processing job', 'Important job')
('Processing job', 'Mid-level job')
('Processing job', 'Low-level job')
堆
默认小顶堆
2.1 小顶堆
python提供了heapq模块，提供了堆的支持，是基于python的list实现的。heapq提供的默认是一个小顶堆的实现，即最小的元素排在前面。
堆（Heap）是一种特殊形式的完全二叉树，其中父节点的值总是大于子节点，根据其性质，Python 中可以用一个满足 heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] 的列表来实现（heapq 也确实是这么做的） 下面介绍headp模块的使用：
heapq模块中有6个函数：
1、heappush(heap, x)：向堆中添加元素
from heapq import *
heap = []
for i in range(3):
heappush(heap, i)
print(heap) #[0, 1, 2]
heappush(heap, 0.5)
print(heap) #[0, 0.5, 2, 1]
heappush(heap, 1.5)
print(heap) #[0, 0.5, 2, 1, 1.5]
2、heappop(heap)：弹出堆中最小的元素，并且维持剩余元素的堆结构
from heapq import *
heap = []
for i in range(3):
heappush(heap, i)
print(heap) #[0, 1, 2]
heappop(heap) #heappop函数会返回弹出的值
print(heap) #[1, 2]
3、heapify(heap)：将列表转换为堆
from heapq import *
heap = [5, 8, 0, 4, 6, 7]
heapify(heap)
print(heap) #[0, 4, 5, 8, 6, 7]
4、heapreplace(heap, x)：弹出堆中最小的元素，然后将新元素插入。
from heapq import *
heap = [5, 8, 0, 4, 6, 7]
heapify(heap)
print(heapreplace(heap, 5.5)) #0
print(heap) #[4, 5.5, 5, 8, 6, 7]
- nlargest(n, iter)、nsmallest(n, iter)：用来寻找任何可迭代对象iter中的前n个最大的或前n个最小的元素。
from heapq import *
lst = [5, 8, 0, 4, 6, 7]
print(nsmallest(3, lst))
print(nlargest(3, lst))
2.2 大顶堆
python没有提供大顶堆的实现，想要使用大顶堆需要一些trick。 heappush(e)改为heappush(-e)，heappop(e)为-heappop(e)，也就是说存入和取出的数都是相反数，其他逻辑和TopK相同。 直接用tuple更Ok
总结
import Queue as Q
q = Q.deque()
q.append(3)
print len(q)
print q[0]
print q.popleft()
#priority queue
class Job(object):
def __init__(self, priority, description):
self.priority = priority
self.description = description
print 'New job:', description
return
def __cmp__(self, other):
return cmp(self.priority, other.priority)
q = Q.PriorityQueue()
q.put(Job(3, 'Mid-level job'))
q.put(Job(10, 'Low-level job'))
q.put(Job(1, 'Important job'))
print q.qsize()
全排列
import itertools
itertools.permutations()
文件重定向
if __name__ == '__main__':
with open('/Users/mafulong/a', 'r') as f:
# for l in f:
# print(l, end='')
import sys
sys.stdin = f
while True:
try:
s = input()
print(s, end='\n')
sl = s.split(' ')
print(sl)
print(float(sl[3]))
print(str(sl[2].strip("\"")))
except Exception:
break
format用法
^, <, > 分别是居中、左对齐、右对齐，后面带宽度， : 号后面带填充的字符，只能是一个字符，不指定则默认是用空格填充。
+ 表示在正数前显示 +，负数前显示 -； （空格）表示在正数前加空格
b、d、o、x 分别是二进制、十进制、八进制、十六进制。
"{} {}".format("hello", "world")
"{1} {0} {1}".format("hello", "world") # 设置指定位置
my_list = ['菜鸟教程', 'www.runoob.com']
print("网站名：{0[0]}, 地址 {0[1]}".format(my_list)) # "0" 是必须的
'{:b}'.format(11)
'{:d}'.format(11)
'{:o}'.format(11)
'{:x}'.format(11)
'{:#x}'.format(11)
'{:#X}'.format(11)
1011
11
13
b
0xb
0XB
| 3.1415926 | {:.2f} | 3.14 | 保留小数点后两位 |
|---|---|---|---|
| 3.1415926 | {:+.2f} | +3.14 | 带符号保留小数点后两位 |
| -1 | {:+.2f} | -1.00 | 带符号保留小数点后两位 |
| 2.71828 | {:.0f} | 3 | 不带小数 |
| 5 | {:0>2d} | 05 | 数字补零 (填充左边, 宽度为2) |
| 5 | {:x<4d} | 5xxx | 数字补x (填充右边, 宽度为4) |
| 10 | {:x<4d} | 10xx | 数字补x (填充右边, 宽度为4) |
| 1000000 | {:,} | 1,000,000 | 以逗号分隔的数字格式 |
range
Range(10**9) 也没关系，因为range的时间复杂度是1，可以o(1)时间复杂度计算出对应的值。如果是list(range(xx))这复杂度就是O(xx)了。 len(range)的时间复杂度也是o(1)
二分bisect
import bisect
bisect.bisect_left
bisect.bisect_right
# range时间复杂度不用list转化的时间复杂度是o(1) 包括取任意位置的值和len
# 如果想找个某个位置为True,可以传key函数并且找True的值。
有负数的除法求模 不同语言可能不同
比如a 除以 b，求对应商和余数。不同语言可能不同
计算-7 Mod 4
那么：a = -7；b = 4；
第一步：求整数商c，c应该是-1.75，如进行求模运算c = -2（向负无穷方向舍入），求余运算则c = -1（向0方向舍入）；
第二步：计算模和余数的公式相同，但因c的值不同，求模时r = 1，求余时r = -3。
当符号不一致时，结果不一样。求模运算结果的符号和b一致，求余运算结果的符号和a一致。
在C/C++, C#, JAVA, PHP这几门主流语言中，%运算符都是做取余运算，而在python中的%是做取模运算。
python求商是向负无穷靠近，而其他是靠近0.
python负数补码
python负数不是存的补码，是-的原码，因此要求补码的话需要和0xffffffff与一下
求负数的补码
a&0xffffffff
判断是否是正数
a <= 0x7fffffff 这是正数的补码
python负数到标准补码:
a&0xffffffff 相当于只保留32位以内的数字
负数标准补码到python负数
~(a^0xffffffff) 相当于32位以外的数字取反
正数负数加判断的标准补码到int
(~(a ^ x) if a > 0x7fffffff else a)
x = 0xffffffff
print(bin(1)) # 0b1
print(bin(-1)) # -0b1
# 转成32位 标准对应补码
a = (-1) & x
print(a, bin(a)) # 2**32-1,0b11111111111111111111111111111111
# 32位标准补码恢复
b = ~(2 ^ x)
# 测试正数, 发现正数不行，也就是说只有负数可以这么搞来搞去。
print(b, bin(b)) # -4294967294 -0b11111111111111111111111111111110
c = ~(a ^ x)
print(c, bin(c)) # -1 -0b1
def intToBin32(i):
return (bin(((1 << 32) - 1) & i)[2:]).zfill(32)
def bin32ToInt(s):
return int(s[1:], 2) - int(s[0]) * (1 << 31)
a = intToBin32(2**32-1)
print(bin32ToInt(a))
杂
import bisect
import functools
import math
from typing import *
import sys
sys.setrecursionlimit(8000)
from sortedcontainers import SortedList
'''
alias pip='python3 -m pip'
pip install sortedcontainers
'''
MOD = int(1e9 + 7)
INF = int(1e20)
class Math1:
pass
def comment():
import math
# b % a == 0
# 表示b能被a整除，a可以整除b, 被除数永远都是有这个『被』
# 组合
math.comb # n! / (k! * (n - k)!)
math.perm # n! / (n - k)!
math.gcd # greatest common divisor
pow # x**y (x to the power of y). use pow rather math.pow
# char
chr # unicode to char
ord # char to unicode
# number
hex # 16进制
bin # 2进制
# sortedcontainers
import sortedcontainers
ss = sortedcontainers.SortedList()
ss.add
ss.remove
del ss[0]
import collections
q = collections.deque()
q.append
q.appendleft
q.pop
q.popleft
# defaultdict
d = collections.defaultdict(list)
# or
d = collections.defaultdict(lambda: list())
# heapq
import heapq
h = []
heapq.heappush(h, 3)
t1 = heapq.heappop(h)
# combinations
import itertools
a = [1, 2, 3]
# combinations(range(4), 3) --> (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)
itertools.combinations(a)
# permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)
itertools.permutations(a)
# bisect
import bisect
def can(mid):
return mid > 64
# 只能用True， 不能Search False
bisect.bisect_left(range(100), True, lo=1, hi=90, key=can)
# lru cache, 使用cache_clear可以降低memory使用，否则leetcode会卡这个
import functools
@functools.lru_cache(None)
def haha(x):
return x
haha.cache_clear()
# 使用 sum 函数求和
import functools
sequence = [1,3,4]
sum_result = sum(sequence)
print("sum 函数求和结果:", sum_result)
# function
# 使用 reduce 函数求和
reduce_result = functools.reduce(lambda x, y: x + y, sequence)
print("reduce 函数求和结果:", reduce_result)
# 使用 itertools.accumulate 函数求和
accumulate_result = list(itertools.accumulate(sequence))
print("itertools.accumulate 函数求和结果:", accumulate_result[-1])
面向对象
类
#!/usr/bin/python
# -*- coding: UTF-8 -*-
class Employee:
'所有员工的基类'
empCount = 0
def __init__(self, name, salary):
self.name = name
self.salary = salary
Employee.empCount += 1
def displayCount(self):
print "Total Employee %d" % Employee.empCount
def displayEmployee(self):
print "Name : ", self.name, ", Salary: ", self.salary
print "Employee.__doc__:", Employee.__doc__
print "Employee.__name__:", Employee.__name__
print "Employee.__module__:", Employee.__module__
print "Employee.__bases__:", Employee.__bases__
print "Employee.__dict__:", Employee.__dict__
类变量
class Person:
species = "Human" # 类字段，所有实例共享
def __init__(self, name):
self.name = name # 对象变量
继承语法
class 派生类名(基类名)
...
#!/usr/bin/python
# -*- coding: UTF-8 -*-
class Parent: # 定义父类
parentAttr = 100
def __init__(self):
print "调用父类构造函数"
def parentMethod(self):
print '调用父类方法'
def setAttr(self, attr):
Parent.parentAttr = attr
def getAttr(self):
print "父类属性 :", Parent.parentAttr
class Child(Parent): # 定义子类
def __init__(self):
print "调用子类构造方法"
def childMethod(self):
print '调用子类方法'
c = Child() # 实例化子类
c.childMethod() # 调用子类的方法
c.parentMethod() # 调用父类方法
c.setAttr(200) # 再次调用父类的方法 - 设置属性值
c.getAttr() # 再次调用父类的方法 - 获取属性值
python的__new__和__init__的区别
概括：简言之，_new_作用于_init_之前。前者可以决定是否调用后者，或者说可以决定调用哪个类的_init_方法。
解释一：首先要知道在面向对象编程中，实例化基本遵循创建实例对象、初始化实例对象、最后返回实例对象这么一个过程。Python 中的 new 方法负责创建一个实例对象，init 方法负责将该实例对象进行初始化；
解释二：有人说如果将类比喻为工厂，那么_init_方法则是该工厂的生产工人，_init_方法接受的初始化参数则是生产所需原料，_init_方法会按照方法中的语句负责将原料加工成实例以供工厂出货。而_new_则是生产部经理，_new_方法可以决定是否将原料提供给该生产部工人，同时它还决定着出货产品是否为该生产部的产品，因为这名经理可以借该工厂的名义向客户出售完全不是该工厂的产品。
new() 方法的特性：
new() 方法是在类准备将自身实例化时调用;
new() 方法始终都是类的静态方法，即使没有被加上静态方法装饰器 ;
继承自object的新式类才有new；
new至少要有一个参数cls，代表要实例化的类，此参数在实例化时由Python解释器自动提供；
new必须要有返回值，返回实例化出来的实例，这点在自己实现new时要特别注意，可以return父类new出来的实例，或直接是object的new出来的实例。
init()
_init_有一个参数self，就是这个_new_返回的实例，_init_在_new_的基础上可以完成一些其它初始化的动作，_init_不需要返回值;
若new没有正确返回当前类cls的实例，那当前类的init是不会被调用的，即使是父类的实例也不行。
__new__(cls[, ...])
__init__(self[, ...])
###
枚举
要大写的Enum.
from enum import Enum
class SegOpCollect(Enum):
Collect_Sum = 1
Collect_Max = 2
Collect_Min = 3
collect=SegOpCollect.Collect_Max