一些通用模板

1、
普通二分法
def binary_search(nums, target):
    n = len(target)
    left, right = 0, n-1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

二分法变种
在有序数组中查找第一个大于等于x的元素，该元素必定存在
def binary_search(nums, x):
    n = len(nums)
    left, right = 0, n-1
    while left <= right:
        mid = left + (right - left) // 2
        if left == right:
            break
        elif nums[mid] < x:
            left = mid + 1
        else:
            right = mid
    return nums[left]

在有序数组中查找最后一个小于等于x的元素，该是元素必定存在
def binary_search(nums, x):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if left == right or left + 1 == right:
            break
        elif nums[mid] < x:
            left = mid
        else:
            right = mid - 1
    if nums[right] <= x:
        return nums[right]
    else:
        return nums[left]

2、回溯法
回溯法通常用递归实现，递归要考虑3个方面，搜索的设计、递归状态、递归结束条件
搜索设计：划分求解空间，让每一层递归都尝试搜索一部分解空间，直至搜索完
递归状态：状态用来区分不同递归，一般至少有当前位置index这种状态，可能还会携带当前路径path已经当前状态cur等信息。
递归结束条件：找到可行解或者搜索完毕都可以结束。
def dfs(index, cur, path):
    if cur == target:
        ans.append(path.copy())
    if index == n:
        return
    for num in nums:
        if num == error or num in visited:
            continue
        visited.add(num)
        path.append(num)
        dfs(index + 1, cur + num, path)
        path.pop()
        visited.remove(num)

3、并查集
并查集是一种树形结构，用来处理一些不相交集合的查询和合并问题。需要快速连接任意两个点，并且判断任意两个点是否连通时，可以使用并查集模板实现。

4、BFS广度优先搜索
基于队列的广度优先比哪里，将起始节点放入队列中，循环遍历队列中的节点，扩展节点相邻的有效节点，并将其放入队列中
from collections import deque
grid ==[[0]*5 for _ in range(5)]
n, m = len(grid), len(grid[0])
direction = [[0,1], [0,-1],[-1,0],[1,0]]
visited = [[False for _ in range(m)] for _ in range(n)]
queue = deque()
level = 0
queue.append([(0,0)])
visited[0][0] = True
while len(queue) > 0:
    size = len(queue)
    for _ in range(size):
        top = queue.popleft()
        x, y = top[0], top[1]
        for d in direction:
            next_x = x + d[0]
            next_y = y + d[1]
            if (next_x < 0 or next_x >=n or next_y < 0 or next_y >=m):
                continue
            queue.append([next_x, next_y])
            visited[next_x][next_y] = True
level += 1

5、滑动窗口
借助双指针表示左右边界，并不断移动指针，搜索可能存在的有效值。

滑动窗口I
窗口固定大小，最优解与窗口大小无关
初始化大小为len的滑动窗口——检查窗口是否满足条件，更新最优解——循环移动直至抵达边界。
cnt = {0 for _ in range(max(nums))}
ans = 0
for i in range(init_len):
    num = nums[i]
    cnt[num] += 1
left, right = 0, init_len
if check(cnt):
    ans = get(left, right)
while right < len(nums):
    num, num2 = nums[left], nums[right]
    cnt[num] -= 1
    cnt[num2] += 1
    if check(cnt):
        ans = max(ans, get(left, right))
left += 1
right += 1

滑动窗口II
窗口不固定，最优解为最小窗口
初始化大小为0的滑动窗口——右指针移动一步，看是否满足条件，是的话则继续移动左指针，缩小窗口直至不符合条件，更新最优解
left, right = 0, 0
cnt = {0 for _ in range(max(nums))}
ans = len(nums)
while right < len(nums):
    num = nums[right]
    cnt[num] += 1
    while left <= right and check(cnt):
        ans = min(ans, right - left + 1)
        num = nums[left]
        cnt[left] -= 1
        left += 1
    right += 1

滑动窗口III
窗口大小不固定，最优解为最大窗口
初始化大小为0的滑动窗口——右指针移动检查窗口是否不满足条件，是则向右移动左指针，直到满足条件，更新最优解
left, right = 0, 0
cnt = {0 for _ in range(max(nums))}
ans = 0
while right < len(nums):
    num = nums[right]
    cnt[num] += 1
    while not check(cnt):
        num = nums[left]
        cnt[num] -= 1
        left += 1
    ans = max(ans, right - left + 1)
    right += 1

6、数学
素数
法一：开根号法
素数只能被1和它本身整除，非素数处理它们之外，至少还有两个除数a、b，判断某个数是否为素数，可在[2, num - 1]区间查找是否存在num的除数
其中a、b是相互配对的，且必然有一个小，只需搜索[2, min]即可，求最小数的最大值，小数*大数=n，为了让小数尽可能大，最后变成小数*小数=n，小数的最大值为根号n
def isPrime(n):#这个是判断某个数是不是质数
    if n <= 1:#n小于等于1没有质数
        return False
    i = 2#从2开始遍历
    while i*i <= n:#遍历到根号n
        if n % i == 0:#如果某个数是n的因数，返回False
            return False
        i += 1#继续遍历下一个数
    return True#遍历完成，没有返回False，则返回True
法二：埃氏筛法
利用素数的倍数是合数，从小到大遍历每个数字，如果是素数，筛掉其倍数
以布尔数组来记录，并通过标记数组元素为False来模拟筛掉操作。
def countPrime(n):
    if n <= 1:#0和1不是素数
        return []
    flag = [True for _ in range(n+1)] #建立标记数组
    ans = []
    i = 2
    while i*i <= n:#从2开始，循环到sqrt(n)
        if flag[i]:#是素数
            for j in range(i*i, n+1, i):#则从i*i开始到最后遍历，每次增加i即遍历i的倍数
                flag[j] = False#标记为False
        i += 1
    for i in range(2, n+1):#统计筛完的数组,从2开始，0和1不在讨论范围
        if flag[i]:
            ans.append(i)
    return ans

法三：欧拉筛法
让每个合数只被它的最小质因数筛去，避免重复筛选，达到线性复杂度
def euler(n):
    flag = [True for _ in range(n+1)]#标记数组，初始时假设所有数都是素数
    ans = []#存储找到的数
    for i in range(2, n+1):#从2开始遍历
        if flag[i]:#是素数
            ans.append(i)#添加到列表里
        for p in ans:#遍历当前已找到的素数
            if i*p > n:#素数与i的乘积大于n,不需要处理更大的素数了
                break
            flag[i*p] = False#处理到这里，说明小于n，将素数与i的乘积标记为合数
            if i%p == 0:#如果数能被素数整除，则停止处理更大的素数，保证只被最小质因数筛掉
                break
    return ans

7、最大公约数Greatest Common Divisor
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
欧几里得算法：递归计算两个数的最大公约数，小数在前也能正确计算，欧几里得算法会自动交换两者的位置（小数除以大数余数就是小数本身）
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

8、最小公倍数Least Common Mutiple
mutiple有倍数的意思
两个数的乘积等于这两个数的的最大公约数和最小公倍数的乘积
def lcm(a, b):
    return a*b // gcd(a, b)

9、KMP算法
10、马拉车算法
11、树状数组
12、线段数