java – “寻找共同祖先”的变体
我最近接受了电话采访.它将问题编码作为整个过程的一部分.
问题是找到一棵树最近的共同祖先但有一个扭曲的变化.树很像图形,即可以连接子节点.例: A / B | C E | | D F / G 在这种情况下,给定这个树和节点F和D,得到的最接近的共同的祖先将是B.第二个扭曲是树被呈现为数组.实现方法有以下输入: public String getCA(String[] nodes,String[][] parentNodes,String targetNode2) { if(nodes == null || parentNodes == null){ throw new IllegalArgumentException(); } Map<String,String[]> map = new HashMap<String,String[]>(); for(int i = 0; i < nodes.length; i++){ map.put(nodes[i],parentNodes[i]); } //These are the parents visited as we go up Set<String> parentsSeen = new HashSet<String>(); parentsSeen.add(targetNode1); Queue<String> path = new LinkedList<String>(); String[] parents = map.get(targetNode1); //The root is the common parent if(parents == null){ return targetNode1; } //Build the path up for(String parent:parents){ path.add(parent); } while(!path.isEmpty()){ String currentParent = path.remove(); parentsSeen.add(currentParent); parents = map.get(currentParent); if(parents == null){ continue; } for(String parent:parents){ path.add(parent); } } parents = map.get(targetNode2); //It is the root,so it is the common parent if(parents == null){ return targetNode2; } //Start going up for the targetNode2. The first parent that we have already visited is the common parent for(String parent:parents){ if(parentsSeen.contains(parent)){ return parent; } path.add(parent); } while(!path.isEmpty()){ String currentParent = path.remove(); if(parentsSeen.contains(currentParent)){ return currentParent; } parents = map.get(currentParent); if(parents == null){ continue; } for(String parent:parents){ path.add(parent); } } return null; } 我没有得到前进的电话.现在由于我“自学成才”,我有兴趣了解我是如何搞砸到这里的.由于这是技术问题,我认为这不是主观问题,希望我能从经验丰??富的人那里得到帮助. 解决方法
我甚至不清楚“最接近”是什么意思.请考虑以下图表:
I / / / H E | /| | / | G / D | / | | / F C |/ | A B 这里有2个共同的祖先A和B,H和E. H是A和B的距离2.E是距离A的距离1但距离B的距离是3.我选择哪个? 此外,无论你对这个问题的答案是什么,从一个人那里找到一组祖先,然后从另一个人那里做一个BFS也行不通.找到A的所有祖先然后从B做BFS首先找到H,找到B的所有祖先然后从A做BFS首先找到E.作为对手,我可以切换A和B,使你的算法失败,无论你做出什么选择(选择2/2还是1/3更好). 因此,正确的算法必须比祖先集计算加上BFS更复杂.除非你告诉我如何做出这个选择,否则我不确定我是否可以确定正确的算法. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |