前言

算法打卡第10天，今天抽到了中等算法，主要考察贪心算法。秉着独立思考的学习习惯以及分析问题转换问题的思想。硬是自己实现了贪心算法。
这里面只是算法思想值得借鉴，但是代码值得考虑。

一、问题

1、分析问题

分析问题
输入一个二维矩阵，包含源节点到目的节点以源到目的节点所需时间。给定总结点数以及第一次出发节点。
寻找到n个节点，则返回时间，若寻找完都未达到n个，则返回-1。

2、转换问题

转换问题
用Map将二维矩阵存入，通过循环从第一个节点开始贪心算法。
最终返回寻找到的节点数以及以第一个节点为root的高度（maxtime）

3、写代码之前

public static int networkDelayTime(int[][] times, int n, int k) {/** 分析问题 * 输入一个二维矩阵，包含源节点到目的节点以源到目的节点所需时间。给定总结点数以及第一次出发节点。* 寻找到n个节点，则返回时间，若寻找完都未达到n个，则返回-1。 * 转换问题* 用Map将二维矩阵存入，通过循环从第一个节点开始贪心算法。* 最终返回寻找到的节点数以及以第一个节点为root的高度（maxtime）*///1. 申请 map，再将所有节点存入//2. 贪心找最小解。//3. 判断寻找个数来返回“树高度”还是-1.

4、写代码之后

public static int networkDelayTime(int[][] times, int n, int k) {/** 分析问题 * 输入一个二维矩阵，包含源节点到目的节点以源到目的节点所需时间。给定总结点数以及第一次出发节点。* 寻找到n个节点，则返回时间，若寻找完都未达到n个，则返回-1。 * 转换问题* 用Map将二维矩阵存入，通过循环从第一个节点开始贪心算法。* 最终返回寻找到的节点数以及以第一个节点为root的高度（maxtime）*/// 1. 申请 map，再将所有节点存入Map<Integer, List<Map.Entry<Integer, Integer>>> map = new HashMap<>();Map<Integer, Integer> isV = new HashMap<>();for (int i = 0; i < times.length; i++) {isV.computeIfAbsent(times[i][0], val -> new Integer(-1));isV.computeIfAbsent(times[i][1], val -> new Integer(-1));Map<Integer, Integer> map2 = new HashMap<>();final int j = i;map2.computeIfAbsent(times[i][1], val -> new Integer(times[j][2]));map.computeIfAbsent(times[i][0], val -> new ArrayList<>()).add(new ArrayList<>(map2.entrySet()).get(0));}//2.贪心找最小解。List<Integer> q = new ArrayList<>();q.add(k);isV.put(k, 0);int maxtime = 0;while (true) {if (q.size() == n)break;boolean flag = false;List<Map.Entry<Integer, Integer>> mtime = new ArrayList<>();for (Integer integer : q) {if (map.get(integer) != null) {List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.get(integer));for (Map.Entry<Integer, Integer> entry : list) {if (isV.get(entry.getKey()).equals(-1)) {flag = flag || true;Map<Integer, Integer> tMap = new HashMap<>();tMap.put(entry.getKey(), entry.getValue() + isV.get(integer));mtime.add(new ArrayList<>(tMap.entrySet()).get(0));}}}}if (mtime.size() != 0) {mtime.sort((o1, o2) -> o1.getValue().compareTo(o2.getValue()));int key = mtime.get(0).getKey(), value = mtime.get(0).getValue();q.add(key);isV.put(key, value);maxtime = maxtime > value ? maxtime : value;}if (!flag)break;}// 3. 判断寻找个数来返回“树高度”还是-1.return q.size() == n ? maxtime : -1;}

二、算法评估

1、时间复杂度

O(n² * maxlength)，n代表节点数，maxlength代表节点的最大出度。若maxlength远小于n，则时间复杂度为O(n²)。

2、空间复杂度

O(length)，length为times.length。

三、收获

1. 运行时间463ms
   这个时间导致运行时间超过限制。仅仅把重复用了四次的ArrayList<Map.Entry<Integer,Integer>>用了变量key和value来表示，在for循环的包装下，运行时间就降到了69ms,这样就让我通过了。

int key = mtime.get(0).getKey(), value = mtime.get(0).getValue();

2. computeIfAbsent(k,val->function)
   顾名思义，当缺value时才启动第二个function。
   总结出来这个方法的适用情况
   a)适用与Map的Value是Arraylist这种需要去添加更多元素的使用。

map.computeIfAbsent(times[i][0], val -> new ArrayList<>()).add(new ArrayList<>(map2.entrySet()).get(0));

b)适用不想添加重复元素，也就是不改变已有Key对应的value。

isV.computeIfAbsent(times[i][0], val -> new Integer(-1));
isV.computeIfAbsent(times[i][1], val -> new Integer(-1));

c)这是它的优点也会变成它的缺点，当你想改变已有的value时，用这个函数就不会做任何事情。就跟putifabsent()函数一个道理
d)当你没有a和b的特殊要求后，建议直接用put(key,value)。
3. 如何得到MapEntry有相同的key不同的value？

List<Map.Entry<Integer, Integer>> mtime = new ArrayList<>();
Map<Integer, Integer> tMap = new HashMap<>();
tMap.put(entry.getKey(), entry.getValue() + isV.get(integer));
mtime.add(new ArrayList<>(tMap.entrySet()).get(0));

4. 贪心思路
   给定一个起始节点，将其加入List，寻找下一个最短路径，将目标节点加入List，更新目标节点的初始路径数，也就是root到它的距离。再根据List中的数寻找最短路径，如此重复。直到达到最终节点或者访问完所有节点。