算法 - 附案例（二分查找 | 分治算法 | 动态规划 | KMP算法 | 贪心算法）_分治算法二分查找自主编程

二分查找模板

l 指针掌管左边蓝色区域， r 指针掌管右边红色区域，两者互不冲突，通过不断向目标元素靠近扩大掌管区域，直到两者掌管区域接壤。

二分查找起始状态：

二分查找终止状态：

＜ 、≤ 、≥ 、＞ 目标元素对应的蓝红区域划分

总结模板：

例子：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //左边界
        int leftIdx = binarySearchLeft(nums, target); 
        //右边界
        int rightIdx = binarySearchRight(nums, target); 
        //判断是否符合
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { 
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }
    
    //找左边界的二分查找
    public int binarySearchLeft(int[] nums, int target) {
        //注意左右指针的初始值
        int left = -1, right = nums.length;
        while (left+1 != right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
     //找右边界的二分查找
    public int binarySearchRight(int[] nums, int target) {
        //注意左右指针的初始值
        int left = -1, right = nums.length;
        while (left+1 != right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

二分查找算法(非递归)

介绍

代码实现：

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

/**
 * @author xdragon
 * @Description 二分查找的非递归实现
 * @createTime 2021年08月12日
 */
public class BinarySearchNoRecur {
    public static void main(String[] args) {
        //测试
        int[] arr = {1,3, 8, 10, 11, 67, 100};
        int index = binarySearch(arr,67);
        System.out.println("index = " + index);
    }

    /**
     * 二分查找的非递归实现
     * @param arr 待查找的数组，按升序排序
     * @param target 需要查找的数
     * @return 返回对应的下标，若不存在则为 -1
     */
    public static int binarySearch(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){//在左边查找
                right = mid - 1;
            }else {//在右边查找
                left = mid + 1;
            }
        }
        return -1; //没有找到就返回-1
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

67查找成功，返回该数的下标5

分治算法

介绍：

---

分治算法的基本步骤

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

1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3. 合并：将各个子问题的解合并为原问题的解。

---

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

汉诺塔游戏的演示和思路分析：
1)如果是有一个盘， A->C

如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘
2) 先把 最上面的盘 A->B
3) 把最下边的盘 A->C
4) 把 B 塔的所有盘 从 B->C

/**
 * @author xdragon
 * @Description 分治算法
 * @createTime 2021年08月12日
 */
public class Hanoitower {
    public static void main(String[] args) {
        //测试
        hanoiTower(3,'A','B','C');
    }

