数据结构和算法(程序员常用的十种算法:上1~5)

一:二分查找

二分查找算法(非递归)介绍

(1)前面我们讲过了二分查找算法,是使用递归的方式,下面我们讲解二分查找算法的非递归方法

(2)二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找

(3)二分查找法的运行时间为对数时间O(log2n),即查找到需要的目标位置最多只需要log2n步,假设从[0~99]的队列(100个数,即n=100)中寻找目标数30,则需要查找步数为log2100,即最多需要查找7次(2^6<100<2^7)

二分查找算法(非递归)代码实现

   需求: 数组{1,3,8,10,11,67,100},编程实现二分查找,要求使用非递归的方法完成

1.  
   package binarySearchNoRecur;
2.  
    
3.  
   /**
4.  
   * 二分查找非递归
5.  
   */
6.  
   public class BinarySearchNoRecur {
7.  
   public static void main(String[] args) {
8.  
   //测试
9.  
   int [] arr ={1,3,8,10,11,67,100};
10.  
    int index = binarySearch(arr,-8);
11.  
    System.out.println("index=" index);
12.  
    }
13.  
     
14.  
    /**
15.  
    * 二分查找非递归实现
16.  
    * @param arr 待查找的数组
17.  
    * @param target 需要查找的数
18.  
    * @return 返回查找到数的下标 -1表示没有找到
19.  
    */
20.  
    public static int binarySearch(int[] arr ,int target){
21.  
     
22.  
    int left = 0; //起始
23.  
    int right = arr.length -1; //结束
24.  
    while(left <= right){ //说明继续查找
25.  
    int mid = (left right) / 2;
26.  
    if (arr[mid] == target){
27.  
    return mid;
28.  
    }else if ( arr[mid] > target){
29.  
    right = mid -1; //需要向左边查找
30.  
    }else {
31.  
    left = mid 1; //需要向右边查找
32.  
    }
33.  
    }
34.  
    return -1;
35.  
    }
36.  
    }

二:分治算法

分治算法介绍

(1)分治法是一种很重要的算法.字面上的解释是"分而治之",就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题...直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并.这个技巧是很多高效算法的基础.入排序算法(快速排序,归并排序),傅里叶变换....

(2)分治算法可以求解的一些经典问题

二分搜索

大整数乘法

棋牌覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循坏赛日程表

汉诺塔

分治算法的基本步骤

分治法在每一层递归上都有三个步骤:

(1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题

(2)解决:若子问题规模较小而容易被解决掉则直接解,否则递归的解各个子问题

(3)合并:将各个子问题的解合并为原问题的解.

分治算法设计模式如下:

 其中|P|表示问题P的规模;n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2.yk)是该分治法中的合并子算法，用于将P的子问题P1,P2 ..Pk的相应的解y1,y2,..,yk合并为P的解。
 

分治算法的最佳实践-汉诺塔

>汉诺塔的传说
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟一次，共需多长时间呢?移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

汉诺塔游戏思路分析

(1)如果有一个盘, A->C

如果我们有n>=2情况,我们总是可以看做是两个盘1.最下面的盘,2上面的盘

(1)先把最上面的盘A->B

(2)把最下面的盘A->C

(3)把B塔的所有盘从B->C

代码实现:

1.  
   package dac;
2.  
    
3.  
   /**
4.  
   * 分治算法---汉诺塔问题
5.  
   */
6.  
   public class hannuota {
7.  
   public static void main(String[] args) {
8.  
   hanoiTower(5,'A','B','C');
9.  
    
10.  
    }
11.  
     
12.  
    //汉诺塔的移动方法
13.  
    //使用分治算法
14.  
    public static void hanoiTower(int num, char a, char b, char c){
15.  
    //如果只有一个盘
16.  
    if (num == 1){
17.  
    System.out.println("第1个盘从" a "->" c);
18.  
    }else {
19.  
    //如果我们有n >= 2情况,我们总是可以看做是两个盘 1.最下边的一个盘 2.上面的所有盘
20.  
    //1.先把最上面的所有盘A->B ,移动过程中会使用到c
21.  
    hanoiTower(num -1, a, c, b);
22.  
    //2.把最下边的盘A-C
23.  
    System.out.println("第" num "个盘从" a "->" c );
24.  
    //3.把B塔的所有盘从B->C,移动过程使用到a
25.  
    hanoiTower(num -1, b, a, c);
26.  
    }
27.  
    }
28.  
    }

