模板

# 快排
1. 找到中间的那个数字x,定义左右端点
2. 递归处理要求x的左边都比x小,右边都比x大
3. 找到x左边第一个大于他的和右边第一个小于他的然后交换
4. 递归剩下两部分

void quickSort(int[] q, int l, int r) {

    if(l >= r) return ;

    int x = q[l + r >> 1], i = l - 1, j = r + 1;

    while(i < j) {
        while(q[ ++ i] < x);
        while(q[ -- j] > x);
        if (i < j) {
            swap(q, i, j);
        }
    }
    quickSort(q, l, j);
    quickSrot(q, j + 1, r);
}

双指针

for (int i = 0, j = 0; i < n; i ++) {
    while(j < n && check(i,j)) j ++;
}

二分

从左边靠近寻找的x

int l = 0, r = n - 1;
while(l < r) {
    int mid = l + r >> 1;
    if (nums[mid] < x)  l = mid + 1;
    else r = mid;
}

从右边靠近寻找的x
int l = 0, r = n - 1;
while(l < r) {
    int mid = l + r + 1;
    if (nums[mid] > x) r = mid - 1;
    else l = mid;
}

单调栈

求x左边或者右边最靠近他的最大/小的值或者序号

for (int i = 0; i < n; i ++) {
    while(!stk.isEmpty() && stk.peek() >= x) stk.pop();
    if (!stk.isEmpty()) sout(stk.peek());
    else sout(-1);
    stk.add(nums[i]);
}

单调队列

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++) {
    if (hh <= tt && i - k + 1 > q[hh]) hh ++;
    while(hh <= tt && a[q[tt]] >= a[i]) tt --;
    q[++ tt] = i;
    if (i - k + 1 >= 0) sout(q[hh]);
}

Trie树

把一个单词插入到树中,一共2个操作insert/query
1. 定义自己和儿子的关系 son[N][26]; // idx ~ 26
2. 定义全局指针idx 
3. 定义出现次数或者is_end结束表示
void insert(String s) {
    char[] c = s.toCharArray();

    int p = 0;
    for (int i = 0; i < c.length; i ++) {
        int u = c[i] - 'a';
        if (son[p][u] == 0) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

# 出现多少次
int query(String s) {

    char[] c = s.toCharArray();
    int p = 0;
    for (int i = 0; i < c.length; i ++) {
        int u = c[i] - 'a';
        if (son[p][u] == 0) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

合并集合  int a = find(nums[i]); int b = find(nums[b]);
p[a] = b;  // 把a加入b的集合


int[] p = new int[N];
// 初始化 p[x] = x;
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

树与图的存储

int h[N], e[N], ne[N], idx;
Arrays.fill(h, -1);
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

树与图的dfs

int dfs(int u) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

树与图的bfs

Queue<Integer> q;
st[1] = true; // 表示1号点已经遍历过
q.add(1);

while(!q.isEmpty()) {
    int t = q.pop();


    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            q.push(j);
        }
    }

}

拓扑排序

图中的每条表(x, y) x都出现在y之前

bool topsort() {
    Queue<Integer> q = new LinkedList<>();

    // 1. 入度为0的入队
    for(int i = 1; i <= n; i ++) {
        if(ru[i] == 0) q.add(i);
    }

    while(!q.isEmpty()) {
        int t = q.poll();

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0) {
                q.add(j);
            }
        }
    }
    // 是否能成拓扑排序 ru[i]是不是点都存在了     
}

单源最短路spfa算法

int n;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; // 每个点到1号点的最短举例
boolean[N] st; // 每个点是否在队列中

int spfa() {
    Arrays.fill(dist, 0x3f3f3f);
    dist[1] = 0;

    Queue<Integer> q = new LinkedList<>();
    q.add(1);
    st[1] = true;

    while(!q.isEmpty()) {
        int t =q.poll();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.add(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

稠密图单源最短路

int dijkstra() {
    Arrays.fill(dist, INF);
    dist[1] = 0;
    // 1. 循环每条边
    for (int i = 0; i < n - 1; i ++) {
        // 2.找到举例源点最近的点
        int t = -1;
        for (int j = 1; j <= n ;j ++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t]) {
                t = j;
            }
        }
        st[t] = true;

        // 更新其他店
        for (int j = 1; j <= n; j ++) {
            if (dist[j] > dist[t] + g[t][j]) {
                dist[j] = dist[t] + g[t][j];
            }
        }
    }
    if (dist[n] == INF) return -1;
    else return dist[n];

}

多源最短路

1. 初始化
for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {
        if (i == j) d[i][j] = 0;
        else d[i][j] = INF;
    }
}

