十大算法

文章目录

十大算法

二分查找算法

//递归方式实现
public static void doubleBreakSearch(int[] arr,int target,int start,int end){
   
        if(start<=end){
   
            int mid = (start+end)/2;
            int arr[mid];
            if (target<arr[mid]){
   
                doubleBreakSearch(arr,target,start,mid);
            }else if (target>arr[mid]){
   
                doubleBreakSearch(arr,target,mid+1,end);
            }else {
   
                System.out.println(target);
                return ;
            }
        }

     }
//非递归方式实现
    private static int doubleBreakSearch2(int[] arr,int target){
   
        int left = 0;
        int right = arr.length -1;
        while (left<right){
   
            int mid = (left+right)/2;
            if(arr[mid]==target){
   
                return mid;
            }else if (arr[mid]<target){
   
                left=mid+1;
            }else{
   
                right=mid-1;
            }
        }
        return -1;
    }

分治算法

public static void hanoiTower(int num,char a,char b,char c){
   
		//如果只有一个盘就移动到c
        if (num==1){
   
            System.out.println("第一个盘从"+a+"->"+c);
        }else {
   
        //第二步把除了最底下的上面所有盘移动到b
            hanoiTower(num-1,a,c,b);
            System.out.println("第"+num+"个盘从"+a+"->"+c);
        //最后一步把b的所有盘移动到c
            hanoiTower(num-1,b,a,c);
        }
    }

动态规划

得出公式

/**
	 * 0-1背包问题
	 * @param V	背包容量
	 * @param N	物品种类
	 * @param weight 物品重量
	 * @param value	物品价值
	 * @return
	 */
	public static String ZeroOnePack(int V,int N,int[] weight,int[] value){
   
		
		//初始化动态规划数组
		int[][] dp = new int[N+1][V+1];
		//为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
		for(int i=1;i<N+1;i++){
   
			for(int j=1;j<V+1;j++){
   
				//如果第i件物品的重量大于背包容量j,则不装入背包
				//由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
				if(weight[i-1] > j)
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
			}
		}
		//则容量为V的背包能够装入物品的最大值为
		int maxValue = dp[N][V];
		//逆推找出装入背包的所有商品的编号
		int j=V;
		String numStr="";
		for(int i=N;i>0;i--){
   
			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
			if(dp[i][j]>dp[i-1][j]){
   
				numStr = i+" "+numStr;
				j=j-weight[i-1];
			}
			if(j==0)
				break;
		}
		return numStr;	
	}

KMP算法

public class Kmp {
   
    public static void main(String[] args) {
   
        String s1 = "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        System.out.println(kmpSearch(s1, s2, kmpNext(s2)));
    }

    public static int kmpSearch(String s1, String s2, int[] next) {
   
        for (int i = 0, j = 0; i < s1.length(); i++) {
   
            while (j > 0 && s1.charAt(i) != s2.charAt(j)) {
   
                j = next[j - 1];
            }
            if (s1.charAt(i) == s2.charAt(j)) {
   
                j++;
            }
            //返回相遇点
            if (j == s2.length()) {
   
                return i - j + 1;
            }
        }
        return -1;
    }

    //创建一个next表,部分匹配值表
    public static int[] kmpNext(String dest) {
   
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {
   
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
   
                j = next[j - 1];
            }
            if (dest.charAt(i) == dest.charAt(j)) {
   
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

贪心算法

普里姆算法

public class Prim {
   

    /**
     *
     * @param graph 表示图
     * @param v 表示data的下标
     */
    public void prim(Graph graph, int v) {
   
        int[] visited = new int[graph.verxs];
        visited[v]=1;
        int h1=-1;
        int h2=-1;
        //这里表示不可联通的意思
        int minWeight=10000;
        //遍历所有的边
        for (int k = 1 ;k < graph.verxs;k++){
   
            for (int i = 0;i<graph.verxs;i++){
   
                for (int j = 0 ; j<graph.verxs;j++){
   
                    if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
   
                        minWeight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            //找到一条边了
            System.out.println(graph.data[h1]+"->"+graph.data[h2]);
            visited[h2]=1;
            minWeight=10000;
        }
    }
}


class Graph {
   
    int verxs;//节点个数
    int[] data;//节点数据
    int[][] weight;//边，值表示权值

    public Graph(int verxs, int[] data, int[][] weight) {
   
        this.verxs = verxs;
        this.data = data;
        this.weight = weight;
    }
}