三.动态规划算法

应用场景-背包问题

背包问题,有一个背包,容量为4磅,现有如下物品

(1)要求达到的目标为装入背包的总价值最大,并且重量不超出

(2)要求装入的物品不能重复

动态规划算法介绍

(1)动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
(2)动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
(3)与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)
(4)动态规划可以通过填表的方式来逐步推进，得到最优解.
 

动态规格算法最佳实践-背包问题

思路分析和图解

(3)背包问题只要是指一个给定容量的背包,若干具有一定价值和重量的物品,如何选择物品放入背包使用物品的价值最大.其中又分01背包和完全背包(完全背包是指每种物品都有无限件可用)

(4)这里的问题属于01背包,即每个物品最多放一个,而无限背包可以转化为01背包.

(5)算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来
确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[]、w[i]分别为第i个物品的价值和重量，c为背包的容量。再令v[i][i]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果:

图解

代码实现

1.  
   package dynamic;
2.  
    
3.  
   /**
4.  
   * 动态规划--背包问题
5.  
   */
6.  
   public class KnapsackProblem {
7.  
   public static void main(String[] args) {
8.  
   int[] w = {1, 4, 3};//物品的重量
9.  
   int[] val = {1500, 3000, 2000}; //物品的价值
10.  
    int m = 4; //背包的容量
11.  
    int n = val.length; //物品的个数
12.  
     
13.  
     
14.  
    //创建二维数组
15.  
    //v[i][j] 表示在前i个物品中能装入容量为j的背包中的最大价值
16.  
    int[][] v = new int[n 1][m 1];
17.  
    //为了记录放入商品的情况,我们定一个二维数组
18.  
    int[][] path = new int[n 1][m 1];
19.  
     
20.  
    //初始化第一行和第一列,这里在本程序中 可以不去处理 默认为0
21.  
    for (int i = 0; i < v.length; i ) {
22.  
    v[i][0] = 0; //将第一列设置为0
23.  
    }
24.  
    for (int i = 0; i < v[0].length; i ) {
25.  
    v[0][i] = 0;//将第一行设置为0
26.  
    }
27.  
     
28.  
     
29.  
    //根据前面得到的公式来动态规划处理
30.  
    for (int i = 1; i < v.length; i ) { //不处理第一行
31.  
    for (int j = 1; j < v[0].length; j ) { //不处理第一列
32.  
    //公式
33.  
    if (w[i - 1] > j) { //因为我们程序i是从1开始的,因此原来公式中的w[i]修改成w[i-1]
34.  
    v[i][j] = v[i - 1][j];
35.  
    } else {
36.  
    //说明
37.  
    //因为我们的i是从1开始的,因此公式需要调整成下面这样
38.  
    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] v[i - 1][j - w[i - 1]]);
39.  
    //为了记录商品存放到背包的情况,我们不能直接使用公式,需要使用if-else来体现公式
40.  
    if (v[i - 1][j] < val[i - 1] v[i - 1][j - w[i - 1]]) {
41.  
    v[i][j] = val[i - 1] v[i - 1][j - w[i - 1]];
42.  
    //把当前情况积累到path
43.  
    path[i][j] = 1;
44.  
    } else {
45.  
    v[i][j] = v[i - 1][j];
46.  
    }
47.  
    }
48.  
    }
49.  
    }
50.  
     
51.  
     
52.  
    //输出一下v看目前的情况
53.  
    for (int i = 0; i < v.length; i ) {
54.  
    for (int j = 0; j < v[i].length; j ) {
55.  
    System.out.print(v[i][j] " ");
56.  
    }
57.  
    System.out.println();
58.  
    }
