利用HashMap,TreeMap实现结构体

通过牛客网的洗礼,小编开始发现其实数据结构描绘的一些结构图,其实也可以利用HashMap,TreeMap来实现我们脑中的虚拟图。通过一个题目一起来感受一下。
题目描述:
利用HashMap,TreeMap实现结构体
看到题目的长度,大家千万别被吓到,其实这道题目实际考察点,只有一个结构的关联建立起来,通过遍历比较大小便可以得出最终结果,而实际的难度在于我们如何构建联系,以及实现题目两个表的结构体。

解题思路:
如果这道题正面解,那么需要考虑以及遍历的次数可能多起来,时间复杂度也会增加,换个解法,既然一定要最后一个H点的参与,我们直接通过最后节点然后逐个返回遍历,尝试。

实例:
利用HashMap,TreeMap实现结构体

结构体的联系其实很简单的:

//这个是输入的二维数组,实际上就是一个多个集合的大集合,构建了图一左边的图
HashMap<Integer, ArrayList<Integer>> parents = new HashMap<>();
		for (int i = 0; i < size; i++) {
			parents.put(i, new ArrayList<Integer>());
		}
		int end = -1;
		for (int i = 0; i < dependents.length; i++) {
			boolean allZero = true;
			for (int j = 0; j < dependents[0].length; j++) {
				if (dependents[i][j] != 0) {
					parents.get(j).add(i);
					allZero = false;
				}
			}
			if (allZero) {
				end = i;
			}
		}

//这个便是从尾节点往前遍历的所有不超过time的最大金钱数
		HashMap<Integer, TreeMap<Integer, Integer>> nodeCostRMap = new HashMap<>();
		for (int i = 0; i < size; i++) {
			nodeCostRMap.put(i, new TreeMap<Integer, Integer>());
		}
		nodeCostRMap.get(end).put(times[end], revenue[end]);

遍历:

LinkedList <Integer> queue = new LinkedList<>();
        queue.add(end);
        while(!queue.isEmpty()) {
        	int cur=queue.poll();
        	for(int last:parents.get(cur)) {
        		for(Entry<Integer,Integer> entry:nodeCostRMap.get(cur).entrySet()) {
        			int lastCost=entry.getKey()+times[last];
        			int lastR=entry.getValue()+revenue[last];
        			TreeMap<Integer, Integer>lastMap=nodeCostRMap.get(last);
        			if(lastMap.floorKey(lastCost)==null||lastMap.floorKey(lastCost)<lastR) {
        				lastMap.put(lastCost, lastR);
        			}
        		}
        		queue.add(last);
        	}
        }
        TreeMap<Integer, Integer> allMap=new TreeMap<>();
        for(TreeMap<Integer, Integer> curMap:nodeCostRMap.values()) {
        	for(Entry<Integer,Integer>entry:curMap.entrySet()) {
        		int cost=entry.getKey();
        		int R=entry.getValue();
        		if(allMap.floorKey(cost)==null||allMap.get(allMap.floorKey(cost))<R) {
        			allMap.put(cost, R);
        		}
        	}
        }

好啦,希望这一个题目对你们对map有一些其他不同的想法,以及用法。

上一篇:Flink sql 之 TopN 与 StreamPhysicalRankRule (源码解析)


下一篇:Map、TreeMap