算法模板

最大公约数

public int gcd(int a, int b){
    return b==0?a:gcd(b,a%b);
}

最小公倍数

public int lcm(int a, int b){
    return a*b/gcd(a,b);
}

求组合数

//求组和数Cn2(n个数里面选两个)；
    long C(int a,int b){
        long res=1l;
        for(int i=a,j=1;j<=b;i--,j++){
        res=res*i/j;
        }
        return res%mod;
    }
    long get(int a,int b,int c){
        if(a==b&&b==c)return C(count[a],3);//cn3
        if(a==b)return C(count[a],2)*count[c]%mod;
        if(b==c)return C(count[b],2)*count[a]%mod;
        return count[a]*count[b]*count[c]%mod;
    }

KMP

int[] getnext(String s){
    int[] next=new int[s.length()];
    int j=0;
    next[0]=0;
    for(int i=1;i<s.length();i++){
        while(j>0&&s.charAt(i)!=s.charAt(j)){
            j=next[j-1];//指向前一位
        }
        if(s.charAt(i)==s.charAt(j))j++;
        next[i]=j;
    }
    return next;
    }

   // 求next数组
	        int j = 0;
	        int n = pj.length();
	        int[] ne = new int[n];
	        for (int i = 1; i < n; i ++) {
	            while (j > 0 && pj.charAt(i) != pj.charAt(j)) {
	                j = ne[j - 1];
	            }
	            if (pj.charAt(i) == pj.charAt(j)) {
	                j ++;
	            }
	            ne[i] = j;
	        }

树状数组

int[] tree;
int len;
/**
 * 单点更新
 * @param i     原始数组索引 i
 * @param delta 变化值 = 更新以后的值 - 原始值
 */
public void update(int i, int delta) {
    // 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
    while (i <= len) {
        tree[i] += delta;
        i += lowbit(i);
    }
}
/**
 * 查询前缀和
 * @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
 */
public int query(int i) {
    // 从右到左查询
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

public static int lowbit(int x) {
    return x & (-x);
}

线段树

class Solution {
    int[] tree;
    int[] p;
    public int reversePairs(int[] nums) {
       int n=nums.length;
       p=new int[n];
       tree=new int[4*n];
    }
    void creat(int node,int start,int end){
        if(start==end){
              tree[node]=p[start];
              return;}
        int mid=(start+end)>>1;
        //左右子树节点位置
        int left=node*2;
        int right=node*2+1;
        //创建左右子树
        creat(left,start,mid);
        creat(right,mid+1,end);
        tree[node]=tree[left]+tree[right];
    }
    void update(int node,int start,int end,int x,int val){
        if(start==end){
            //找到节点更新值;
            p[x]=val;
            tree[node]=val;
             return;
        }
        int mid=(start+end)>>1;
        //左右子树节点位置
        int left=node*2;
        int right=node*2+1;
        if(x>=start&&x<=mid)update(left,start,mid,x,val);
        else update(right,mid+1,end,x,val);
        tree[node]=tree[left]+tree[right];
    }
    //查询区间[l,r]之间的值的总和
    int query(int node,int start,int end,int l,int r){
        //不在区间内
       if(start>r||end<l)return 0;
       //整个区间
       else if(start>=l&&end<=r)return tree[node];
       //继续查找
       else{
            int mid=(start+end)>>1;
            //左右子树节点位置
            int left=node*2;
            int right=node*2+1;
            int leftsum=query(left,left,mid,l,r);
            int rightsum=query(right,mid+1,end,l,r);
            return leftsum+rightsum;
       }
    }
}

字典树

class Trie {
    boolean isEnd;
    Trie[] son;
    public Trie() {
       isEnd=false;
       son=new Trie[26];
    }
    
    public void insert(String s) {
        Trie root=this;
           for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
              if(root.son[c-'a']==null)root.son[c-'a']=new Trie();
              root=root.son[c-'a'];
          }
          root.isEnd=true;
    }
    
    public boolean search(String s) {
        Trie root=this;
           for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
              if(root.son[c-'a']==null)return false;
              root=root.son[c-'a'];
          }
          return root.isEnd;
    }
    
    public boolean startsWith(String s) {
          Trie root=this;
            for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
              if(root.son[c-'a']==null)return false;
              root=root.son[c-'a'];
          }
          return true;
    }
}

快速幂

//求a的n次方
int quickpow(int a,int n){
    int res=1;
    while(n>0){
         if(n&1==1) res=res*a;
           a=a*a;
           n>>=1; 
        }
    return res;
}

筛质数

int[] primes=new int[n];
int cnt;
boolean[] =new boolean st[N];
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

并查集

int[] p,s;
int size;
void init(int size){
    this.size=size;
    p=new int[size];
    s=new int[size];
    for(int i=0;i<size;i++){
        p[i]=i;
        size[i]=1;
    }
}
int find(int x){
    if(x!=p[x])return find(p[x]);
    return p[x];
}
boolean connect(int a,int b){
    return find(a)==find(b);
}
void union(int a,int b){
    int x=find(a),y=find(b);
    //本身相连
    if(x==y)return;
    //size小的接到大的上面
    if(s[x]>s[y]){
        p[y]=x;
        s[x]+=s[y];
    }
    else{
        p[x]=y;
        s[y]+=s[x];
    }
}

一维前缀和

int[] s=new int[n];
for(int i=1;i<=n;i++)s[i]=s[i-1]+num[i-1];
int get(int x,int y){
    return s[y]-s[x-1];
}

二维前缀和

int[][] s=new int[m][n];
 for(int i=1;i<=m;i++){
      for(int j=1;j<=n;j++){
           //二位前缀和
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+grid[i-1][j-1];
      }    
 }
  //计算(x1,y1)为左上端点和(x2,y2)为右下端点的矩形前缀和
   int get(int x1,int y1,int x2,int y2){
       return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
   }