b******i 发帖数: 914 | 1 给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序
例:
单词顺序:
wrt
wrf
er
ett
rftt
字母顺序:
w,e,r,t,f
大家说说怎么做看? |
h*****a 发帖数: 1718 | 2 topological sort
【在 b******i 的大作中提到】 : 给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序 : 例: : 单词顺序: : wrt : wrf : er : ett : rftt : 字母顺序: : w,e,r,t,f
|
w****a 发帖数: 710 | |
b******i 发帖数: 914 | |
b******i 发帖数: 914 | 5 Hi,
你好,贴一下你的code。有几个问题:
1. Graph g(26)是什么,这个Graph的类是哪儿来的?
2. 中间
for(auto i = 0; i < len; ++i) {
if(w1[i] < w2[i]) {
g.add_edge(w1[i] - 'a', w2[i] - 'a');
} else if(w1[i] > w2[i]) {
g.add_edge(w2[i] - 'a', w1[i] - 'a');
}
}
我觉得有问题,首先并不知道w1[i]和w2[i]哪个大啊,只知道w1
从小到大来排序的)。所以我觉得正缺的应该是:
for(auto i = 0; i < len; ++i) {
if(w1[i] != w2[i])
g.add_edge(w1[i]-'a', w2[i]-'a');
}
最后再做topological sort。你这个g.torp_sort()是自带的方法吗?
P.S. 你的博客很好,找到了好几道我感兴趣的题!
----------------
string get_order(const vector& dict) {
Graph g(26);
auto build_graph = [&](const string& w1, const string& w2) {
auto len = min(w1.length(), w2.length());
for(auto i = 0; i < len; ++i) {
if(w1[i] < w2[i]) {
g.add_edge(w1[i] - 'a', w2[i] - 'a');
} else if(w1[i] > w2[i]) {
g.add_edge(w2[i] - 'a', w1[i] - 'a');
}
}
};
for(auto i = 0; i < dict.size() - 1; ++i) {
build_graph(dict[i], dict[i+1]);
}
auto sorted = g.topo_sort();
string ret;
for(auto n : sorted) {
ret += 'a' + (char)n;
}
return ret;
}
【在 w****a 的大作中提到】 : http://www.fgdsb.com/2014/12/28/get-lexicographical-order-from-
|
w****a 发帖数: 710 | 6 1. graph是我实现的一个简单类,链接在这里
http://www.fgdsb.com/2014/12/31/graph/
2. 因为是有向图,需要有方向,所以你的建议是会得出不正确结果的
很高兴你喜欢我的博客
【在 b******i 的大作中提到】 : Hi, : 你好,贴一下你的code。有几个问题: : 1. Graph g(26)是什么,这个Graph的类是哪儿来的? : 2. 中间 : for(auto i = 0; i < len; ++i) { : if(w1[i] < w2[i]) { : g.add_edge(w1[i] - 'a', w2[i] - 'a'); : } else if(w1[i] > w2[i]) { : g.add_edge(w2[i] - 'a', w1[i] - 'a'); : }
|
k******e 发帖数: 145 | 7 您好
addedge之后是否需要break呢?
谢谢
【在 w****a 的大作中提到】 : 1. graph是我实现的一个简单类,链接在这里 : http://www.fgdsb.com/2014/12/31/graph/ : 2. 因为是有向图,需要有方向,所以你的建议是会得出不正确结果的 : 很高兴你喜欢我的博客
|
z******f 发帖数: 277 | |
b******i 发帖数: 914 | 9 请问第二点能不能展开说说呢?
我理解你的add_edge方法是加一个从first_arg到second_arg的edge,所以是有向的。
【在 w****a 的大作中提到】 : 1. graph是我实现的一个简单类,链接在这里 : http://www.fgdsb.com/2014/12/31/graph/ : 2. 因为是有向图,需要有方向,所以你的建议是会得出不正确结果的 : 很高兴你喜欢我的博客
|
b******i 发帖数: 914 | 10 对的,我觉得需要,在我回复的版本中我忘记写了,bug!
【在 k******e 的大作中提到】 : 您好 : addedge之后是否需要break呢? : 谢谢
|
h**********c 发帖数: 4120 | 11 对每一个字母,binary search 在字典上
对字母出现的第一个位置排序
如果有字母从不是任何word的首字母,需要对words的第i字母binary search,i-pass
【在 b******i 的大作中提到】 : 给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序 : 例: : 单词顺序: : wrt : wrf : er : ett : rftt : 字母顺序: : w,e,r,t,f
|
r********7 发帖数: 102 | 12 自己练着写了一个,请见 https://sites.google.com/site/codingbughunter/
algorithm-question-discuss 第四题
【在 b******i 的大作中提到】 : 给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序 : 例: : 单词顺序: : wrt : wrf : er : ett : rftt : 字母顺序: : w,e,r,t,f
|
r********7 发帖数: 102 | 13 恩,准确说 不算自己写的,借鉴了一个帖子。。分享给大家
【在 r********7 的大作中提到】 : 自己练着写了一个,请见 https://sites.google.com/site/codingbughunter/ : algorithm-question-discuss 第四题
|