python模板整理

LeetCode

读写文件

# 读
with open("xx.txt","r") as f:
    article = f.read() # 返回字符串
    line = f.readline()
    lines = f.readlines() # 返回字符串列表
# 写
f = open('xx.txt','w')
f.write('...') # 直接覆盖
f = open('xx.txt','a')
f.write('...') # 追加写入

控制台读入

a = input()

格式化输出 format

>>> print('{} {}'.format('hello','world'))  # 不带字段
hello world
>>> print('{0} {1} {0}'.format('hello','world'))  # 带数字编号
hello world hello
>>> print('{a} {tom} {a}'.format(tom='hello',a='world'))  # 带关键字
world hello world
>>> print('{:f}'.format(20)) # 浮点
16 20.000000

main 函数

def main(argv=None):
    if argv is None:
        argv = sys.argv
    pass
if __name__ == "__main__":
    sys.exit(main())

类继承

class A:
    def __init__(self):
        self.x = 0
class B(A):
    def __init__(self):
        super().__init__()
        self.y = 1

字符串操作

join()

s = "-"
seq = ("a", "b", "c") # This is sequence of strings.
print(s.join(seq))

split()

对字符串进行切片，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等，如果第二个参数 num 有指定值，则分割为 num+1 个子字符串(切num次)。

str.split(str, num)

print (str.split( ))       # 以空格为分隔符
print (str.split('i',1))   # 以 i 为分隔符

多个分隔符

re.split(r"[;,?]", line)

strip()

移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。

str.strip([chars])

s = s.strip() #去除首尾空格
s = s.strip('01') #去除首尾字符0或1

replace()

把字符串中的旧字符串替换成新字符串，如果指定第三个参数max，则替换不超过 max 次。

str.replace(old, new[, max])

s = s.replace("is", "was")

count()

统计字符串里某个字符或子字符串出现的次数

str.count(sub, start= 0,end=len(string))

str.count("i")

ord()

以一个字符(长度为1的字符串) 作为参数，返回对应的 ASCII 或者 Unicode 数值。配对函数是chr()。

ord(c)

isdigit()

判断字符串是否全为数字组成

str.isdigit()

string转int

int(str)

string数组转为int数组

results = list(map(int, results))

list 数组

初始化

b = [0 for _ in range(10)]  #也可以b = [0]*10
//二维
a = [[0 for i in range(m)] for j in range(n)]

末尾元素

a[-1]

判断存在

if x in List

逆序遍历

a = [1,3,6,8,9]
for i in a[::-1]:
    print(i)
for i in range(len(a)-1,-1,-1):
    print(a[i])

查找列表中某个值value的位置

p=list.index(value)

逆着反向找

p=list.rindex(value)

去除list中的空字符串

arr = list(filter(None, arr))

插入 insert()

在index位置插入obj

list.insert(index, obj)

得到所有元素平方的list

x = [1,2,3,4,5]
# map
def square(num):
    return num*num
list(map(square,x))
#lambda
list(map(lambda num:num*num, x))
# list comprehensions
[num*num for num in x]

排序sort()/sorted()

list.sort() 方法只可用于list，而 sorted() 函数可以接受任何可迭代对象

list.sort() #直接修改原list
list.sort(cmp=None, key=None, reverse=False)
lis = sorted(dic, key=abs) #将dic的key按照abs排序的key list

key的使用

使用对象的索引作为key：

student_tuples = [
     ('john', 'A', 15),
     ('jane', 'B', 12),
     ('dave', 'B', 10),
]
student_tuples = sorted(student_tuples, key=lambda student: student[2])   # sort by age

对具有命名属性的对象：

class Student:
     def __init__(self, name, grade, age):
         self.name = name
        self.grade = grade
         self.age = age
     def __repr__(self):
         return repr((self.name, self.grade, self.age))
student_objects = [
     Student('john', 'A', 15),
     Student('jane', 'B', 12),
     Student('dave', 'B', 10),
 ]
 sorted(student_objects, key=lambda student: student.age)   # sort by age
 sorted(student_objects, key=lambda student: (student.grade, student.age)) 

