常见的基本算法整理

分治算法

• 思想：
  把一个问题分解为几个子问题，这些子问题原问题相似，但问题的规模小.然后递归地求解子问题，如果子问题的规模小到可以用直接的方法求出解，则停止递归．最后把这些子问题的解组合成原问题的解．

• 优点：
  它的运行时间往往可以由子问题的运行时间得到．

• 程序

  合并算法：

  int n=10;
  int[] B=new int[n];
  public void mergeSort(int[] A,int left,int right){
  	if(left<right){
  		int mid=(left+right)/2;
  		mergeSort(A,left,mid);
  		mergeSort(A,mid+1,right);
  		merge(A,left,mid,right);
  	}
  }
  private  void merge(int[] A,int left,int mid,int right){
  	for(int i=left;i<=right;i++){
  		B[i]=A[i];
  	}
  	int l=left,r=mid+1,k=left;
  	while(l<=mid && r<=right){
  		if(B[l]<B[r])
  			A[k++]=B[l++];
  		else
  			A[k++]=B[r++];
  	}
  	while(l<=mid)A[k++]=B[l++];
  	while(r<=right)A[k++]=B[r++];
  }

快速排序算法:

public void quickSort(int[] A,int left,int right){
	if(left<right){
		int p=partition(A,left,right);
		quickSort(A,left,p-1);
		quickSort(A,p+1,right);
	}
}
/**
 * 用ｉ作为标志位，将小于Ａ［right］的值存放在Ａ[i]左边，ｉ表示最左边的一个小于x的数．
 * ｊ往后查找，如果遇到小于x的数则i++ 位置的值交换，即放到前面，而i++的值移到后面了．
 * @param a
 * @param left
 * @param right
 * @return
 */
private int partition(int[] A, int left, int right) {
	int x=A[right];
	int i=left-1;
	int temp;
	for(int j=left;j<=right-1;j++){
		if(A[j]<=x){
			i++;
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
		}
	}
	i++;
	temp=A[i];
	A[i]=A[right];
	A[right]=temp;
	return i;
}

partition的第二种写法：

private int partition1(int[] A,int left,int right){
	int x=A[left];
	while(left<right){
		while(left<right && A[right]>x) right--;
		A[left]=A[right];
		while(left<right && A[left]<x) left++;
		A[right]=A[left];
	}
	A[left]=x;
	return left;
}

动态规划

思想

采用分治算法的思想，将原问题的解分解为若干子问题，然后分别求解子问题，最后将子问题的解组合起来得到原问题的解．动态规划不是递归地求解各个子问题，而是从简单问题入手，逐步求解，直到求出原问题的解．它的高明之处在于避免重复计算那些重复出现的子问题，即重叠子问题．

步骤

• 1.找出最优解的结构
• 2.递归定义一个最优解的值
• 3.以自底向上的方式（从最简单的问题开始入手）计算出最优值的解
• 4.根据计算最优解的信息，构造一个最优解

斐波那契数列

public static int fibonacci(int num){
	int[] F=new int[num+1];
	F[0]=1;
	F[1]=1;
	for(int i=2;i<=num;i++){
		F[i]=F[i-1]+F[i-2];
	}
	return F[num];
}

装配线调度问题