59.  
    //输出最后我们放入的是那些商品
60.  
    //遍历path
61.  
    // for (int i = 0 ;i <path.length; i ){
62.  
    // for (int j=0 ;j<path[i].length; j ){
63.  
    // if(path[i][j]==1){
64.  
    // System.out.println("第%d个商品放入到背包\n" i);
65.  
    // }
66.  
    // }
67.  
    // }
68.  
     
69.  
    //最终结果
70.  
    int i = path.length - 1; //行的最大下标
71.  
    int j = path[0].length - 1;//列的最大下标
72.  
    while (i > 0 && j > 0) {
73.  
    if (path[i][j] == 1) {
74.  
    System.out.printf("第%d个商品放入到背包\n", i);
75.  
    j -= w[i - 1];
76.  
    }
77.  
    i--;
78.  
    }
79.  
     
80.  
    }
81.  
    }

四:KMP算法

应用场景-字符串匹配问题

字符串匹配问题:
(1)有一个字符串 str1="硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好"，和一个子串 str2="尚硅谷你尚硅你"
(2)现在要判断str1是否含有str2,如果存在，就返回第一次出现的位置,如果没有，
则返回-1
 

暴力匹配算法

如果用暴力匹配的思路，并假设现在str1匹配到i位置，子串str2匹配到j位置，则有:
(1)如果当前字符匹配成功(即str1[i]== str2[li])，则i ，j ，继续匹配下一个字符
(2)如果失配（即str1[i]! = str2[li])，令i=i-(j- 1)，j=0。相当于每次匹配失败时，i回溯，j被置为0。
(3)用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)
(4)暴力匹配算法实现.

代码实现
 

1.  
   package kmp;
2.  
    
3.  
   /**
4.  
   * 暴力匹配
5.  
   */
6.  
   public class ViolenceMatch {
7.  
    
8.  
   public static void main(String[] args) {
9.  
   //测试暴力匹配算法
10.  
    String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
11.  
    String str2 = "尚硅谷你尚硅你";
12.  
    int index = violenceMatch(str1, str2);
13.  
    System.out.println("index=" index);
14.  
    }
15.  
     
16.  
    //暴力匹配算法实现
17.  
    public static int violenceMatch(String str1, String str2) {
18.  
    char[] s1 = str1.toCharArray();
19.  
    char[] s2 = str2.toCharArray();
20.  
     
21.  
    int s1Len = s1.length;
22.  
    int s2Len = s2.length;
23.  
     
24.  
    int i = 0; //i索引指向s1
25.  
    int j = 0; //j索引指向s2
26.  
    while (i < s1Len && j < s2Len) { //保证匹配时,不越界
27.  
     
28.  
    if (s1[i] == s2[j]) { //匹配成功
29.  
    i ;
30.  
    j ;
31.  
    } else { //没有匹配成功
32.  
    i = i - (j - 1);
33.  
    j = 0;
34.  
    }
35.  
    }
36.  
    //判断是否匹配成功
37.  
    if (j == s2Len) {
38.  
    return i - j;
39.  
    } else {
40.  
    return -1;
41.  
    }
42.  
    }
43.  
    }

KMP算法介绍

(1) KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
(2) Knuth-Morris-Pratt字符串查找算法，简称为KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法Dopald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.
(3) KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
(4)参考资料: https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
 

KMP算法最佳应用-字符串匹配问题

>字符串匹配问题:
(1)有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串str2="ABCDABD"
(2)现在要判断str1是否含有str2,如果存在，就返回第一次出现的位置,如果没有,中―则返回-1
(3)要求:使用KMP算法完成判断，不能使用简单的暴力匹配算法.

代码实现

1.  
   package kmp;
2.  
    
3.  
   import java.util.Arrays;
4.  
    
5.  
   /**
6.  
   * KMP算法
7.  
   */