使用 itemgetter() 、 attrgetter() 和 methodcaller() 函数：

from operator import itemgetter, attrgetter
sorted(student_tuples, key=itemgetter(2))
sorted(student_objects, key=attrgetter('age'))

多级排序：

按 grade 降序然后 age 升序对学生数据进行排序：先 age 排序，然后再使用 grade 排序：

s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
sorted(s, key=attrgetter('grade'), reverse=True)       # sort on primary key
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

对二维lists进行排序。对于每个list，其他位置降序排序，第num个位置升序排序：

        s = sorted(lists, key=lambda x: x[num])
        s = sorted(s, key=lambda x: x[:num], reverse=True)

zip()

参数为可迭代的对象。将对象中对应的元素打包成一个个元组，返回由这些元组组成的generator。

zip([iterable, ...])

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> list(zip(a,b))
[(1, 4), (2, 5), (3, 6)]
>>> a1, a2 = zip(*zip(a,b)) #zip(*...) 解压，返回二维矩阵式
>>> list(a1)
[1, 2, 3]

可以用于快速构造dict：

keys, values = [1,2,3], [2,3,4]
dict(zip(keys, values))

可以用于转置or旋转二维矩阵

matrix = [[1,2,3],
        [4,5,6],
        [7,8,9]]
list(zip(*matrix)) # [(1, 4, 7), (2, 5, 8), (3, 6, 9)] 相当于转置
list(zip(*matrix))[::-1] # [(3, 6, 9), (2, 5, 8), (1, 4, 7)] 逆时针旋转

enumerate()

作用于一个可遍历的数据对象，返回下标和数据

enumerate(sequence, [start=0])

>>>seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 下标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

dict 字典

类似map的使用

初始化一个空dict

dic = {}

添加元素

if x in dic: dic[x]+=1
else: dic[x]=1

删除元素

dic.pop(x) # x是key

遍历

for x in dic: # x是key

get(key, default=None) 返回指定键的值，如果值不在字典中返回默认值

dict = {'Name': 'Runoob', 'Age': 27}
dict.get('Sex', "Never") #Never

将字典中的值转换成list

list(dic.values())
list(dic.keys())

按key排序 (直接sorted返回的是list)

