ela*_*dan 24 puzzle algorithm graph-theory topological-sort
我的女朋友在接受采访时得到了这个问题,我非常喜欢它,我以为我会分享它......写一个接收字典的算法(字数组).数组按字典顺序排序,但abc顺序可以是任何内容.例如,它可以是z,y,x,..,c,b,a.或者它可能完全搞砸了:d,g,w,y,......它甚至不需要包含所有的abc字母,最后它根本不必是字母.它可以是形成字符串的任何符号.例如,它可以由5,？,!,@,？组成......你明白了.由您的算法决定发现字母是什么(简单部分).
算法应返回符号的正确词典顺序.
注意事项/需要考虑的事项:1.对于给定的字典,您是否总能发现所有字母的完整顺序？考虑一个只有1个单词,多于1个符号的字典...... 2.你不能认为字典是没有错误的.该算法应确定字典是否包含矛盾并输出存在错误.3.提示:想一个好的数据结构来表示你在符号之间发现的关系.这应该使问题更容易.
我明天可能会发布我的解决方案.我绝不会声称它是最有效的.我想先看看其他人的想法.希望你喜欢这个问题
PS我认为发布解决方案的最佳格式是使用伪代码,但我将此留待您考虑
pol*_*nts 34
这是有向无环图上的拓扑排序.您需要首先构建图形:顶点是字母,如果一个字典在字典上小于另一个,则有一个边缘.拓扑顺序然后给你答案.
矛盾的是有向图不是非循环的.唯一性取决于是否存在哈密顿路径,这在多项式时间内是可测试的.
您可以通过比较字典中的每两个连续"单词"来完成此操作.假设你说这两个词一个接一个地出现:
x156@
x1$#2z
然后,x1在这种情况下,您会找到最长的公共前缀,并检查此前缀后面的紧随其后的字符.在这种情况下,我们有5和$.由于单词在字典中按此顺序出现,我们可以确定5必须按字典顺序小于$.
同样,给出以下词语(在词典中一个接一个出现)
jhdsgf
19846
19846adlk
我们可以'j' < '1'从第一对(其中最长的公共前缀是空字符串)中分辨出来.第二对没有告诉我们任何有用的东西(因为一个是另一个的前缀,所以没有可比较的字符).
现在假设我们稍后会看到以下内容:
oi1019823
oij(*#@&$
然后我们发现了一个矛盾,因为这一对说明了这一点'1' < 'j'.
有两种传统的拓扑排序方法.算法上更简单的是深度优先搜索方法,其中存在从if x到yif 的边缘y < x.
该算法的伪代码在维基百科中给出:
L ? Empty list that will contain the sorted nodes
S ? Set of all nodes with no incoming edges
function visit(node n)
if n has not been visited yet then
mark n as visited
for each node m with an edge from n to m do
visit(m)
add n to L
for each node n in S do
visit(n)
在上述算法结束时,列表L将以拓扑顺序包含顶点.
以下是维基百科的引用:
如果拓扑排序具有排序顺序中的所有连续顶点对通过边连接的属性,则这些边在DAG中形成有向哈密顿路径.如果存在哈密尔顿路径,则拓扑排序顺序是唯一的; 没有其他顺序尊重路径的边缘.相反,如果拓扑排序不形成哈密顿路径,则DAG将具有两个或更多有效拓扑排序,因为在这种情况下,总是可以通过交换两个未通过边连接的连续顶点来形成第二个有效排序对彼此.因此,可以在多项式时间内测试是否存在唯一排序,以及是否存在哈密顿路径.
因此,要检查订单是否唯一,您只需检查L(来自上述算法)中的所有两个连续顶点是否通过直接边连接.如果是,则订单是唯一的.
构建图形后,拓扑排序就是O(|V|+|E|).唯一性检查是O(|V| edgeTest),edgeTest测试两个顶点是否通过边连接的复杂性.使用邻接矩阵,这是O(1).
构建图表只需要对字典进行单次线性扫描.如果存在W的话,那么它的O(W cmp),这里cmp是比较两个词的复杂性.你总是比较两个后续的话,那么你可以在必要时做各种优化,但在其他方面幼稚的比较O(L),其中L是的话长度.
一旦你确定你有足够的字母表信息等,你也可以短信阅读字典,但即使是一个天真的建设步骤O(WL),也就是字典的大小.