public static void dpFastestWay(int[][] a,int[][] t,int[] e,int[] x,int n)  	{
	int[] f1=new int[n];
	int[] f2=new int[n];
	int[][] l=new int[2][n];
	
	f1[0]=e[0]+a[0][0];
	f2[0]=e[1]+a[1][0];
	for(int i=1;i<n;i++){
		if(f1[i-1]+a[0][i]<=f2[i-1]+t[1][i-1]+a[0][i]){
			f1[i]=f1[i-1]+a[0][i];
			l[0][i]=0;
		}else{
			f1[i]=f2[i-1]+t[1][i-1]+a[0][i];
			l[0][i]=1;
		}
		if(f2[i-1]+a[1][i]<=f1[i-1]+t[0][i-1]+a[1][i]){
			f2[i]=f2[i-1]+a[1][i];
			l[1][i]=1;
		}else{
			f2[i]=f1[i-1]+t[0][i-1]+a[1][i];
			l[1][i]=0;
		}
	}
	int f,lIdx;
	if(f1[n-1]+x[0]<=f2[n-1]+x[1])
	{
		f=f1[n-1]+x[0];
		lIdx=0;
	}else{
		f=f2[n-1]+x[1];
		lIdx=1;
	}
	System.out.println(f);
	printStation(l,lIdx);
}
private static void printStation(int[][] l,int lIdx){
	int i=lIdx;
	int[] stack=new int[l[0].length];
	int top=0;
	for(int j=l[0].length-1;j>=0;j--){
		stack[top++]=i;
		i=l[i][j];
	}
	for(int j=0;j<stack.length;j++){
		System.out.println("line "+(stack[--top]+1)+" ,sation"+(j+1));
	}
}

矩阵链乘法问题

