手撸算法




楼教主的男人八题:
https://wenku.baidu.com/view/cb87fe8cb9d528ea81c779d1.html

远离之前的模板代码,从原理上开始手撸数据结构.

代码均上传至github仓库.

【Dijsktra 2017/5/26】

前向星+优先队列优化+路径回溯
Dijsktra.cpp

【并查集 2017/5/27】

路径压缩,启发式rank优化,将rank较小的并到rank大的集合.

Union-Find-Set.cpp

【树状数组 2017/6/21】

lowbit() x&(-x),前缀和,LA 4329

树状数组.cpp

【快速排序 2017/11/4】

java

import java.util.Random;

public class Quick
{
    private static int cnt=0;
    public static void sort(int[] a){
        Random rand = new Random();
        System.out.println("快排之前:");
        for(int i=0;i<20;++i){
            a[i]=rand.nextInt(100);
            System.out.print(a[i]+" ");
        }
        sort(a,0,a.length - 1);
    }
    public static void sort(int[] a,int lo,int hi){
        if(hi <= lo) return;
        int j = partition(a,lo,hi);//切分
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
    public static int partition(int[] a,int lo,int hi){
        //将数组切分为a[lo..i-1],a[i],a[i+1..hi]
        int i=lo,j=hi+1;//左右扫描指针
        int pt=a[lo];//切分元素
        while(true){
            //扫描左右,检查扫描是否结束并交换元素
            while(a[++i]<pt)if(i==hi) break;//扫描到最左边都没找到大于等于pt的
            while(a[--j]>pt)if(j==lo) break;
            if(i>=j) break;//指针重合
            swap(a,i,j);//没有问题,交换两值
        }
        swap(a,lo,j);//将作为基准的数放回正确的位置,切分为两部分,大于基准,小于基准
        return j;
    }
    public static void swap(int[] a,int x,int y){
        if(x == y) return;
        a[x]=a[x]^a[y];
        a[y]=a[y]^a[x];
        a[x]=a[x]^a[y];
        cnt++;
        System.out.println("\n第"+cnt+"次变化 "+x+" to "+y+" : ");
        for(int item: a){
            System.out.print(item+" ");
        }
    }
    public static void main(String[] args){
        int[] a=new int[20];
        sort(a);
        System.out.println("\n快排之后:");
        for(int item: a){
            System.out.print(item+" ");
        }
    }
}

C++

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;

int qpartition(int *a,int lo,int hi){
    int v=a[lo];
    int i=lo,j=hi+1;
    while(true){
        while(a[++i]<v)if(i==hi)break;
        while(a[--j]>v)if(j==lo)break;
        if(i>=j)break;
        swap(a[i],a[j]);
    }
    swap(a[lo],a[j]);
    return j;
}

void qsort(int *a,int lo,int hi){
    if(lo>=hi) return;
    int j=qpartition(a,lo,hi);
    qsort(a,lo,j-1);
    qsort(a,j+1,hi);
}

int main(){
    srand((unsigned)time(NULL));
    int a[20];
    for(int i=0;i<20;++i){
        a[i]=rand()%100;
        printf("%d ",a[i]);
    }
    printf("\n");
    qsort(a,0,19);
    for(int i=0;i<20;++i){
        printf("%d ",a[i]);
    }
    return 0;
}

Output:

快排之前:
29 41 75 80 82 60 0 51 10 57 26 5 84 70 60 78 10 29 11 56 
第1次变化 1 to 18 : 
29 11 75 80 82 60 0 51 10 57 26 5 84 70 60 78 10 29 41 56 
第2次变化 2 to 17 : 
29 11 29 80 82 60 0 51 10 57 26 5 84 70 60 78 10 75 41 56 
第3次变化 3 to 16 : 
29 11 29 10 82 60 0 51 10 57 26 5 84 70 60 78 80 75 41 56 
第4次变化 4 to 11 : 
29 11 29 10 5 60 0 51 10 57 26 82 84 70 60 78 80 75 41 56 
第5次变化 5 to 10 : 
29 11 29 10 5 26 0 51 10 57 60 82 84 70 60 78 80 75 41 56 
第6次变化 7 to 8 : 
29 11 29 10 5 26 0 10 51 57 60 82 84 70 60 78 80 75 41 56 
第7次变化 0 to 7 : 
10 11 29 10 5 26 0 29 51 57 60 82 84 70 60 78 80 75 41 56 
第8次变化 1 to 6 : 
10 0 29 10 5 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第9次变化 2 to 4 : 
10 0 5 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第10次变化 0 to 3 : 
10 0 5 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第11次变化 0 to 2 : 
5 0 10 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第12次变化 0 to 1 : 
0 5 10 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第13次变化 4 to 6 : 
0 5 10 10 11 26 29 29 51 57 60 82 84 70 60 78 80 75 41 56 
第14次变化 9 to 18 : 
0 5 10 10 11 26 29 29 51 41 60 82 84 70 60 78 80 75 57 56 
第15次变化 8 to 9 : 
0 5 10 10 11 26 29 29 41 51 60 82 84 70 60 78 80 75 57 56 
第16次变化 11 to 19 : 
0 5 10 10 11 26 29 29 41 51 60 56 84 70 60 78 80 75 57 82 
第17次变化 12 to 18 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 70 60 78 80 75 84 82 
第18次变化 13 to 14 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 60 70 78 80 75 84 82 
第19次变化 10 to 13 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 60 70 78 80 75 84 82 
第20次变化 10 to 12 : 
0 5 10 10 11 26 29 29 41 51 57 56 60 60 70 78 80 75 84 82 
第21次变化 10 to 11 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 78 80 75 84 82 
第22次变化 16 to 17 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 78 75 80 84 82 
第23次变化 15 to 16 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 84 82 
第24次变化 18 to 19 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 82 84 
快排之后:
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 82 84 

【动态规划-划分数 2017/11/16】

java

动态转移方程:

dp[i][j]: j的i划分数

j>=i: dp[i][j]=dp[i-1][j]+dp[i][j-i]

i>j: dp[i][j]=dp[i-1][j]

即有一个划分数为0时的目标状态是dp[i-1][j]

import java.util.*;
public class stlin {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n,m,M;
        n=in.nextInt();
        m=in.nextInt();
        M=in.nextInt();
        solve(n,m,M);
    }
    public static void solve(int n,int m,int M){
        int[][] dp=new int[m+1][n+1]; 
        //递推式=>dp[i][j]=dp[i-1][j](ai=0时对应的是i-1划分)+dp[i][j-i]()
        dp[0][0]=1;
        for(int i=1;i<=m;++i){
            for(int j=0;j<=n;++j){
                if(i>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=(dp[i-1][j]+dp[i][j-i])%M;
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

【矩阵链乘 2017/11/17】

输入保证有效,例:

6
30 35
35 15
15 5
5 10
10 20
20 25
结果: 15125

从每隔两个开始计算,即自底向上的动态规划.
仔细想一下吧,计算三个的时候,两个已经计算完成了,计算四个的时候,两个和三个已经计算完成了.

比如求((M1)(M2M3M4M5)),你就不需要再去递归求解M2M3M4M5,直接查表就可以了.

import java.util.*;

public class VeDP {
    public static final int MAXN=100;
    public static final int INF=0x3f3f3f3f;
    static int[] p=new int[MAXN+1];
    static int[][] m=new int[MAXN+1][MAXN+1];
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        int n;
        n=cin.nextInt();
        for(int i=1;i<=n;++i){//因为中间肯定相同
            p[i-1]=cin.nextInt();
            p[i]=cin.nextInt();
        }
        for(int l=2;l<=n;++l){
            for(int i=1;i<=n-l+1;++i){
                int j=i+l-1;
                m[i][j]=INF;
                for(int k=i;k<=j-1;++k){
                    m[i][j]=Math.min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
                }
            }
        }
        System.out.println(m[1][n]);
    }
}

【LIS 2017/11/18】

O(n^2) java:
dp[j]:以c[j]为结尾的最长子序列长度.

//O(n^2)
import java.util.*;
public class LIS {
    private static int[] c=new int[100000+1];
    private static int[] dp=new int[100000+1];
    public static void main(String[] args){
        int n;
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        for(int i=0;i<n;++i){
            c[i]=cin.nextInt();
        }
        /*
         * dp[j]: 以c[j]为结尾从0...i的LIS 
         */
        for(int i=1;i<n;++i){
            for(int j=0;j<i;++j){
                if(c[i]>=c[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        System.out.println(dp[n-1]+1);
    }
}

O(nlgn) c++:
二分搜索+dp 可以过51nod

//O(NlgN)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60000;

int c[maxn],l[maxn];
int n;

int lis(){
    l[0]=c[0];
    int length=1;

    for(int i=1;i<n;++i){
        if(l[length-1]<c[i]){
            l[length++]=c[i];
        }else{
            *lower_bound(l,l+length,c[i])=c[i];
        }
    }

    return length;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&c[i]);
    }

    printf("%d",lis());
    return 0;
}

【2017/11/19 最大正方形】

原题连接: AOJ-Lagest Square

dp[i][j]为向左上方扩展最大的边长.
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

Code C++:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1500;

int dp[maxn][maxn],G[maxn][maxn];
int n,m;

int main(){
    int maxedge=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            scanf("%d",&G[i][j]);
            if(G[i][j]==1)dp[i][j]=0;
            else dp[i][j]=1,maxedge=1;
        }
    }
    for(int i=1;i<n;++i){
        for(int j=1;j<m;++j){
            if(!G[i][j]){
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                maxedge=max(maxedge,dp[i][j]);
            }
        }
    }
    printf("%d\n",maxedge*maxedge);
    return 0;
}

【2017/11/19 最大子矩阵】

博客内写了题解
Code:

#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
#define MAX 1400
using namespace std;

struct Rectangle { int height; int pos; };

int getLargestRectangle(int size,int buffer[]){
    stack<Rectangle> S;
    int maxv=0;
    //通过后一位向前面的计算
    //这里用到的DP大概是无参数getLargestRectangle里面的预处理
    //这里用到的更多是思维吧,对每一行进行计算,最后求出最大值.
    buffer[size]=0;

    for(int i=0;i<=size;++i){
        Rectangle rect;
        rect.height=buffer[i];
        rect.pos=i;
        if(S.empty()){
            S.push(rect);
        }else{
            if(S.top().height < rect.height){
                S.push(rect);
            }else if(S.top().height > rect.height){
                int target=i;
                while(!S.empty() && S.top().height >= rect.height){
                    Rectangle pre=S.top();S.pop();
                    int area=pre.height*(i-pre.pos);
                    maxv=max(maxv,area);
                    target=pre.pos;
                }
                rect.pos=target;
                S.push(rect);
            }
        }
    }
    //printf("\nmaxv: %d\n",maxv);
    return maxv;
}

int H,W;
int buffer[MAX][MAX];
int T[MAX][MAX];

int getLargestRectangle(){
    //预处理每个点离他最近的上边未被污染地板的高度
    for(int j=0;j<W;++j){
        for(int i=0;i<H;++i){
            if(buffer[i][j]){
                T[i][j]=0;
            }else{
                T[i][j]=(i>0)?T[i-1][j]+1:1;
            }
        }
    }
    /*
    例:
        0 0 1 0 0
        1 0 0 0 0
        0 0 0 1 0
        0 0 0 1 0

    After:
        1 1 0 1 1
        0 2 1 2 2
        1 3 2 0 3
        2 4 3 0 4
    */
    int maxv=0;
    //传入两个值 W,列数,处理后T[i]第i行的首地址
    for(int i=0;i<H;++i){
        maxv=max(maxv,getLargestRectangle(W,T[i]));
    }

    return maxv;
}

int main(){
    scanf("%d %d",&H,&W);
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            scanf("%d",&buffer[i][j]);
        }
    }

    printf("%d\n",getLargestRectangle());
    return 0;
}

【2017/11/25 筛法求euler】

#include<iostream>
#include<algorithm>
using namespace std;

///筛法求euler(1)~euler(n)
const int maxn=101;
int euler_1_n[maxn];

void a_euler(){
    euler_1_n[1]=1;
    for(int i=2;i<maxn;++i) euler_1_n[i]=i;
    for(int i=2;i<maxn;++i){
        if(euler_1_n[i]==i){
            for(int j=i;j<maxn;j+=i){
                euler_1_n[j]=euler_1_n[j]/i*(i-1);
            }
        }
    }
}

int main(){
    a_euler();
    for(int i=1;i<101;++i)
        cout<<euler_1_n[i]<<endl;

    return 0;
}

【2018/1/8 开放式散列表】

/*
//alds1_4_c:Dictionary
//算法:开放地址法散列表
//Time: 2018/1/8 星期一
*/
#include<stdio.h>
#include<string.h>

const int M=1000003;
const int L=14;

char H[M][L];

//对于每个字符返回的定义值
int getChar(char ch){
    if(ch=='A') return 1;
    if(ch=='C') return 2;
    if(ch=='D') return 3;
    if(ch=='T') return 4;
    return 0;
}
//对于字符串返回的初始散列值
long long getKey(char str[]){
    long long len=strlen(str),sum=0,p=1;
    for(int i=0;i<len;++i){
        sum+=p*getChar(str[i]);
        //每次获取定义值后p*5,相当于转换成五进制,不会冲突
        p*=5;
    }
    return sum;
}

//开放式散列值计算式: h(k,i)=(h1(k)+i*h2(k))%M
int h1(int key){
    return key%M;
}
//为了保证不会递归冲突(即往下算结果始终相同),必须使h2(key)与M互素
//TLE最好的情况就是改这个函数= =
//目前可以AC的: 1+(key%(M-1))
//(1+key)%(M-1)
int h2(int key){
    return (1+key)%(M-1);
}

//查找
//-1表示找到
//h表示找到第一个可插入点
int find(char str[]){
    long long key=getKey(str),i,h;
    for(i=0;;++i){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return -1;
        else if(strlen(H[h])==0) return h;
    }
    return 0;
}

//插入
void insert(char str[]){
    int key=find(str);
    if(key!=-1) strcpy(H[key],str);
}

int main(){
    for(int i=0;i<M;++i) H[M][0]='\0';
    char str[L],com[L];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s %s",com,str);

        if(com[0]=='i'){
            insert(str);
        }else{
            if(find(str)==-1)
                printf("yes\n");
            else
                printf("no\n");
        }
    }

    return 0;
}

【2018/1/17 强连通分量算法 Tarjan】

详解Tarjan:
http://be-sunshine.cn/index.php/2018/01/17/tarjan-scc-algorithm/

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;

vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    printf("SCC个数: %d\n",scc_cnt);

