算法图解笔记（附PDF下载地址）

编程入门行业动态更新时间:2024-10-26 20:34:48

算法图解笔记

分治策略
散列函数
广度优先搜索
狄克斯特拉算法
动态规划

算法图解（pdf版）链接：https://pan.baidu/s/1FJvija2NNmhOSpd7D3yE_g 提取码：bwcm

分治策略

分治策略（分而治之）是一种解决问题的思路，使用递归实现

工作原理：

找出简单基线条件（递归中的概念，基线条件指函数不再调用自己；递归条件指函数调用自己）
缩小问题规模使接近基线条件（编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。）

代表算法：二分查找，快排

散列函数

散列表适用场景

模拟映射关系
防止重复
数据缓存

注意的点

冲突很糟糕，应使用可以最大限度减少冲突的散列函数（冲突过多会影响数据查找、删除速度；严重时会退化为链表）
一旦填装因子超过0.7，就该调整散列表的长度

广度优先搜索

广度优先是一种用于图的查找算法，一般用来帮助解决两类问题：

有无路径问题（从节点A出发，有到节点B的路径吗？）
最短路径问题（从节点A触发，前往节点B哪条路径最短？）

注意点

对于寻找最短路径的问题，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
有向图中的边为箭头，箭头的方向指定了关系的方向
无向图中的边不带箭头，其中的关系是双向的
你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列
对于检查过的人，务必不要再去检查，否则可能导致无限循环（节点间的相互引用）

狄克斯特拉算法

在介绍迪克斯特拉算法前，先介绍一些基础概念
每条边都有关联数字的图，这些数字称为权重

带权重的图称为加权图，不带权重的图称为非加权图

图中可能有环

狄克斯特拉算法包含4个步骤。

找出“最便宜”的节点，即可在最短时间内到达的节点
对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销
重复这个过程，直到对图中的每个节点都这样做了
计算最终路径

注意点

狄克斯特拉算法只适用于有向无环图
不能将狄克斯特拉算法用于包含负权边的图

小结

广度优先搜索用于在非加权图中查找最短路径。
狄克斯特拉算法用于在加权图中查找最短路径。
仅当权重为正时狄克斯特拉算法才管用。
如果图中包含负权边，请使用贝尔曼福德算法。

算法的Java实现

public class MyDijkstra {

    private static int NOWAY_SIGN = Integer.MAX_VALUE;
    private static String START = "start";
    private static String END = "end";

    public static void main(String[] args) {
        MyDijkstra dijkstra = new MyDijkstra();
        dijkstra.getMinStep();
    }

    private void getMinStep(){
        // 初始化
        Map<String, Map<String, Integer>> grapth = grapthInit();
        Map<String, Integer> costs = costInit();
        Map<String, String> parents = parentInit();
        // 判断是否检查过
        List<String> processed = new ArrayList<>(10);

        // 1. 找到start的最小开销节点
        String node = this.findLowestCostNode(costs,processed);

        // 2. 遍历该节点所有邻居并更新其开销
        while (node != null && grapth.get(node) != null){
            // 获取相邻节点
            Map<String, Integer> xianglinjiedian = grapth.get(node);

            int cost = costs.get(node);

            for (Map.Entry<String, Integer> entry : xianglinjiedian.entrySet()) {
                // 新旧开销的比较，若成功则更新
                int newCost = cost + entry.getValue();
                if(newCost < costs.get(entry.getKey()) || !costs.containsKey(entry.getKey())){
                    costs.put(entry.getKey(),newCost);
                    parents.put(entry.getKey(),node);
                }
            }
            // 加入已处理节点
            processed.add(node);
            // 找出最小开销节点
            node = this.findLowestCostNode(costs,processed);
        }
        System.out.println(parents);
        System.out.println(costs.get(END));
    }

    private String findLowestCostNode(Map<String, Integer> costs,List<String> processed){
        int lowestCost = NOWAY_SIGN;
        String lowNode = null;

        for (Map.Entry<String, Integer> entry : costs.entrySet()) {
            // 未被处理且小于mini
            if(!processed.contains(entry.getKey()) && entry.getValue() < lowestCost){
                lowestCost = entry.getValue();
                lowNode = entry.getKey();
            }
        }

        return lowNode;
    }
    
    private Map<String,String> parentInit() {
        Map<String,String> parentInit = new HashMap<>(16);
        parentInit.put("A",START);
        parentInit.put("B",END);
        parentInit.put(END,null);
        return parentInit;
    }

    private Map<String,Integer> costInit() {
        Map<String,Integer> costsMap = new HashMap<>(16);
        costsMap.put("A",6);
        costsMap.put("B",2);
        costsMap.put(END,Integer.MAX_VALUE);
        return costsMap;
    }

    // 构造有向图
    private Map<String, Map<String,Integer>> grapthInit() {
        Map<String, Map<String,Integer>> grapth = new HashMap<>(16);
        Map<String,Integer> startValue1 = new HashMap<>(2);
        startValue1.put("A",6);
        startValue1.put("B",2);
        grapth.put(START,startValue1);
        Map<String,Integer> startValue2 = new HashMap<>(2);
        startValue2.put(END,1);
        grapth.put("A",startValue2);
        Map<String,Integer> startValue3 = new HashMap<>(2);
        startValue3.put("A",3);
        startValue3.put(END,5);
        grapth.put("B",startValue3);
        grapth.put(END,null);
        return grapth;
    }
}

贪婪算法

动态规划

学习点

学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题
学习如何设计问题的动态规划解决方案

工作原理

先解决子问题，再逐渐解决大问题

课后答案
9.1 假设你还可偷另外一件商品——MP3播放器，它重1磅，价值1000美元。你要偷吗？

不要，因为重1磅的吉他价值1500磅，所有偷Mp3播放器在本题中目前没有意义

9.2 假设你要去野营。你有一个容量为6磅的背包，需要决定该携带下面的哪些东西。其中每样东西都有相应的价值，价值越大意味着越重要：
 水（重3磅，价值10）
 书（重1磅，价值3）
 食物（重2磅，价值9）
 夹克（重2磅，价值5）
 相机（重1磅，价值6）
请问携带哪些东西时价值最高？

	1	2	3	4	5	6
水			10（水）	10（水）	10（水）	10（水）
书	3（书）	3（书）	10（水）	13（水、书）	13（水、书）	13（水、书
食物	3（书）	9（食物）	11（书、食物）	13（水、书）	19（水、食物）	22（水、书、食物）
夹克	3（书）	9（食物）	11（书、食物）	14（食物、夹克）	19（水、食物）	22（水、书、食物）
相机	6（相机）	9（书、相机）	15（食物、相机）	17（书、食物、相机）	20（食物、夹克、相机）	25（水、食物、相机）