8.  
   public class KMPAlgorithm {
9.  
    
10.  
    public static void main(String[] args) {
11.  
     
12.  
    String str1 = "BBC ABCDAB ABCDABCDABDE";
13.  
    String str2 = "ABCDABD";
14.  
    //String str2 = "BBC";
15.  
     
16.  
    int[] next = kmpNext("ABCDABD");
17.  
    System.out.println("next=" Arrays.toString(next));
18.  
     
19.  
    int index = kmpSearch(str1, str2, next);
20.  
    System.out.println("index" index);
21.  
    }
22.  
     
23.  
     
24.  
    /**
25.  
    * 写出我们的kmp搜索算法
26.  
    *
27.  
    * @param str1 源字符串
28.  
    * @param str2 要搜索的字符串
29.  
    * @param next 部分匹配表,是字串对应的部分匹配吧
30.  
    * @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
31.  
    */
32.  
    public static int kmpSearch(String str1, String str2, int[] next) {
33.  
    //遍历
34.  
    for (int i = 0, j = 0; i < str1.length(); i ) {
35.  
     
36.  
    //需要处理str1.charAt(i)!= str2.charAt(j),去调整j的大小
37.  
    //KMP算法核心点
38.  
    while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
39.  
    j = next[j - 1];
40.  
    }
41.  
    if (str1.charAt(i) == str2.charAt(j)) {
42.  
    j ;
43.  
    }
44.  
    if (j == str2.length()) {
45.  
    //找到了
46.  
    return i - j 1;
47.  
    }
48.  
    }
49.  
    return -1;
50.  
     
51.  
    }
52.  
     
53.  
    //获取到一个字符串(字串) 的部分匹配值表
54.  
    public static int[] kmpNext(String dest) {
55.  
    //创建一个next数组保存部分匹配值
56.  
    int[] next = new int[dest.length()];
57.  
    next[0] = 0; //如果字符串长度为1部分匹配值就是0
58.  
    for (int i = 1, j = 0; i < dest.length(); i ) {
59.  
    //当dest.charAt(i)!=dest.charAt(j),我们需要从next[j-1]获取新的j
60.  
    //直到我们发现有当dest.charAt(i)==dest.charAt(j)成立才退出
61.  
    //这是kmp算法的核心点
62.  
    while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
63.  
    j = next[j - 1];
64.  
     
65.  
    }
66.  
    //当dest.charAt(i)==dest.charAt(j)满足时,部分匹配值就是 1
67.  
    if (dest.charAt(i) == dest.charAt(j)) {
68.  
    j ;
69.  
    }
70.  
    next[i] = j;
71.  
    }
72.  
    return next;
73.  
     
74.  
    }
75.  
    }

五:贪心算法

应用场景-集合覆盖问题

假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区.如何选择最少的广播台,让所有地区都可以接收到信号

 贪心算法介绍

(1)贪婪算法(贪心算法)是指对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法

(2)贪婪算法所得到的结果不一定是最优结果(有时侯会是最优解),但是都相对近似(接近)最优的结果

贪心算法最佳应用-集合覆盖

思路分析:
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2-1个,假设每秒可以计算10个子集，如图:

思路分析:
>使用贪婪算法，效率高:
目前并没有算法可以快速计算得到准备的值，使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
(1)遍历所有的广播电台,找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系)
(2)将这个电台加入到一个集合中(比如ArrayList),想办法把该电台覆盖的地区在下次比较时去掉。
(3)重复第1步直到覆盖了全部的地区

分析图解

代码实现:

1.  
   package greedy;
2.  
    
3.  
   import java.util.ArrayList;
4.  
   import java.util.HashMap;
5.  
   import java.util.HashSet;
6.  
    