    for(int i=0;i<n;++i){
        printf("点 %d 的 SCC 编号是: %d\n",i,sccno[i]);
    }
    return 0;
}
/*
6 6

1 0
0 4
4 5
5 1
1 2
2 3
*/

【2018/2/5 排列递推公式+容斥 组合数学】

原题以及题解连接

UVa 11806

#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7;
int T;

const int MAXK=500;
int C[MAXK+10][MAXK+10];
void init(){
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=0;i<=MAXK;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            //组合的一个递推公式
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}

int main(){
    init();
    cin>>T;
    for(int kase=1;kase<=T;++kase){
        int n,m,k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<16;++i){
            int nn=n,mm=m;
            int b=0;
            if(i&1){mm--;b++;}
            if(i&2){nn--;b++;}
            if(i&4){mm--;b++;}
            if(i&8){nn--;b++;}
            //奇数-偶数+
            if(b&1) sum=(sum+mod-C[nn*mm][k])%mod;
            else sum=(sum+C[nn*mm][k])%mod;
        }
        cout<<"Case "<<kase<<": "<<sum<<endl;
    }
    return 0;
}

【2018/2/6 O(n)素数筛法 线性筛法】

一道例题:
http://acm.hdu.edu.cn/showproblem.php?pid=1431

#include<bits/stdc++.h>
#define maxn 100001000
using namespace std;