void floyd() {
    for (int k = 1; k <= n; k ++) {
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

最小生成树

图转成树 边权最小

1. 并查集 + 按照边权排序
2. 遍历每条小边然后合并到一个集合中

int n, m; // 点数和边数
int p[N];
Edge[] eges = new int[M];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {

    Arrays.sort(edges);

    for (int i = 1; i <= n; i ++) p[i] = i;

    int res = 0; int cnt = 0;
    for (int i = 0; i < m; i ++) {
        int a = edg[i].a;
        int b = edg[i].b;
        int c = edge[i].c;

        a = find(a); 
        b = find(b);
        if (a != b) {
            p[a] = b;
            res += c;
            cnt ++;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}
class Edge implemenets Comparable<Edge> {
    int a, b, c;

    public int compareTo(Edge o) {
        reutrn this.c - o.c;

    }
}

图的遍历

地图模型：
蛇梯图 稠密图最短路



dist[n][m]: 记录 由某个点转移到某个点的次数
最小基因： s--> t
Map<String, Integer> 由字符串s--->变化到t 的次数
for (int i = 0; i < t.length(); i ++ ) {
    for (int j = 'a'; j <= 'z'; j ++) {
        xxx
    }
}

回溯： 组合

求一个数组里某些组合
n个里面选k个
void dfs(int u, int n, int k, List<Integer> path) {
    if (path.size() > k ) return ;
    if (path.size() == k _ {
        ans.add(new ArrayList<>(path));
        return ;
    }

    for (int i = u; i <= n; i ++) {
        path.add(i);
        dfs(i + 1, n, k, path); // 这里如果是i则可重复选，i + 1则不可重复选
        path.remove(path.size() - 1);
    }
}

排列

void dfs(int u, int[] nums, List<Integer> path) {
if (u == n) {
        for (int i = 0; i < n; i ++) {
            sout(p[i]);
        }
        return;
    }

    for (int i = 1; i <= n ;i ++) {
        // 数字i
        if (st[i]) continue;
        st[i] = true;
        path.add(nums[i]);
        dfs(u + 1, nums, path);
        path.remove(path.size() - 1);
        st[i] = false;
    }
}

试除法选质数

boolean check(int x) {

    for (int i = 2; i <= x / i; i ++) {
        if (x % i == 0) return false;
    }
    return true;
}

01背包

f[i][j]; 第i个物品体积为j最大价值

for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        // 不选
        f[i][j] = f[i-1][j]; 
        if (j >= v[i]) {
            f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    return f[n][m];
}

完全背包

物品不限 还是有点区别
int[] f = new int[N];// f[j] 体积为j得最大价值

for(int i = 1; i <= n; i++) {
    for(int j = v[i]; j <= m;j++) {
        f[j] = Math.max(f[j], f[j-v[i]] + w[i]);
    }
}

return f[m];

多重背包问题

// 最多选s个

for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        f[i][j] = f[i-1][j];
        if (j >= v[i]) {
            for (int k = 1; k <= s[i]; k ++) {
                if (j >= k * v[i]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
    }
    return f[n][m];
}

分组背包问题

for(int i = 1; i<= n; i++) {
            for(int j = 0; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
                for (int k = 0; k < s[i]; k ++) {
                    if (j >= v[i][k]) {
                        f[i][j] = Math.max(f[i][j], f[i-1][j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
return f[n][m];

区间dp

枚举区间长度 和 左端点
for (int len = 2; len <= n; len ++) {
    for (int i = 1; i + len - 1 <= n; i ++) {
        int j = i + len - 1;
        f[i][j] = 0x3f3f3f3f;
        for (int k = i; k < j; k ++) {
            f[i][j] = Math.max(f[i][j], f[i][k] + f[k + 1][j]  + s[j] - s[i-1]);
        }
    }
}
return f[1][n];

线性DP

(是否需要初始化)
1.公共子序列f[i][j] 两个字符串前i个和前j个
2.最长上升子序列 
3.最短编辑距离
4.