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 第四题
|
