首页 > 代码库 > 保研机试准备之常用机试代码

保研机试准备之常用机试代码

Java快速IO
 
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(            new InputStreamReader(System.in)));    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));        int n = nextInt();        int m = nextInt();        out.flush();        out.close();    public static int nextInt() throws IOException {        sc.nextToken();        return (int) sc.nval;    }
 
并查集
 
/** * Union Find Set * @author andong * */import java.util.Arrays;public class UFS {        final int MAX = 20;    int[] par;    int[] rank;        public UFS(){                par = new int[MAX];        rank = new int[MAX];        for(int i=0;i<MAX;i++){                        par[i] = i;        }        Arrays.fill(rank, 1);    }        public int find(int x){                int px = x;        while(px!=par[px]){            px = par[px];        }        int t;        while(x!=px){            t = par[x];            par[x] = px;            x = t;        }        return px;    }        public void union(int x,int y){                int px = find(x);        int py = find(y);        if(px != py){            if(rank[px]>=rank[py]){                par[py] = px;                rank[px]+=rank[py];            }            else{                par[px] = py;                rank[py]+=rank[px];            }                        }    }        public int count(){        int cnt = 0;        for(int i=0;i<MAX;i++){            if(par[i]==i)                cnt++;        }        return cnt;    }}

 

拓扑排序
 
public class Topo {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int[][] g = new int[n+1][n+1];        int m = sc.nextInt();        for(int i=0;i<m;i++){            int a = sc.nextInt();            int b = sc.nextInt();            g[a][b] = 1;        }        int[] cnt = new int[n+1];        boolean[] in = new boolean[n+1];        Arrays.fill(in, false);        Arrays.fill(cnt, 0);        for(int i=1;i<=n;i++){            for(int j=1;j<=n;j++){                if(g[i][j]==1)                    cnt[j]++;            }        }        Queue<Integer> q = new LinkedList<Integer>();        for(int i=1;i<=n;i++){            if(cnt[i]==0){                q.add(i);                in[i] = true;            }        }        while(!q.isEmpty()){            int p = q.remove();            for(int i=1;i<=n;i++){                if(g[p][i]==1){                    cnt[i]--;                    if(cnt[i]==0&&!in[i]){                        q.add(i);                        in[i] = true;                    }                    }            }            System.out.print(p);                    }    }}

 

最小生成树的Kruskal算法
 