    /**
     * 分治算法 - 汉诺塔的移动的方法
     * @param num 多少个盘
     * @param a 开始
     * @param b 借助中间盘
     * @param c 目的
     */
    public static void hanoiTower(int num, char a, char b, char c){
        //如果只有一个盘，A -> C
        if (num == 1){
            System.out.println("第1个盘从 " + a + " -> " + c);
        }else {
            // 1.先把最上面的所有盘移动到b，其中会借用到c
            hanoiTower(num - 1,a,c,b);
            // 2.把最下面的盘a到c
            System.out.println("第" + num + "个盘从 " + a + " -> " + c);
            //3. 把 B 塔的所有盘 从 b->c , 移动过程使用到 a 塔
            hanoiTower(num - 1,b,a,c);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

动态规划

动态规划算法介绍：

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

---

应用场景

解题思路：

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

则我们有下面的结果：

图解的分析

---

动态规划-背包问题的代码实现

import java.util.Arrays;

/**
 * @author xdragon
 * @Description TODO
 * @createTime 2021年08月13日
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        //各个物品的重量
        int[] weight = {1, 4, 3};
        //各个物品的价值
        int[] value = {1500, 3000, 2000};
        //背包最大的容量
        int maxSize = 4;
        //物品的个数
        int n = value.length;
        //最大价值
        int[][] maxValue = new int[n + 1][maxSize + 1];
        //装入的方式
        int[][] method = new int[n + 1][maxSize + 1];

        //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是 0
        //maxValue.length 获取二维数组的行
        //maxValue[0].length 获取二维数组的列
        for (int i = 0; i < maxValue.length; i++) {
            maxValue[i][0] = 0; //将第一列设置为 0
        }
        for (int i = 0; i < maxValue[0].length; i++) {
            maxValue[0][i] = 0; //将第一行设置 0
        }

        //依次装入背包
        for (int i = 1; i < maxValue.length; i++) {
            for (int j = 1; j < maxValue[0].length; j++) {
                //当准备装入的物品重量 大于 当前背包容量时，就直接使用上一个单元格的装入策略
                if (weight[i - 1] > j) {
                    maxValue[i][j] = maxValue[i - 1][j];
                } else {  //准备装入的物品重量 小于 当前背包容量时
                    //剩下的容量
                    int remainWeight = j - weight[i - 1];
                    //如果放入该物品前的最大价值 大于 放入该物品后的最大价值，就不放入该物品
                    if (maxValue[i - 1][j] > value[i - 1] + maxValue[i - 1][remainWeight]) {
                        maxValue[i][j] = maxValue[i - 1][j];
                    } else { //放入该物品前的最大价值 小于 放入该物品后的最大价值，就记录到 方式 中
                        maxValue[i][j] = value[i - 1] + maxValue[i - 1][remainWeight];
                        //存入到 方式 中
                        method[i][j] = 1;
                    }
                }
            }
        }

        //打印放入背包的最大价值
        for (int[] arr : maxValue) {
            System.out.println(Arrays.toString(arr));
        }

        //打印价值最大的 方式
        //存放 方式 的二维数组的最大下标，从最后开始搜索存放方式
        int i = method.length - 1;
        int j = method[0].length - 1;
        while (i > 0 && j > 0) {
            if (method[i][j] == 1) {
                System.out.println("将第 " + i + " 个物品放入背包中");
                //背包剩余容量
                j -= weight[i - 1];
            }
            i--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

KMP算法

算法应用——字符串匹配

思路及图解

问题：有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

---

先看，暴力匹配实现：

---

算法步骤

首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位

重复第一步，还是不符合，再后移

一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止
接着比较字符串和搜索词的下一个字符，还是符合
遇到 Str1有一个字符与 Str2对应的字符不符合
重要步骤

这时候，想到的是继续遍历 str1的下一个字符，重复第 1步。(其实是很不明智的，因为此时 BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”

KMP 算法的想法是：设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率

怎么做到把刚刚重复的步骤省略掉？可以对 str2计算出一张部分匹配表，这张表的产生在后面介绍

str2的部分匹配表如下

已知空格与 D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的部分匹配值为 2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于 4，所以将搜索词向后移动 4 位

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（”AB”），对应的部分匹配值为0。

所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位

因为空格与 A不匹配，继续后移一位


逐位比较，直到发现 C与 D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了

部分匹配表的生成

前缀与后缀
前缀：ABCD的前缀为[A, AB, ABC]
后缀：ABCD的后缀为[BCD, CD, D]

部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

实现代码：

/**
 * @author xdragon
 * @Description TODO
 * @createTime 2021年08月13日
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        //原字符串
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        //子字符串
        String str2 = "ABCDABD";
        //匹配结果
        int result = getPosition(str1, str2);
        if (result != -1) {
            System.out.print("匹配位置是：str1[" + result + "]");
        } else {
            System.out.println("匹配失败");
        }
    }

    /**
     * 得到匹配字符串的部分匹配表
     *
     * @param matchStr 用于匹配的字符串
     * @return 部分匹配表
     */
    public static int[] getTable(String matchStr) {
        //部分匹配值的数组
        int[] sectionTable = new int[matchStr.length()];
        //匹配字符串的第一个元素没有前缀与后缀，部分匹配值为0
        sectionTable[0] = 0;
        //i用来指向部分匹配字符串末尾的字符，j用来指向开始的字符
        for (int i = 1, j = 0; i < matchStr.length(); i++) {
            //当j>0且前缀后缀不匹配时，使用部分匹配表中前一个表项的值
            while (j > 0 && matchStr.charAt(j) != matchStr.charAt(i)) {
                j = sectionTable[j - 1];
            }

            //如果前缀后缀匹配，j向后移，继续比较
            if (matchStr.charAt(j) == matchStr.charAt(i)) {
                j++;
            }
            //存入匹配值
            sectionTable[i] = j;
        }
        return sectionTable;
    }

    /**
     * 通过KMP算法匹配字符串，若匹配成功，返回第一个字符出现的位置
     *
     * @param str1 用于匹配的字符串
     * @param str2 要匹配的字符串
     * @return 第一个字符出现的位置，没有则返回-1
     */
    public static int getPosition(String str1, String str2) {
        //获得str2的部分匹配表
        int[] sectionTable = getTable(str2);
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //两个字符匹配
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
                if (j == str2.length()) {
                    //如果匹配完成，返回第一个字符出现位置
                    return i - str2.length() + 1;
                }
            } else {
                //如果匹配失败了，使用部分匹配表，跳转到str1对应位置
                //如果j==0，说明没有字符被被匹配，直接让i指向str1的下一个字符
                if (j == 0) {
                    continue;
                }
                //跳转步数 = 已经匹配的字符个数 - 部分匹配表对应的值
                int position = j - sectionTable[j - 1];
                i += position;
                //因为循环后会+1，所以此处i-1
                i--;
                //重置j，重新匹配
                j = 0;
            }
        }
        return -1;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

测试数据：

        //原字符串
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        //子字符串
        String str2 = "ABCDABD";
1
2
3
4

结果：

贪心算法

算法简介

• 贪心算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。
• 贪心算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

算法应用1——集合覆盖：

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

思路

• 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系
• 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
• 重复第 1步直到覆盖了全部的地区

图解

---

遍历电台的覆盖地区，发现K1覆盖的地区最多，将K1覆盖的地区从地区集合中移除。然后将K1放入电台集合中，并更新覆盖地区个数

遍历，发现K2覆盖的地区最多，将K2覆盖的地区从地区集合中移除。然后将K2放入电台集合中，并更新覆盖地区个数

遍历，发现K3覆盖的地区最多，将K3覆盖的地区从地区集合中移除。然后将K3放入电台集合中，并更新覆盖地区个数

遍历，发现K5覆盖的地区最多，将K5覆盖的地区从地区集合中移除。然后将K5放入电台集合中，并更新覆盖地区个数。所有区域都被覆盖，算法结束

Java代码实现：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

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

---

算法应用2——钱币找零

假设纸币金额为1元、5元、10元、20元、50元、100元

要凑成123元应该尽可能兑换少的纸币

算法思路

• 尽可能从大面值一直往下减即可

Java实现代码：

package com.ai.myproject.atguigu;

/**
 * @author xdragon
 * @Description 贪心算法 | 钱币找零
 * @createTime 2021年08月13日
 */
public class GreedyAlgorithm2 {
    public static void main(String[] args) {
        splitChange(123);
    }

    /**
     * 拆分零钱
     *
     * @param money 钱币总金额
     */
    public static void splitChange(int money) {
        //零钱金额，纸币的种类
        int[] prices = {100, 50, 20, 10, 5, 1};
        //用于记录每种纸币的数量，下标与prices数组的下标对应
        int[] counts = new int[prices.length];
        //剩下的金额
        int surplus = money;
        if (money > 0) {
            //如果剩下的金额大于0
            while (surplus > 0) {
                //从大金额向小金额进行凑数
                for (int i = 0; i < prices.length; i++) {
                    //每张钱币的数量
                    int count = 0;
                    //如果该金额的钱币小于总金额，该钱币数量+1
                    while (surplus - prices[i] >= 0) {
                        count++;  //该钱币数量+1
                        surplus -= prices[i]; //剩下的金额
                    }
                    counts[i] = count;
                }
            }
        }

        //打印结果
        System.out.println("凑成" + money + "元");
        for (int i = 0; i < prices.length; i++) {
            if (counts[i] != 0) {
                System.out.println("需要" + prices[i] + "元的纸币" + counts[i] + "张");
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51