我在接受采访时被问到这个问题.假设您有一个有序字典,并给出一个无序字符列表 - 您将如何按优先顺序排列这些字符？此词典包含保证显示所有26个字符的单词.但请注意,字典的大小可能是任何内容.字典可以小到几个单词,并且可能没有针对每个字符的单独部分,例如,可能没有用于开头的单词的部分a; 虽然a会作为另一个词的一部分出现,例如"bat".
这本字典可能被"责令"(/讽刺)这样"斑马",'苹果’,'猫’,'粗鲁’,如果你给出的列表{ a,z,r},正确的顺序是{ z,a,r因为"斑马"在字典中位于"苹果"之前,我们知道在presedence z之前a出现.因为"apple"出现在"cat"之前,我们知道a之前c.因为"cat"出现在"crass"之前,我们知道这a到来之前r,这种排序的叶子c和r用ambugious presendece,但由于信件列表为{ a,z,r},我们知道解决的办法是{ z,a,r}.
Hel*_*rld 11
使用带有26个顶点的有向图,每个顶点代表一个字符.从顶点A到顶点B的边缘表示字母B在A的前面.
第一步是建立只有顶点但没有边缘的图形.
其次,逐字扫描输入字典.并将每个单词与前一个单词进行比较.您应该为扫描的每个单词找到确切的关系.因此,您在此图表中添加了一条边.假设字典是正确的,应该没有冲突.
完成字典后,输出字母
编辑:为了更好地解释这个算法,让我们在你的样本输入上运行它.
输入:{"zebra","apple","cat","crass"}
字0和字1,我们立即知道z在a之前出现,所以我们创建一个边a-> z
单词1和单词2,我们立即知道a在c之前出现,所以我们制作另一个边c-> a
Word 2和Word 3,第一个字母是相同的"c",但第二个字母不同,所以我们知道a出现在r之前,所以我们有另一个边r-> a
现在所有的单词都被读了.通过随机拾取一个顶点来输出顺序(比如我们选择c),然后我们在图中有c-> a-> z.输出z并从图形中删除z(将其标记为NULL).现在选择另一个(比如我们选择r),然后我们在图中找到r-> a.我们输出并删除图表.现在我们选择另一个(比如我们再次选择c),找不到路径,所以我们只输出c并删除它.现在我们选择最后一个,r,再没有路径,所以我们输出r并删除它.由于删除了所有顶点,因此算法完成.
输出为z,a,c,r."c"和"r"的顺序是随机的,因为我们并不真正知道它们与输入的关系.