import java.util.ArrayList;import java.util.Comparator;import java.util.PriorityQueue;/** * Kruskal算法练习 * @author andong * */public class Kruskal {    public static final int INF = Integer.MAX_VALUE;    public static int nV;    public static int[][] graph;    public static UFS ufs;    public static PriorityQueue<Edge> priq;    public static ArrayList<Edge> list;    public static void init(int[][] g){        nV = g.length;        graph = g;        ufs = new UFS(nV);        Comparator<Edge> com = new Comparator<Kruskal.Edge>() {            @Override            public int compare(Edge o1, Edge o2) {                return o1.w<o2.w?-1:1;            }        };        priq = new PriorityQueue<Edge>(nV,com);        list = new ArrayList<Edge>();        //i->j的图        for(int i=0;i<nV;i++){            for(int j=0;j<nV;j++){                if(graph[i][j]>0&&graph[i][j]<INF){                    priq.add(new Edge(i, j,graph[i][j]));                }            }        }        work();    }    public static void work(){        int cnt = 0;        while(!priq.isEmpty()){            Edge edge = priq.remove();            if(ufs.find(edge.s)!=ufs.find(edge.e)){                ufs.union(edge.s, edge.e);                list.add(edge);                cnt++;            }            if(cnt==nV-1){                output();                break;            }        }    }        public static void output(){        for(int i=0;i<list.size();i++){            System.out.println(list.get(i).w);        }    }        static class Edge {        int s,e,w;        public Edge(int s,int e,int w){            this.s = s;            this.e = e;            this.w = w;        }    }        public static void main(String[] args) {        int[][] a = {{0,1,2,4},{0,0,2,5},{0,0,0,3},{0,0,0,0}};        Kruskal.init(a);            }}
 
最短路径的Dijkstra算法
 
import java.util.ArrayList;import java.util.Comparator;import java.util.PriorityQueue;/** * Dijkstra算法练习 * @author andong * */public class Dijkstra {    public static int nV;    public static int src;    public static int[][] graph;    public static int[] dist;    public static ArrayList<Integer> list;    public static PriorityQueue<point> priq;        public static void init(int[][] g,int s){        nV = g.length;        src = s;        graph = g;        dist = new int[nV];        list = new ArrayList<Integer>();        Comparator<point> com = new Comparator<point>() {            public int compare(point o1, point o2) {                return o1.dist<o2.dist?-1:1;            }        };        priq = new PriorityQueue<point>(nV,com);                for(int i=0;i<nV;i++){            dist[i] = graph[src][i];            if(i!=src)    priq.add(new point(i, dist[i]));        }            }        public static void work(){        while(!priq.isEmpty()){            point p = priq.remove();            for(int i=0;i<nV;i++){                int tmp = dist[p.pos]+graph[p.pos][i];                if(tmp<dist[i]){                    dist[i] = tmp;                    priq.add(new point(i, dist[i]));                }            }            list.add(p.pos);        }            }        public static void output(int dest){        System.out.println(dist[dest]);        for(int i=0;i<list.size();i++){            System.out.print(list.get(i));            if(list.get(i)==dest){                System.out.println();                break;            }        }    }        static class point{        int pos,dist;        public point(int pos,int dist){            this.pos = pos;            this.dist = dist;        }    }        public static void main(String[] args) {        int[][] a = {{0,1,2,4},{0,0,2,5},{0,0,0,3},{0,0,0,0}};        Dijkstra.init(a, 0);        for(int i=0;i<4;i++){            Dijkstra.output(i);        }    }}
 
最短路径的Floyd算法
 
import java.util.Arrays;/** * Floyd算法练习 * @author andong * */public class Floyd {    public static int nV;    public static int[][] dist;    public static int[][] inter;    public static void init(int[][] g){        nV = g.length;        dist = new int[nV][nV];        for(int i=0;i<nV;i++)            for(int j=0;j<nV;j++){                if(g[i][j]<Integer.MAX_VALUE)                    dist[i][j] = g[i][j];                else                    dist[i][j] = -1;            }        inter = new int[nV][nV];        for(int i=0;i<nV;i++){            for(int j=0;j<nV;j++){                inter[i][j] = j;            }        }        work();    }        public static void work(){        for(int k=0;k<nV;k++){            for(int i=0;i<nV;i++){                for(int j=0;j<nV;j++){                    if(dist[i][k]>0&&dist[k][j]>0&&dist[i][j]>dist[i][k]+dist[k][j]){                        dist[i][j] = dist[i][k]+dist[k][j];                        inter[i][j] = k;                    }                }            }        }    }        public static void outputDist(int src,int dest){        System.out.println(dist[src][dest]);    }        public static void outputPath(int src,int dest){        if(src=http://www.mamicode.com/=dest){            System.out.print(src);            return;        }        System.out.print(src);        outputPath(inter[src][dest], dest);    }        public static void main(String[] args) {        int INF = Integer.MAX_VALUE;        int[][] a = {{0,1,2,4},{INF,0,2,7},{INF,INF,0,3},{INF,INF,INF,0}};        Floyd.init(a);        for(int i=0;i<4;i++)            outputDist(1, i);        outputPath(1, 3);    }}

 

由前序序列和中序序列构建树
 
1)序列用字符串表示

    

  public static void build(String a,String b){        int len = a.length();        if(len==1){            System.out.println(a);        }        else if(len>1){            char c = a.charAt(0);            String[] temp = b.split(c+"");            int len0 = temp[0].length();            int len1 = temp[1].length();            build(a.substring(1, 1+len0),temp[0]);            build(a.substring(len-len1),temp[1]);            System.out.print(c);        }    }
 
2)序列用整数数组表示
    
  public static void build(int pos, int[] pre, int[] in) {        if (pre.length <= 0)            return;        tree[pos] = pre[0];        int idx = 0;        for (idx = 0; idx < pre.length; idx++) {            if (in[idx] == pre[0])                break;        }        if (idx > 0 && pos * 2 < tree.length) {            int[] leftpre = new int[idx];            int[] leftin = new int[idx];            System.arraycopy(pre, 1, leftpre, 0, idx);            System.arraycopy(in, 0, leftin, 0, idx);            build(pos * 2, leftpre, leftin);        }        if (idx < pre.length - 1 && pos * 2 + 1 < tree.length - 1) {            int[] rightpre = new int[pre.length - idx - 1];            int[] rightin = new int[in.length - idx - 1];            System.arraycopy(pre, 1 + idx, rightpre, 0, pre.length - 1 - idx);            System.arraycopy(in, 1 + idx, rightin, 0, in.length - 1 - idx);            build(pos * 2 + 1, rightpre, rightin);        }    }

 

保研机试准备之常用机试代码