7.  
   public class GreedyAlgorithm {
8.  
   public static void main(String[] args) {
9.  
   //创建广播电台,放入Map中管理
10.  
    HashMap<String, HashSet> broadcats = new HashMap<String, HashSet>();
11.  
    //将各个电台放入broadcasts
12.  
    HashSet<String> hashSet1 = new HashSet<>();
13.  
    hashSet1.add("北京");
14.  
    hashSet1.add("上海");
15.  
    hashSet1.add("天津");
16.  
     
17.  
    HashSet<String> hashSet2 = new HashSet<>();
18.  
    hashSet2.add("广州");
19.  
    hashSet2.add("北京");
20.  
    hashSet2.add("深圳");
21.  
     
22.  
     
23.  
    HashSet<String> hashSet3 = new HashSet<>();
24.  
    hashSet3.add("成都");
25.  
    hashSet3.add("上海");
26.  
    hashSet3.add("杭州");
27.  
     
28.  
    HashSet<String> hashSet4 = new HashSet<>();
29.  
    hashSet4.add("上海");
30.  
    hashSet4.add("天津");
31.  
     
32.  
    HashSet<String> hashSet5 = new HashSet<>();
33.  
    hashSet5.add("杭州");
34.  
    hashSet5.add("大连");
35.  
     
36.  
    //加入到map
37.  
    broadcats.put("K1", hashSet1);
38.  
    broadcats.put("K2", hashSet2);
39.  
    broadcats.put("K3", hashSet3);
40.  
    broadcats.put("K4", hashSet4);
41.  
    broadcats.put("K5", hashSet5);
42.  
     
43.  
    //allAreas 存放所有所有的地区
44.  
    HashSet<String> allAreas = new HashSet<>();
45.  
    allAreas.add("北京");
46.  
    allAreas.add("上海");
47.  
    allAreas.add("天津");
48.  
    allAreas.add("广州");
49.  
    allAreas.add("深圳");
50.  
    allAreas.add("成都");
51.  
    allAreas.add("杭州");
52.  
    allAreas.add("大连");
53.  
     
54.  
    //创建ArrayList,存放选择的电台集合
55.  
    ArrayList<String> selects = new ArrayList<>();
56.  
     
57.  
    //定义一个临时的集合,在遍历过程中,存放遍历过程中的电台覆盖地区和没有覆盖地区的交集
58.  
    HashSet<String> tempSet = new HashSet<>();
59.  
     
60.  
    //定义maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖的地区对应的电台key
61.  
    String maxKey = null;
62.  
    //如果maxKye 不为null,则会加入到selects
63.  
    while (allAreas.size() != 0) { //如果allAreas不为0,则表示还没有覆盖到所有的地区
64.  
    //每进行一次while需要
65.  
    maxKey = null;
66.  
     
67.  
    //遍历broadcasts,取出key
68.  
    for (String key : broadcats.keySet()) {
69.  
    //每进行一次for
70.  
    tempSet.clear();
71.  
    //当前这个key能够覆盖的地区
72.  
    HashSet<String> areas = broadcats.get(key);
73.  
    tempSet.addAll(areas);
74.  
    //求出tempSet和allAreas集合的交集,交集会赋给tempSet
75.  
    tempSet.retainAll(allAreas);
76.  
    //如果当前这个集合包含的未覆盖地区的数量,比maxKey指向的集合地区还多
77.  
    //就需要重置maxKey
78.  
    //体现出贪婪算法的特性
79.  
    if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcats.get(maxKey).size())) {
80.  
    maxKey = key;
81.  
    }
82.  
    }
83.  
    //maxKey != null ,就应将maxKey加入selects
84.  
    if (maxKey != null) {
85.  
    selects.add(maxKey);
86.  
    //将maKey指向的广播电台覆盖的地区,从allAreas去掉
87.  
    allAreas.removeAll(broadcats.get(maxKey));
88.  
    }
89.  
     
90.  
    }
91.  
    System.out.println("得到的选择结果是" selects);//k1 k2 k3 k5
92.  
    }
93.  
    }

贪心算法注意事项和细节

(1)贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
(2)比如上题的算法选出的是K1,K2,K3, K5，符合覆盖了全部的地区
(3)但是我们发现K2,K3,K4,K5也可以覆盖全部地区，如果K2的使用成本低于K1,那
么我们上题的K1,K2,K3,K5虽然是满足条件，但是并不是最优的.
 

这篇好文章是转载于：学新通技术网