通过牛客网的洗礼,小编开始发现其实数据结构描绘的一些结构图,其实也可以利用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有一些其他不同的想法,以及用法。