f*********i 发帖数: 197 | 1 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
有可能的alphabetical order,(后来又问了如何判断是否有conflict)
例子:it is a good day today,
it
is
a
good
day
我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
有的可能组合....30分钟实在是不够阿....算了,move on了.
期待高人解答. |
g**e 发帖数: 6127 | 2 没看懂输出的是什么...
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k 发帖数: 623 | 3 Build a tree?
If it is DAG, then no conflict and then do the DFS to output the topological
order?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k 发帖数: 623 | 4 貌似输出所有的排序,因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】 : 没看懂输出的是什么...
|
g*****k 发帖数: 623 | 5 and if you want all orders, then permute all children and get different DFS
topological
【在 g*****k 的大作中提到】 : Build a tree? : If it is DAG, then no conflict and then do the DFS to output the topological : order?
|
h*********n 发帖数: 11319 | 6 所有能判断顺序的字母之间连上一条有向边,最后会生成一个dag,然后
void printAllOrders(graph G, string order){
if(G not empty){
for each node in G{
if(node.inDeg==0){
G.delete(node);
order.append(node);
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, "");
把每个list按顺序concatenate,每个list内部随便排列
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
r*******y 发帖数: 1081 | 7 bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
i**********e 发帖数: 1145 | 8 从你那个例子:
"it is a good day today"
可以建个链表,t->s, i->a->g->d->t
然后 merge 成:i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来?
还是有一些 trick 在里面?
这里有介绍 DAG 的算法:
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
b**********2 发帖数: 1923 | 9 btw, how do u know u are rejected? does the recruiter contact u and tell u
that u are rejected? how many days after ur onsite?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
f*********i 发帖数: 197 | 10 两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗..... |
|
|
d*******l 发帖数: 338 | 11 最后图可能是不连通的,没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点,然后从它开始DFS
【在 i**********e 的大作中提到】 : 从你那个例子: : "it is a good day today" : 可以建个链表,t->s, i->a->g->d->t : 然后 merge 成:i->a->g->d->t->s : 怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了. : 但如果是这样的情况似乎很复杂啊: : c->a, s->b->a : 这题是不是要有对图论有很深的知识才能答出来? : 还是有一些 trick 在里面? : 这里有介绍 DAG 的算法:
|
b*********n 发帖数: 1258 | 12 this is toplogical sort, isn't it?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
h*********n 发帖数: 11319 | 13 看看我的方法行不?
【在 d*******l 的大作中提到】 : 最后图可能是不连通的,没有依赖关系的字母看做单个的节点。可以添加一个指向所有 : 字母的辅助节点,然后从它开始DFS
|
g***s 发帖数: 3811 | 14 yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】 : 看看我的方法行不?
|
g**u 发帖数: 583 | 15
请问:
如果同时有2个或者2个以上的node的inDeg是0的话,怎样可以保证输出了所有可能的组
合呢?
谢谢
【在 h*********n 的大作中提到】 : 所有能判断顺序的字母之间连上一条有向边,最后会生成一个dag,然后 : void printAllOrders(graph G, string order){ : if(G not empty){ : for each node in G{ : if(node.inDeg==0){ : G.delete(node); : order.append(node); : printAllOrders(G, order); : G.addback(node);//together with deleted edges : }
|
g**u 发帖数: 583 | 16
大牛, 讲讲为什么可以产生所有的合法的组合, 谢了
【在 g***s 的大作中提到】 : yes. that's right. 其实就是始终遍历度为0的点。
|
g*****k 发帖数: 623 | 17 对所有的inDeg是0的点依次枚举啊,这样就保证所有的可能。
【在 g**u 的大作中提到】 : : 大牛, 讲讲为什么可以产生所有的合法的组合, 谢了
|
v*s 发帖数: 946 | 18 貌似topological sort只会输出一种可能的排列。
【在 b*********n 的大作中提到】 : this is toplogical sort, isn't it?
|
h*********n 发帖数: 11319 | 19 that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】 : 貌似topological sort只会输出一种可能的排列。
|
g**u 发帖数: 583 | 20
0
还有个问题没有解决啊, 你的node_inDeg=0的node所组成的集合没有更新
还有, 没看明白 你说的 “每个list按顺序concatenate,每个list内部随便排列”
可以详细说一下么?
谢了
【在 h*********n 的大作中提到】 : that's the point of undo the deletion and recurse next point with inDeg = 0
|
|
|
g***s 发帖数: 3811 | 21 删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】 : : 0 : 还有个问题没有解决啊, 你的node_inDeg=0的node所组成的集合没有更新 : 还有, 没看明白 你说的 “每个list按顺序concatenate,每个list内部随便排列” : 可以详细说一下么? : 谢了
|
g**u 发帖数: 583 | 22
还是有一点不明白,比如说有下面一个简单的 图
1-》2
1-》3
2-》4
3-》4
有2个排列:
1 2 3 4或者 1 3 2 4
比较纠结的是
在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
谢谢
【在 g***s 的大作中提到】 : 删除点的时候更新这个集合。 : 他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
|
g***s 发帖数: 3811 | 23 去掉1以后,变成
2-》4
3-》4
所以在第二层上,度为0的点是2,3。分别遍历,所以就是
1,2,3,4
1,3,2,4
【在 g**u 的大作中提到】 : : 还是有一点不明白,比如说有下面一个简单的 图 : 1-》2 : 1-》3 : 2-》4 : 3-》4 : 有2个排列: : 1 2 3 4或者 1 3 2 4 : 比较纠结的是 : 在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
|
o*****e 发帖数: 99 | 24 问题的关键是每当前面单词选定一个字母,后面就不能重复了。
(不知道相邻单词能不能取同一个字母,假设不能)
那就是一个不复杂的递归问题了。
My pseudo code,
String array size n
S0 ~ Sn-1
Output out[0 ~ n-1]
void func(S[], out[], k) {
if (k==n) {
print(out);
return;
}
for(i in 0 ~ strlen(S[k]-1){
if (S[k][i] not in Out[0 ~ k-1]) {
out[k] = S[k][i];
func(S, out, k+1);
}
}
}
main:
func(S, out, 0)
How to design efficiency algorithm to find whether
char S[k][i] is in string Out[0 ~ k-1]
A simple hash map should do it. |
h*********n 发帖数: 11319 | 25 那句话是错的。。。忽略之就可以了
=
【在 g**u 的大作中提到】 : : 还是有一点不明白,比如说有下面一个简单的 图 : 1-》2 : 1-》3 : 2-》4 : 3-》4 : 有2个排列: : 1 2 3 4或者 1 3 2 4 : 比较纠结的是 : 在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
|
k****n 发帖数: 369 | 26
一个比较显然的结论是,首字母是按照递增序排列的,所以你两两看就是给自己增加混
乱了
直接应该就写出来
i
然后考察有相同prefix的string,把它们确定的关系insert到上面的序列里面
像上面就是
i
应该可以recursive的做
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g***s 发帖数: 3811 | 27 I could not understand what you said.
"it is A"
t < s
i < A
then?
【在 k****n 的大作中提到】 : : 一个比较显然的结论是,首字母是按照递增序排列的,所以你两两看就是给自己增加混 : 乱了 : 直接应该就写出来 : i: 然后考察有相同prefix的string,把它们确定的关系insert到上面的序列里面 : 像上面就是 : i: 应该可以recursive的做
|
f*********i 发帖数: 197 | 28 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所
有可能的alphabetical order,(后来又问了如何判断是否有conflict)
例子:it is a good day today,
it
is
a
good
day
我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所
有的可能组合....30分钟实在是不够阿....算了,move on了.
期待高人解答. |
g**e 发帖数: 6127 | 29 没看懂输出的是什么...
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g*****k 发帖数: 623 | 30 Build a tree?
If it is DAG, then no conflict and then do the DFS to output the topological
order?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
|
|
g*****k 发帖数: 623 | 31 貌似输出所有的排序,因为是partial order所以有很多种?
没看懂输出的是什么...
【在 g**e 的大作中提到】 : 没看懂输出的是什么...
|
g*****k 发帖数: 623 | 32 and if you want all orders, then permute all children and get different DFS
topological
【在 g*****k 的大作中提到】 : Build a tree? : If it is DAG, then no conflict and then do the DFS to output the topological : order?
|
h*********n 发帖数: 11319 | 33 所有能判断顺序的字母之间连上一条有向边,最后会生成一个dag,然后
void printAllOrders(graph G, string order){
if(G not empty){
for each node in G{
if(node.inDeg==0){
G.delete(node);
order.append(node);
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, "");
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
r*******y 发帖数: 1081 | 34 bless
onsite到底是全面考察 problem solving 的能力
还是全面考察你是否能融入到这个team的能力?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
i**********e 发帖数: 1145 | 35 从你那个例子:
"it is a good day today"
可以建个链表,t->s, i->a->g->d->t
然后 merge 成:i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来?
还是有一些 trick 在里面?
这里有介绍 DAG 的算法:
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
b**********2 发帖数: 1923 | 36 btw, how do u know u are rejected? does the recruiter contact u and tell u
that u are rejected? how many days after ur onsite?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
f*********i 发帖数: 197 | 37 两个星期没有消息,发信HR,被拒了. 发现google只要onsite后一个星期不联系你,大部
分情况就黄了.
DAG的方法好像也不太行阿,我当时就是说从图的角度来找所有可能性.他们一直纠结于
图的起点问题,我回答说所有的节点都有一个出度和一个入度,任意一个入度为0的节点
都可以作为开始节点,他们不满意.
还有,当merge的时候是要输出所有的可能,这个基本上是O(n^2)的复杂度,因为两个
independent的链表merge有up to N^2种可能,同时还要考虑他们是否部分重合.
到现在回想起来都是一头汗..... |
d*******l 发帖数: 338 | 38 最后图可能是不连通的,没有依赖关系的字母看做单个的节点。可以添加一个指向所有
字母的辅助节点,然后从它开始DFS
【在 i**********e 的大作中提到】 : 从你那个例子: : "it is a good day today" : 可以建个链表,t->s, i->a->g->d->t : 然后 merge 成:i->a->g->d->t->s : 怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了. : 但如果是这样的情况似乎很复杂啊: : c->a, s->b->a : 这题是不是要有对图论有很深的知识才能答出来? : 还是有一些 trick 在里面? : 这里有介绍 DAG 的算法:
|
b*********n 发帖数: 1258 | 39 this is toplogical sort, isn't it?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
h*********n 发帖数: 11319 | 40 看看我的方法行不?
【在 d*******l 的大作中提到】 : 最后图可能是不连通的,没有依赖关系的字母看做单个的节点。可以添加一个指向所有 : 字母的辅助节点,然后从它开始DFS
|
|
|
g***s 发帖数: 3811 | 41 yes. that's right. 其实就是始终遍历度为0的点。
【在 h*********n 的大作中提到】 : 看看我的方法行不?
|
g**u 发帖数: 583 | 42
请问:
如果同时有2个或者2个以上的node的inDeg是0的话,怎样可以保证输出了所有可能的组
合呢?
谢谢
【在 h*********n 的大作中提到】 : 所有能判断顺序的字母之间连上一条有向边,最后会生成一个dag,然后 : void printAllOrders(graph G, string order){ : if(G not empty){ : for each node in G{ : if(node.inDeg==0){ : G.delete(node); : order.append(node); : printAllOrders(G, order); : G.addback(node);//together with deleted edges : }
|
g**u 发帖数: 583 | 43
大牛, 讲讲为什么可以产生所有的合法的组合, 谢了
【在 g***s 的大作中提到】 : yes. that's right. 其实就是始终遍历度为0的点。
|
g*****k 发帖数: 623 | 44 对所有的inDeg是0的点依次枚举啊,这样就保证所有的可能。
【在 g**u 的大作中提到】 : : 大牛, 讲讲为什么可以产生所有的合法的组合, 谢了
|
h*********n 发帖数: 11319 | 45 that's the point of undo the deletion and recurse next point with inDeg = 0
【在 v*s 的大作中提到】 : 貌似topological sort只会输出一种可能的排列。
|
g**u 发帖数: 583 | 46
0
还有个问题没有解决啊, 你的node_inDeg=0的node所组成的集合没有更新
还有, 没看明白 你说的 “每个list按顺序concatenate,每个list内部随便排列”
可以详细说一下么?
谢了
【在 h*********n 的大作中提到】 : that's the point of undo the deletion and recurse next point with inDeg = 0
|
g***s 发帖数: 3811 | 47 删除点的时候更新这个集合。
他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
【在 g**u 的大作中提到】 : : 0 : 还有个问题没有解决啊, 你的node_inDeg=0的node所组成的集合没有更新 : 还有, 没看明白 你说的 “每个list按顺序concatenate,每个list内部随便排列” : 可以详细说一下么? : 谢了
|
g**u 发帖数: 583 | 48
还是有一点不明白,比如说有下面一个简单的 图
1-》2
1-》3
2-》4
3-》4
有2个排列:
1 2 3 4或者 1 3 2 4
比较纠结的是
在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
谢谢
【在 g***s 的大作中提到】 : 删除点的时候更新这个集合。 : 他那句话我也没有明白。但整个算法是对的。基于拓扑排序的的方法。
|
g***s 发帖数: 3811 | 49 去掉1以后,变成
2-》4
3-》4
所以在第二层上,度为0的点是2,3。分别遍历,所以就是
1,2,3,4
1,3,2,4
【在 g**u 的大作中提到】 : : 还是有一点不明白,比如说有下面一个简单的 图 : 1-》2 : 1-》3 : 2-》4 : 3-》4 : 有2个排列: : 1 2 3 4或者 1 3 2 4 : 比较纠结的是 : 在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
|
o*****e 发帖数: 99 | 50 问题的关键是每当前面单词选定一个字母,后面就不能重复了。
(不知道相邻单词能不能取同一个字母,假设不能)
那就是一个不复杂的递归问题了。
My pseudo code,
String array size n
S0 ~ Sn-1
Output out[0 ~ n-1]
void func(S[], out[], k) {
if (k==n) {
print(out);
return;
}
for(i in 0 ~ strlen(S[k]-1){
if (S[k][i] not in Out[0 ~ k-1]) {
out[k] = S[k][i];
func(S, out, k+1);
}
}
}
main:
func(S, out, 0)
How to design efficiency algorithm to find whether
char S[k][i] is in string Out[0 ~ k-1]
A simple hash map should do it. |
|
|
h*********n 发帖数: 11319 | 51 那句话是错的。。。忽略之就可以了
=
【在 g**u 的大作中提到】 : : 还是有一点不明白,比如说有下面一个简单的 图 : 1-》2 : 1-》3 : 2-》4 : 3-》4 : 有2个排列: : 1 2 3 4或者 1 3 2 4 : 比较纠结的是 : 在那个算法里面 输出 1 2 3 4之后,如何回退到 1 3 2这个状态呢?
|
k****n 发帖数: 369 | 52
一个比较显然的结论是,首字母是按照递增序排列的,所以你两两看就是给自己增加混
乱了
直接应该就写出来
i
然后考察有相同prefix的string,把它们确定的关系insert到上面的序列里面
像上面就是
i
应该可以recursive的做
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
g***s 发帖数: 3811 | 53 I could not understand what you said.
"it is A"
t < s
i < A
then?
【在 k****n 的大作中提到】 : : 一个比较显然的结论是,首字母是按照递增序排列的,所以你两两看就是给自己增加混 : 乱了 : 直接应该就写出来 : i: 然后考察有相同prefix的string,把它们确定的关系insert到上面的序列里面 : 像上面就是 : i: 应该可以recursive的做
|
r*******g 发帖数: 1335 | 54 没看懂题,输出难道不是一个整体的string?
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
q****x 发帖数: 7404 | 55 这题写代码有点二逼。
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
B*******1 发帖数: 2454 | 56 还好吧? 建图,然后topsort。
比版上那哥们电话phone就要写word ladder的好多了吧。
【在 q****x 的大作中提到】 : 这题写代码有点二逼。
|
g***x 发帖数: 494 | 57 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
解对吗?
【在 h*********n 的大作中提到】 : 所有能判断顺序的字母之间连上一条有向边,最后会生成一个dag,然后 : void printAllOrders(graph G, string order){ : if(G not empty){ : for each node in G{ : if(node.inDeg==0){ : G.delete(node); : order.append(node); : printAllOrders(G, order); : G.addback(node);//together with deleted edges : }
|
B*******1 发帖数: 2454 | 58 哪里看出backtracking啊?
就是topsort吧。
【在 g***x 的大作中提到】 : 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理 : 解对吗?
|
c*******n 发帖数: 72 | 59
哪里看出backtracking啊?就是topsort吧。
★ Sent from iPhone App: iReader Mitbbs 7.28 - iPad Lite
【在 B*******1 的大作中提到】 : 哪里看出backtracking啊? : 就是topsort吧。
|
e*****m 发帖数: 171 | 60 void printAllOrders(graph G, string order){
if(G not empty){
for each node in G{
if(node.inDeg==0){
G.delete(node);
order.append(node); //请问这一句是不是有错啊?我觉得
应该是删掉这一句,并在下一句中写printAllOrders(G,order+node.toString()), 否则
order不是
一直在append,越来越长么(假设是java,按引用传递)
printAllOrders(G, order);
G.addback(node);//together with deleted edges
}
}
}
else
print order
}
printAllOrders(graph G, ""); |
|
|
w****x 发帖数: 2483 | 61 void MarkMap(const char* szStrs[], int n, int nBegIndex, bool chrMap[26][26])
{
assert(szStrs && nBegIndex >= 0 && n >= 0);
if (n <= 1) return;
int nDiv = -1;
for (int i = 0; i < n-1; i++)
{
char tmp1 = *(szStrs[i] + nBegIndex);
char tmp2 = *(szStrs[i+1] + nBegIndex);
assert(((tmp1 >= 'a' && tmp1 <= 'z') || tmp1 == 0));
assert(((tmp2 >= 'a' && tmp2 <= 'z') || tmp2 == 0));
if (tmp1 != 0 && nDiv < 0)
nDiv = i;
if (tmp1 == 0 || tmp1 == tmp2)
continue;
MarkMap(szStrs + nDiv, i + 1 - nDiv, nBegIndex + 1, chrMap);
nDiv = i+1;
chrMap[tmp1 - 'a'][tmp2 - 'a'] = true;
}
MarkMap(szStrs + nDiv, n - nDiv, nBegIndex + 1, chrMap);
}
void PrintComb(bool bRec[26], bool chrMap[26][26], char szTmp[26], int nBeg)
{
if (nBeg == 26)
{
for (int i = 0; i < 26; i++)
cout<
cout<
return;
}
for (int i = 0; i < 26; i++)
{
if (bRec[i])
continue;
int j = 0;
for (; j < 26; j++)
{
if (!bRec[j] && chrMap[j][i])
break;
}
if (j >= 26)
{
bRec[i] = true;
szTmp[nBeg] = 'a' + i;
PrintComb(bRec, chrMap, szTmp, nBeg + 1);
bRec[i] = false;
}
}
}
void PrintAllPossible(const char* szStrs[], int n)
{
assert(szStrs && n > 0);
bool chrMap[26][26];
memset(chrMap, 0, sizeof(chrMap));
MarkMap(szStrs, n, 0, chrMap);
bool bRec[26];
memset(bRec, 0, sizeof(bRec));
char szTmp[26];
PrintComb(bRec, chrMap, szTmp, 0);
} |
w****x 发帖数: 2483 | 62 这题如果叫你在半小时内写出代码你可以给那个面试官说:
FUCK OFF !!!!!!!!!!! |
f*******t 发帖数: 7549 | 63 对于搞ACM竞赛的人这种题半小时写出差不多的代码应该没压力。。
【在 w****x 的大作中提到】 : 这题如果叫你在半小时内写出代码你可以给那个面试官说: : FUCK OFF !!!!!!!!!!!
|
y***d 发帖数: 2330 | 64 阿,似乎不难,我是不是申请一下 google...
【在 f*********i 的大作中提到】 : 一个arraylist,里面有很多string,它们按照未知的alphabetical顺序排列,要求输出所 : 有可能的alphabetical order,(后来又问了如何判断是否有conflict) : 例子:it is a good day today, : it: is: a: good: day: 我觉得有两个难点,一个是如何把多个一一对应的大小关系merge,另一个是如何输出所 : 有的可能组合....30分钟实在是不够阿....算了,move on了.
|
w****x 发帖数: 2483 | 65 不信没压力, 我第二次写28分钟, 第二次那可是有了思路和知道了所有要注意的地方的
情况下呀~~ 这题30分钟要求code出来是不是要求太过了, 明显是刁难, 伪代码或讲思
路还差不多 |