python代码模板-算法竞赛用

一些常用的算法要做得到熟稔于心。
很多算法其实有自带库了，就直接调库了。

def getBin(n: int) -> str:
    """获取一个数字的二进制"""
    b = str(bin(n))
    if n < 0:
        return b[3:]
    else:
        return b[2:]

全排列

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)]

回文数

def isPalindrome(x: int) -> bool:
    """判断是否是回文数"""
    return x > -1 and str(x)[::-1] == str(x)

图

from typing import List
class Graph:
    def __init__(self, number: int):
        # 0~ number
        self.dicChild = {}  # 节点：孩子节点集合
        self.dicFather = {}  # 节点：祖先节点集合
        for i in range(number):
            self.dicChild[i] = set()
            self.dicFather[i] = set()
        self.childCountDic = {}  # 节点编号 : 子节点的数量
        self.zeroChildNode = set()  # 存放没有孩子节点的集合
        self.nextZero = set()  # 删除节点方法的时候会用到这个变量
    def initSet(self, childList: List[List[int]]):
        for i, childArr in enumerate(childList):
            for child in childArr:
                self.dicFather[child].add(i)
                self.dicChild[i].add(child)
            self.childCountDic[i] = len(childArr)
            if len(childArr) == 0:
                self.zeroChildNode.add(i)
    def delZeroChild(self):
        # 执行一次删除所有没有子节点的节点的操作
        for node in self.zeroChildNode:
            self.delNode(node)
        self.zeroChildNode = self.nextZero
        self.nextZero = set()
    def delNode(self, node: int):
        # 删除一个节点
        for n in self.dicFather[node]:
            self.dicChild[n].remove(node)
            if len(self.dicChild[n]) == 0:
                self.nextZero.add(n)
        for n in self.dicChild[node]:
            self.dicFather[n].remove(node)
        self.dicChild.pop(node)  # 子孩子字典中直接删除这个节点
        self.dicFather.pop(node)  # 父字典中直接删除这个节点

给字典排序

import collections

d = dict(collections.Counter('Hello World'))
#  d.items() 是  [(k, v), (k, v),(k, v)...] 组成的列表
print(sorted(d.items(), key=lambda x: x[1], reverse=True))

字典计数器

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))

日期

from datetime import datetime, timedelta

d = datetime(2001, 5, 15, 13, 59, 59)
dt = timedelta(days=1, seconds=1, microseconds=1, milliseconds=1, minutes=1, hours=1, weeks=1)

最大公约数（其实math里面有）

def gcd(n1, n2):
    return gcd(n2, n1 % n2) if n2 > 0 else n1

最小公倍数

def gcd(n1, n2):
    return gcd(n2, n1 % n2) if n2 > 0 else n1
def lcm(n1, n2):
    return n1 * n2 // gcd(n1, n2)

序列组合

from itertools import combinations

print(list(combinations([1, 2, 3], 2)))  # [(1, 2), (1, 3), (2, 3)]

组合数

def c(m, n):
    import math
    return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))

自定义排序

arr = [23, 131, 5, 124, 35]
arr = sorted(arr, key=lambda item: item, reverse=True)
print(arr)

质数

def isPrim(n: int) -> bool:
    """判断是否是质数  O(✓n)"""
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def countPrim(n: int) -> int:
    """[0, n) 内有多少个质数 厄拉多塞筛法 O(n*(?n))"""
    count = 0
    signs = [True] * n
    for i in range(2, n):
        if signs[i]:
            count += 1
            for j in range(i + i, n, i):
                signs[j] = False
    return count

队列

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)