- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我最近接受了一次电话采访。它涉及将问题编码作为过程的一部分。
问题是 Find the most closest common ancestor of a tree
的变体,但有一个扭曲。这棵树很像图,即可以连接子节点。示例:
A
/
B
| \
C E
| |
D F
\ /
G
在这种情况下,给定这棵树和节点 F
和 D
,得到的最接近的共同答案将是 B
。第二个转折点是树以数组的形式呈现。实现方法具有以下输入:public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2)
在这个例子中 nodes
= {"G", "F", "E", "D", "C", "B", "A"}
和 parentNodes
= {{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, 空
本质上,对于 nodes[i]
,parent(s) 是 parentNodes[i]
。
老实说,我完全 panic (已经很紧张了),花了我真的很长时间才找到答案。
虽然我认为这是递归解决的,但我以某种方式提出了一个迭代解决方案,据我所知,它是有效的:我将节点插入队列并首先沿着路径向上移动到第一个目标节点,然后是第二个节点。一旦我找到一个已经遇到的节点,我就将其视为解决方案(已添加注释以清除问题)。
public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, 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 更复杂。除非你告诉我如何做出选择,否则我不确定我能否确定正确的算法。
关于java - "Find common ancestor"的变体,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12148687/
我正在创建一个连接到 firebase 的应用程序。但我面临一些问题。当同步我的 gradle 文件时,我收到此警告 WARNING: API 'variant.getMergeResources()
想知道是否有任何方法可以将变体分配给自定义 radio 输入?我想为 2 天、3 天和标准运输设置不同费率的分级运输。我可以使用变体来做到这一点,但下拉菜单对我不起作用。我想要日期信息和日期选择器,以
我是 Haskell 的新手。鉴于 Haskell 的整个前提是函数将始终返回相同的值,我希望有某种方式,例如在编译时计算常量的斐波那契值,就像我可以在 C++ 中使用模板元编程一样,但我不知道该怎么
我是 OCaml 的新手,但过去两天一直在工作,以便更好地了解如何使用它。我最近做了很多事情,但有些事情阻碍了我前进。 我正在尝试在 OCaml 中实现 evaexpr。使用这种语言非常容易,你会说:
我有一个使用一些typedef的std::variant的代码库。 最初,它们是不同的类型,但现在它们像下面的示例一样重叠 typedef int TA; typedef int TB; std::v
鉴于此: data Foo = Bar { name :: String } | Baz { nickname :: String } 函数 name 和 nickname 似乎都是 Foo -> S
嘿,我猜这可能相当微不足道,但我很难找到答案或弄清楚它。 我正在尝试创建一个带有任意间距的彩色方 block 网格。这本身很容易做到,特别是因为我只需要九个正方形。但是虽然我看着我完成的代码,我不禁觉
我有 woocommerce 设置,其中包含产品和这些产品的变体。当我更改变化时(例如,产品的尺寸(340克或900克),我希望它在页面上动态更新价格,以便人们可以看到两种尺寸之间的价格差异。目前,我
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 7 年前。
在我的一节课上,我被问到这是一个脑筋急转弯,但我无法弄明白(这不是家庭作业问题,只是其中一位助教给我们的一个脑筋急转弯让我们思考)。 给你一根杆,上面有 n 个要切割的点,例如 [1,5,11],以及
关于 CRP如果我想实现它的细微变化(使用模板模板参数),我会得到一个编译错误: template class Derived> class Base { public: void Call
我正在创建一个 woocommerce 主题,并且我有产品变体,即显示在产品详细信息页面上的尺寸,但问题是我想通过使用产品 ID 在我的自定义 php 页面中获取所有变体,任何人都可以帮助我。 提前致
我正在使用 Ionic 开发移动应用程序,我必须与 Twitter API 连接。 所以我使用 ng-cordova 和 $cordovaAuth .但是当我这样做时: $cordovaOauth.t
这里的网站有一个音乐播放器http://www.numberonedesigns.com/ubermusic.com/ ...当点击下一个按钮并随机突出显示时,它不会正确随机化。它总是返回到播放列表中
我有列 sql 变体,其含义如下:100, 150, D1我正在尝试根据特定逻辑将列中的所有数字转换为字母(例如 D1)以防万一。但是 150 有空格并且 CASE WHEN 不起作用。 这是我正在使
有没有一种快速方法可以用从匹配模式派生的数据替换所有出现的某些模式? 例如,如果我想将字符串中出现的所有数字替换为用 0 填充到固定长度的相同数字。 在本例中,如果长度为 4,则 ab3cd5 将变为
我目前正在寻找生成具有特定位数的数字列表,我的代码当前如下: | Python 2.7 | import itertools inp = raw_input('Number of digits to
我正在对类型系统进行研究。对于这项工作,我正在研究流行语言中变体、结构子类型、通用多态性和存在多态性的用法。像 heskell、ocaml 这样的功能性语言提供了这样的功能。但我想知道像 C++ 这样
这是 variant.hpp 文件中的相关代码(可在此处找到 http://www.boost.org/doc/libs/1_49_0/boost/variant/variant.hpp) templ
您好,我有两个具有多对多关系的表和一个联结表。简而言之,具有不同属性的产品也随之增加了价格。为了更清楚地说明我是产品和属性表。 +-------------+------------+--------
我是一名优秀的程序员,十分优秀!