利用HashMap,TreeMap实现结构体

本文主要是介绍利用HashMap,TreeMap实现结构体，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

通过牛客网的洗礼，小编开始发现其实数据结构描绘的一些结构图，其实也可以利用HashMap,TreeMap来实现我们脑中的虚拟图。通过一个题目一起来感受一下。
题目描述：

看到题目的长度，大家千万别被吓到，其实这道题目实际考察点，只有一个结构的关联建立起来，通过遍历比较大小便可以得出最终结果，而实际的难度在于我们如何构建联系，以及实现题目两个表的结构体。

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

实例：

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

//这个是输入的二维数组，实际上就是一个多个集合的大集合，构建了图一左边的图
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有一些其他不同的想法，以及用法。

这篇关于利用HashMap,TreeMap实现结构体的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！