l*********4
发帖数: 112 | 1 有一个binary directed acyclic graph， 每个node存有一个字符，有一个左节点和一
个右节点。
（node定义如下：
Node {
Node L;
Node R;
char ch;
}
）
这样如果in-order traverse这个DAG，就会得到一个string。例子如下：假设一个DAG
只有两个node，分别装着A和B这两个字符。假设Node A的左右两条边都指向Node B:
A (root node)
||
B
那么这个存储的string就是BAB
现在假设已经有了一个这样的DAG, 请写一个函数，返回这个string的第k个字符。要求
复杂度不能是exponential的。。。
我先写了个in order 的遍历。面试官就问我如果n个node,string最长可以是多少
我觉得是2^n-1
面试官说，那么traverse的话最坏情况复杂度就是O(2^n)，不符合要求～
谢谢大家指教！ |
l********s
发帖数: 358 | |
s*****j
发帖数: 35 | 3 没懂。。。这不就是一个in order traversal么？
只不过因为是dag所以你要一个hash set来keep track 哪个是visited |
l*********4
发帖数: 112 | 4 因为面试官说如果有n个node，字符最长可以是2^n-1
遍历的话最坏情况就是O(2^n)了。。。
【在 l********s 的大作中提到】
: 为什么不能遍历，遍历的复杂度又不是O(2^n)
|
l*********4
发帖数: 112 | 5 面试官先问我如果n个node,string最长可以是多少
我觉得是2^n-1
于是面试官说，traverse的话最坏情况复杂度就是O(2^n)啦，不符合要求。于是我就无
语凝噎了。。。
另外，遍历时访问过的node是可以再次访问的。比如那个两个节点的例子
A
||
B
A是root
in order 先访问B，再访问A,可是A的right edge指向的还是B，于是要再访问B。所以
这两个node的图表示的string是BAB
【在 s*****j 的大作中提到】
: 没懂。。。这不就是一个in order traversal么？
: 只不过因为是dag所以你要一个hash set来keep track 哪个是visited
|
e******u
发帖数: 1067 | 6 太难了，要是我直接放弃了
【在 l*********4 的大作中提到】
: 面试官先问我如果n个node,string最长可以是多少
: 我觉得是2^n-1
: 于是面试官说，traverse的话最坏情况复杂度就是O(2^n)啦，不符合要求。于是我就无
: 语凝噎了。。。
: 另外，遍历时访问过的node是可以再次访问的。比如那个两个节点的例子
: A
: ||
: B
: A是root
: in order 先访问B，再访问A,可是A的right edge指向的还是B，于是要再访问B。所以
|
k****s
发帖数: 16 | 7 被面试官问的套进去了吧
>> traverse的话最坏情况复杂度就是O(2^n)
traverse树是O(n), 枚举每个字符才是O(2^n).
traverse树的时候，记住左孩子的count就可以，右孩子相同的话，直接加count，不用
一个字符一个字符生成就不是O(2^n). |
s******7
发帖数: 1758 | 8 有点意思， 最坏 A=B=C=D, 确实字符串长度是 2^n
不过，这个跟fibonachi数列一样，你可以用dp保存sub的str,遇到=就copy一下就可以
了，所以还是O(n)就可以了 |
k***s
发帖数: 6 | 9 感觉应该是O(n)。以当前节点为inorder node的字符串长为left + 1 + right, 其中
left和right都可以只算一次然后用map存起来。
伪代码如下，感觉写得有点恶...
Character c;
Map map;
private int count(Node node, int rank) {
if (rank <= 0) {
return 0;
} else if (node == null) {
return 0;
} else if (map.containsKey(node)) {
return map.get(node);
}
int count = 1;
int leftCount = count(node.left, rank);
if (leftCount == -1) {
return -1;
} else if ((count += leftCount) == rank) {
c = node.ch;
return -1;
}
int rightCount += count(node.right, rank - count);
if (rightCount == -1) {
return -1;
} else if ((count += rightCount) == rank) {
c = node.ch;
return -1;
}
map.put(node, count);
return count;
}
public Character find(Node node, int rank) {
c = null;
map = new HashMap();
count(node, rank);
return c;
} |
l***m
发帖数: 16 | 10 很有趣的一个题
产生exp复杂度的原因是当Node L ＝＝ Node R的时候，只要一个input node却导致节
点数＊2了
所以可以给每个节点存储以当前节点为根的字符串的长度LEN(root)
LEN(root) = LEN(L) + LEN(R)
就像楼上说的用map把节点的count存起来，这样L＝＝R的时候R就直接拿结果就好了
因为没有环，O（n）就能遍历这个树，得到每个节点的LEN
要找第K个字符，root的位置是r＝LEN(L) + 1，比K小那就找R里的K － r，比K大就找L
里的K，不然返回就好。复杂度是树的高度。
DAG
【在 l*********4 的大作中提到】
: 有一个binary directed acyclic graph， 每个node存有一个字符，有一个左节点和一
: 个右节点。
: （node定义如下：
: Node {
: Node L;
: Node R;
: char ch;
: }
: ）
: 这样如果in-order traverse这个DAG，就会得到一个string。例子如下：假设一个DAG
|
G*****n
发帖数: 19 | 11 请问DAG的in order traversal 什么是停止条件？比如树的inorder 遇到叶结点(左右
child都是null)就可以返回当前recursion
那图的呢？ |
r********y
发帖数: 30 | 12 我怎么感觉复杂度应该是O(2*n)=O(n)呢？一个节点两条边，看题意最多就走完这两次
吧应该？不知道哪里理解的不对 |
l**********1
发帖数: 415 | 13 lz这个题里的树都是这种结构的a＝b＝c还是正常的binary tree和这种结构混杂的？就
是说有可能一个node左右ponter指向不同node么？如果都是这种结构的a＝b＝c，还有O
（n）的方法，不是感觉就没了 |