dic = dict(sorted(dic.items()) #默认就是按key排序
dic = dict(sorted(dic.items(), key=lambda x: x[1])) #按value排序

queue 队列

#向队列中添加元素
Queue.put(item[, block[, timeout]])
#从队列中获取元素并删除
Queue.get([block[, timeout]])
#队列判空
Queue.empty()
#队列大小
Queue.qsize()

优先队列（默认从小到大排序）

from queue import PriorityQueue
pq = PriorityQueue()
pq.put((-x,x)) #构造元组使其从大到小排序

插入格式：q.put((priority number, data))
特点：priority number 越小，优先级越高
其他的操作和队列相同

 q = PriorityQueue()
 q.put((2, "Lisa"))
 q.put((1, "Lucy"))
 q.put((0, "Tom"))
 i = 0
 while i < q.qsize()：
    print(q.get())
# (0，"Tom")
# (1，"Lucy")
# (2，"Lisa")

或者用堆（PriorityQueue也是基于qheap实现的）

import heapq
heapq.heappushpop (heap, item)：将item 放入堆中，然后弹出并返回heap 的最小元素
heapq.heappush(heap, item)：将 item 的值加入 heap 中，保持堆的不变性
heapq.heappop(heap)：弹出并返回 heap 的最小的元素，保持堆的不变性

双端队列

from collections import deque
d = collections.deque()
d += element
while d:
    d.pop() 
    d.popleft()

stack 栈

用list就能直接模拟栈

stack = [3, 4, 5]
stack.append(6)
stack.pop() #从栈顶取出元素

找lower/upper index

python的lower_bound是 bisect.bisect_left(nums, target)（值为target的第一个位置），upper_bound是 bisect.bisect(nums, target)（值为target的末尾位置+1）

collections

collections.Counter

list 的 counter：

from collections import Counter
myList = [1,1,2,3,4,5,3,2,3,4,2,1,2,3]
Counter(myList) #Counter({2: 4, 3: 4, 1: 3, 4: 2, 5: 1})
Counter(myList).items() #[(1, 3), (2, 4), (3, 4), (4, 2), (5, 1)]
Counter(myList).keys() #[1, 2, 3, 4, 5]
Counter(myList).values() #[3, 4, 4, 2, 1]

c = Counter()                           # 创建一个新的空counter
c = Counter('abcasdf')                  # 一个迭代对象生成的counter 
# Counter({'a': 2, 'c': 1, 'b': 1, 's': 1, 'd': 1})
c = Counter({'red': 4, 'yello': 2})      # 一个映射生成的counter
c = Counter(cats=2, dogs=5)             # 关键字参数生成的counter

因为 Counter 实现了字典的 missing 方法， 所以当访问不存在的key的时候，返回值为0:

c = Counter(['apple', 'pear'])
c['orange'] #0

counter 常用的方法：

# elements() 按照counter的计数，重复返回元素
c = Counter(a=4, b=2, c=0, d=-2)
list(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']
# most_common(n) 按照counter的计数，按照降序，返回前n项组成的list; n忽略时返回全部
Counter('abracadabra').most_common(3)
[('a', 5), ('r', 2), ('b', 2)]
# subtract([iterable-or-mapping]) counter按照相应的元素，计数相减
c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d) #Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})
# Counter 间的数学集合操作
c = Counter(a=3, b=1, c=5)
d = Counter(a=1, b=2, d=4)
c + d                       # 相加  
#Counter({'c': 5, 'a': 4, 'd': 4, 'b': 3})
c - d                       # 相减, 只保留正值value  
#Counter({'c': 5, 'a': 2})
c & d                       # 交集:  取两者都有的key,value取小的那一个 
#Counter({'a': 1, 'b': 1})
c | d                       # 并集:  汇聚所有的key, key相同的情况下，取大的value
#Counter({'c': 5, 'd': 4, 'a': 3, 'b': 2})
#常见做法:
sum(c.values())                 # 继承自字典的.values()方法返回values的列表，再求和
c.clear()                       # 继承自字典的.clear()方法，清空counter
list(c)                         # 返回key组成的list
set(c)                          # 返回key组成的set
dict(c)                         # 转化成字典
c.items()                       # 转化成(元素，计数值)组成的列表
Counter(dict(list_of_pairs))    # 从(元素，计数值)组成的列表转化成Counter
c.most_common()[:-n-1:-1]       # 最小n个计数的(元素，计数值)组成的列表
c += Counter()                  # 利用counter的相加来去除负值和0的值

collections.defaultdict

普通的dict需要手动判是否存在和初始化，用defaultdict会方便一些
key不存在的value默认为0，可以直接赋值 如dp[i,j]=xxx

value是int：

s = 'mississippi'
d = defaultdict(int)
for k in s:
     d[k] += 1
d.items()
#[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

value是list：

 s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
 d = defaultdict(list)
for k, v in s:
     d[k].append(v) #可以直接拿任意key放心做list的操作(包括extend等)不用担心not in dic
d.items()
#[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

itertools.groupby

itertools.groupby(iterable[, key])
返回一个产生按照key进行分组后的值集合的迭代器.

people = [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
for k, g in itertools.groupby(people, key=lambda x: x[0]): #以x[0]为key建组
    print(k, g) #key, group
    for x in g:
        #group 中的每一项

collections.OrderedDict

一个 dict 子类的实例，能重新排列字典顺序。
这个dict中如果有key值被覆盖的时候会被挪到末尾，相当于调用了move_to_end

popitem(last=True)
移除并返回一个 (key, value) 键值对。 如果 last 值为真，则按 LIFO 后进先出的顺序返回键值对，否则就按 FIFO 先进先出的顺序返回键值对。

move_to_end(key, last=True)
将现有 key 移动到有序字典的任一端。 如果 last 为真值（默认）则将元素移至末尾；如果 last 为假值则将元素移至开头。如果 key 不存在则会触发 KeyError:

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

数据结构模板相关

实时更新元素后求某区间和（307. Range Sum Query - Mutable）

# Your NumArray object will be instantiated and called as such:
obj = NumArray(nums) # Initializes the object with the integer array nums
obj.update(index,val) # Updates the value of nums[index] to be val
param_2 = obj.sumRange(left,right) # Returns the sum of the elements of nums between indices left and right

1. 线段树

每个节点存储一个区间的左右的端点以及该区间的总和。叶节点存数组的元素，每个内部节点存储其下的叶子之和。创建树需要O(n)时间，查询和更新都是O(log n)。

#Segment tree node
class Node(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None
class NumArray(object):
    def __init__(self, nums):
        def createTree(nums, l, r): 
            if l > r: return None
            #leaf node
            if l == r:  
                n = Node(l, r)
                n.total = nums[l]
                return n
            mid = (l + r) // 2
            root = Node(l, r)
            root.left = createTree(nums, l, mid)
            root.right = createTree(nums, mid+1, r)
            root.total = root.left.total + root.right.total
            return root
        self.root = createTree(nums, 0, len(nums)-1)
    def update(self, i, val):
        def updateVal(root, i, val):
            if root.start == root.end:
                root.total = val
                return val
            mid = (root.start + root.end) // 2
            if i <= mid:
                updateVal(root.left, i, val)
            else:
                updateVal(root.right, i, val)
            root.total = root.left.total + root.right.total
            return root.total
        return updateVal(self.root, i, val)
    def sumRange(self, i, j):
        def rangeSum(root, i, j):
            #If the range exactly matches the root, we already have the sum
            if root.start == i and root.end == j:
                return root.total
            mid = (root.start + root.end) // 2
            #If end of the range is less than the mid, the entire interval lies
            #in the left subtree
            if j <= mid:
                return rangeSum(root.left, i, j)
            #If start of the interval is greater than mid, the entire inteval lies
            #in the right subtree
            elif i >= mid + 1:
                return rangeSum(root.right, i, j)
            #Otherwise, the interval is split. So we calculate the sum recursively,
            #by splitting the interval
            else:
                return rangeSum(root.left, i, mid) + rangeSum(root.right, mid+1, j)
        return rangeSum(self.root, i, j)

2. 树状数组

class NumArray:
    def __init__(self, nums):
        self.arr = [0] * len(nums)
        self.BIT = [0] * (len(nums) + 1)
        for i, n in enumerate(nums): self.update(i, n)
        self.sumRange = lambda i, j: self.Sum(j + 1) - self.Sum(i)
    def update(self, i, val):
        diff, self.arr[i] = val - self.arr[i], val
        i += 1
        while i < len(self.BIT):
            self.BIT[i] += diff
            i += (i & -i) # to next
    def Sum(self, k):
        res = 0
        while k:
            res += self.BIT[k]
            k -= (k & -k) # to parent
        return res

Trie 树

class TrieNode():
    def __init__(self):
        self.children = {}
        self.isEnd=False
class Trie():
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for x in word:
            if x not in node.children:
                node.children[x] = TrieNode()
            node = node.children[x]
        node.isEnd = True

数学相关

最小公倍数

def lcm(a, b):
    return abs(a*b) // math.gcd(a, b)

快速幂

def power(bas,exp):
    ans, sqr = 1, bas
    while exp>0:
        if exp&1:
            ans = ans*sqr
        sqr = sqr*sqr
        exp >>= 1
    return ans

素数筛

sieve = [True]*(n+1)
for i in range(2,n):
    if sieve[i]:
        print(i)
        for j in range(i*i, n, i):
            sieve[j] = False