bool valid[maxn];
int prime[maxn];
/*素数筛法 O(n),对于每个素数只标记一次*/
void getPrime(int n,int &tot,int ans[maxn]){
    memset(valid,true,sizeof(valid));
    for(int i=2;i<=n;++i){
        if(valid[i]){
            tot++;
            ans[tot]=i;
        }
        for(int j=1;((j<=tot) && (i*ans[j]<=n));++j){
            valid[i*ans[j]]=false;
            if(i%ans[j]==0) break;
        }
    }
}

int main(){
    clock_t t1 = clock();
    int tot=0;
    getPrime(100000000,tot,prime);
    clock_t t2 = clock();

    cout<<tot<<endl;
    cout<<prime[5760000]<<endl;
    cout<<"总运行时间为: "<<(double)(t2-t1)/ CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

【2018/3/10 逆元】

逆元递推式

适用于较小数据的情况

LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}

欧拉定理求逆元

如果mod p 不是素数时最好用这个,比较少见

long long euler(int p)  
{  
    long long ans=p,a=p;  
    long long i;  
    for(i=2;i*i<=a;i++)  
    {  
        if(a%i==0)  
        {  
            ans=ans/i*(i-1);  
            while(a%i==0)  
                a/=i;  
        }  
    }  
    if(a>1)  
        ans=ans/a*(a-1);  
    return ans;  
}  

long long eu=euler(mod)-1;  

long long inv(long long a)  
{  
    return Pow(a,eu);  
}  

费马小定理求逆元

a^(p-1)≡1(mod p)

a^(p-2)就是 a 关于p的逆元

前提 a与b互素

long long fast_mod(long long a,long long n,long long Mod){
    long long ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
} 

/*但p(即MOD)是素数时,inv[a]=fast_mod(a,p-2,p)*/

扩展欧几里得求逆元

void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inverse(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

费马小预处理阶乘逆元(一般用于直接求组合数)

ll inv[maxn+10],fac[maxn+10];
///预处理N!的逆元
//费马小定理
/*
 *假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
 *根据这个性质我们可以知道 a的逆元为a^(p-2)
 */
ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}