二分

左闭右闭区间

while <=
l, r = m+1，m-1
==return mid
return left

def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left  # 或者 right+1

=x => bin(x)
x => bin(x+1)
<=x => bin(x+1)-1 # 小于等于x对应大于x的那个index-1
<x => bin(x)-1

图论

floyd O(n^3)

枚举所有点，从中间计算
Distance[i][j] = minimum (Distance[i][j], (Distance from i to A) + (Distance from A to j ))

for p in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j]=min(dp[i][j],dp[i][p]+dp[p][j])

Dijkstra O(n^2)

def dijkstra(u: int) -> int:
    dist = [inf] * n
    dist[u] = 0
    vis = [False] * n
    for _ in range(n):
        k = -1
        for j in range(n):
            if not vis[j] and (k == -1 or dist[k] > dist[j]):
                k = j
        vis[k] = True
        for j in gg[k]:
            dist[j] = min(dist[j], dist[k] + g[k][j])
    return sum(d <= distanceThreshold for d in dist)

下一个排列

思路：

1. 先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
2. 再找出另一个最大索引 l 满足 nums[l] > nums[k]；
3. 交换 nums[l] 和 nums[k]；
4. 最后翻转 nums[k+1:]。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        firstIndex = -1
        n = len(nums)
        def reverse(nums, i, j):
            while i < j:
                nums[i],nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                firstIndex = i
                break
        #print(firstIndex)
        if firstIndex == -1:
            reverse(nums, 0, n-1)
            return 
        secondIndex = -1
        for i in range(n-1, firstIndex, -1):
            if nums[i] > nums[firstIndex]:
                secondIndex = i
                break
        nums[firstIndex],nums[secondIndex] = nums[secondIndex], nums[firstIndex]
        reverse(nums, firstIndex+1, n-1)

作者：powcai
链接：https://leetcode.cn/problems/next-permutation/solutions/3830/xia-yi-ge-pai-lie-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二叉树迭代遍历

        s = [root]
        res = []
        while s:
            tmp  = s.pop()
            if isinstance(tmp,TreeNode):
                #注意栈是先进先出，所以right在left前边
                s.extend([tmp.right,tmp.left,tmp.val])#前序
                s.extend([tmp.right,tmp.val,tmp.left])#中序
                s.extend([tmp.val,tmp.right,tmp.left])#后序
            elif isinstance(tmp,int):
                res.append(tmp)
        return res
另一种：
def inorderTraversal(root):
        if not root: return []
        return inorderTraversal(root.left)+[root.val]+inorderTraversal(root.right)

KMP

        #构造next数组，类似单调栈
        j=0
        next=[0]*len(needle)
        for i in range(1,len(needle)):
            while j>0 and needle[i]!=needle[j]:
                j=next[j-1]
            if needle[i]==needle[j]:
                j+=1
            next[i]=j

        if len(needle)==0:
            return 0
        j=0
        ans=0
        for i in range(len(haystack)):
            while j>0 and haystack[i]!=needle[j]:
                j = next[j-1]
            if haystack[i]==needle[j]:
                j+=1
                if j==len(needle):
        ######求子串出现的位置
                    return i-j+1
        return -1
        ######

        ######求字串出现的次数
                    ans+=1
                    j=next[j-1]
        return ans
        ######

---

---

//python 二分

---

def search(nums, target):
    l,r=0,len(nums)-1
    while l<=r:
        mid=l+(r-l)//2
        if target==nums[mid]:
            return mid
        if nums[mid]>target:
            r=mid-1
        else:
            l=mid+1
    return -1

---

//优先队列定义
priority_queue<int,vector<int>,greater<int>> q;

---

//并查集

---

//最大公约数gcd
int gcd(int a,int b) {
if(b==0) return a;
else
return gcd(b,a%b);
}
//最大公倍数lcm
int lcm(int a,int b){
return a/gcd(a,b)*b;
}

---

//int字符串互转

include <iostream>

using namespace std;
int main() {
int a;
char aa[425]="12345678900";
//注意有&符号!!!
sscanf(aa,"%lld",&a);//注意有&符号!!!
sprintf(aa,"%d",a);
cout<<a;
}

---

//质数欧拉筛
int prime[100005], total=0;
bool check[100005];
void get_primes(int n){//筛出[1,n]之间的素数
for (int i = 2; i <= n; ++i) {
if (!check[i]) prime[total++] = i;
for (int j = 0; j < total && i * prime[j] <= n; ++j) {
check[i*prime[j]] = 1;
if (i % prime[j] == 0) break;//保证每个数被他最小的质因数约去
}
}
}

n=int(input())
primes=[]
checks=[False]2+[True]n
for i in range(2,n+1):
if checks[i]==True:
primes.append(i)
checks[i]=False
for k in primes:
if ik>=len(checks):
break
checks[ik]=False
if i%k==0:
break

---

//计算n！中有多少个质因子p
int cal(int n,int p){
if(n<p) return 0;
return n/p+cal(n/p,p);
}

---