public static void matrixChain(int[] p){
	int[][] m=new int[p.length][p.length];
	int[][] s=new int[p.length][p.length];
	int n=p.length-1;
	for(int i=1;i<=n;i++)
		m[i][i]=0;
	int j,temp;
	for(int c=2;c<=n;c++){
		for(int i=1;i<=n-c+1;i++){
			j=i+c-1;
			m[i][j]=Integer.MAX_VALUE;
			for(int k=i;k<=j-1;k++){
				temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(temp<m[i][j]){
					m[i][j]=temp;
					s[i][j]=k;
				}
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(j=1;j<=n;j++)
			System.out.print(m[j][i]+" ");
		System.out.println();
	}
	printParents(s,1,n);
	
}

private static void printParents(int[][] s, int i, int j) {
	if(i==j) System.out.print("A"+i);
	else {
		System.out.print("(");
		printParents(s,i,s[i][j]);
		printParents(s,s[i][j]+1,j);
		System.out.print(")");
	}
}

最长公共子序列

public static void lCSlength(char[] X,char[] Y,int m,int n){
	int[][] c=new int[m+1][n+1];
	int[][] b=new int[m+1][n+1];
	for(int i=1;i<=m;i++) c[i][0]=0;
	for(int i=0;i<=n;i++) c[0][i]=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(X[i]==Y[j]) {
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1;
			}else if(c[i-1][j]>=c[i][j-1]){
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}else{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
	}
	System.out.println(c[m][n]);
	printLCS(b,X,m,n);
}

private static void printLCS(int[][] b, char[] X,int i,int j) {
	if(i==0 || j==0) return;
	if(b[i][j]==1){
		printLCS(b,X,i-1,j-1);
		System.out.print(X[i]+" ");
	}else if(b[i][j]==2){
		printLCS(b,X,i-1,j);
	}else
		printLCS(b,X,i,j-1);
}

0-1背包问题

public static void knapsack(int[][] S,int W){
	int[][] V=new int[S.length][W+1];
	int[][] b=new int[S.length][W+1];
	int w,i;
	for(w=0;w<S[0][0];w++) V[0][w]=0;
	for(w=S[0][0];w<=W;w++) V[0][w]=S[0][1];
	
	for(i=1;i<S.length;i++){
		for(w=0;w<=W;w++){
			if(S[i][0]>w){
				V[i][w]=V[i-1][w];
				b[i][w]=1;
			}else if(V[i-1][w]>(V[i-1][w-S[i][0]]+S[i][1])){
				V[i][w]=V[i-1][w];
				b[i][w]=1;
			}else{
				V[i][w]=V[i-1][w-S[i][0]]+S[i][1];
				b[i][w]=2;
			}
		}
	}
	printKnapsackItem(b,S,S.length-1,W);
}

private static void printKnapsackItem(int[][] b,int[][] S, int i, int w) {
	if(i==-1 || w==0) return;
	if(b[i][w]==2){
		printKnapsackItem(b,S,i-1,w-S[i][0]);
		System.out.print((i+1)+" ");
	}else{
		printKnapsackItem(b,S,i-1,w);
	}
}

最优二叉搜索树

public static void optimalBST(double[] p,double[] q){
	int n=p.length-1;
	double[][] e=new double[n+2][n+1];
	double[][] w=new double[n+2][n+1];
	int[][] root=new int[n+2][n+1];
	
	for(int i=1;i<=n+1;i++){
		e[i][i-1]=q[i-1];
		w[i][i-1]=q[i-1];
	}
	int j;
	double t;
	for(int c=1;c<=n;c++){
		for(int i=1;i<=n-c+1;i++){
			j=i+c-1;
			e[i][j]=Integer.MAX_VALUE;
			w[i][j]=w[i][j-1]+p[j]+q[j];
			for(int r=i;r<=j;r++){
				t=e[i][r-1]+e[r+1][j]+w[i][j];
				if(t<e[i][j]){
					e[i][j]=t;
					root[i][j]=r;
				}
					
			}
		}
	}
	System.out.println(e[1][n]);
	printBST(root,1,n);
}
private static void printBST(int[][] root, int i, int j) {
	if(i==0 || j<0) return;
	if(j==i-1){
		System.out.print("d"+(i-1)+" ");
	}else{
		printBST(root,i,root[i][j]-1);
		System.out.print("k"+root[i][j]+" ");
		printBST(root,root[i][j]+1,j);
	}
}

贪心算法：

思想

总是在每一步骤中做最优的决策，希望通过这一系列的局部最优决策，获得问题的全局最优解．

任务选择问题

public static List<Integer> taskSelect(int[] S,int[] F){
	List<Integer> result=new ArrayList<Integer>();
	result.add(1);
	int i=0;
	for(int m=1;m<F.length;m++){
		if(S[m]>=F[i]){
			result.add(m+1);
			i=m;
		}
	}
	for(int a:result){
		System.out.print(a+" ");
	}
	return result;
}

背包问题

public static void knapsack(int[][] S,int W){
	int n=S[0].length;
	int[] sort=new int[n];
	for(int i=0;i<n;i++)
		sort[i]=i;
	quickSort(S,sort,0,n-1);
	int i=0;
	double w=W,x;
	while(w>0){
		x=Math.min(1,w/S[0][sort[i]]);
		System.out.println((sort[i]+1)+"  "+x);
		w=w-x*S[0][sort[i]];
		i++;
	}
}
	
private static void quickSort(int[][] s, int[] sort,int left,int right) {
	if(left<right){
		int p=partition(s,sort,left,right);
		quickSort(s,sort,left,p-1);
		quickSort(s,sort,p+1,right);
	}
}

private static int partition(int[][] s, int[] sort, int left, int right) {
	int tempIdx=sort[left];
	int temp=s[1][tempIdx]/s[0][tempIdx];
	
	while(left<right){
		while(left<right && s[1][sort[right]]/s[0][sort[right]]<temp) right--;
		sort[left]=sort[right];
		
		while(left<right && s[1][sort[left]]/s[0][sort[left]]>temp) left++;
		sort[right]=sort[left];
	}
	sort[left]=tempIdx;
	return left;
}

缓存维护问题

public static void caching(int[] pages,int cacheCapocity){
	int[] cache=new int[cacheCapocity+1];
	int top=0,rear=0;
	int count=0;
	for(int i=0;i<pages.length;i++){
		if(rear==top || (top+pages.length-rear)%pages.length<cacheCapocity){
			cache[top]=pages[i];
			top=(top+1)%cache.length;
		}if(!exist(pages[i],cache,top,rear)){
			rear=(rear+1)%cache.length;
			cache[top]=pages[i];
			top=(top+1)%cache.length;
			count++;
		}
	}
	System.out.println(count);
}
private static boolean exist(int x, int[] cache,int top,int rear) {
	while(rear!=top){
		if(cache[rear]==x) return true;
		rear=(rear+1)%cache.length;
	}
	return false;
}