你的浏览器禁用了JavaScript, 请开启后刷新浏览器获得更好的体验!
发现
动态
话题
发起
问题
登录
面试经验
Google面试题求解:26个英文字母从新排序(未知的顺序alphabet),然后用这个位置的顺序给一组数据(array list)排序现在给你这组array list,问能不能计算出来那个alphabet未知的顺序。
没有找到相关结果
已邀请:
与内容相关的链接
提交
1 个回复
木舟
赞同来自:
数美招聘
、
Eric_Jiang
**思路:**
拓扑排序就行
初始排序图为单个点,小于任何字母(添加为了保证图的连通性,编程简单),为有向图。
对于输入array ,取每个串第一个字母,去重复,得到一个有序序列。将这个串merge到排序图中,merge的方法:
a.对每个字母,如果在中没有存在,则添加到中。若为中第一个字母,则添加边->,否则添加边->。
b. 如果在中已经存在,若边->(对于为->)不存在,添加此边。
对于首字母相同的中的串,去掉首字母后组成新的array ', 如果有空串,在空串处splitarray。 递归调用步骤1.
**结果生成: **
1. 如果中存在回路,输入有矛盾,无解
2. 如果中的字母节点小于26个,或者存在环(除1情况外),产生不唯一的解。
3. 如果是一条含有26个节点的无环路径,产生唯一解。
要回复问题请先
登录
或
注册
发起人
数美招聘
问题状态
最新活动:
2015-09-09 17:10
浏览:
4598
关注:
2
人
1 个回复
木舟
赞同来自: 数美招聘 、Eric_Jiang
拓扑排序就行
初始排序图为单个点,小于任何字母(添加为了保证图的连通性,编程简单),为有向图。
对于输入array ,取每个串第一个字母,去重复,得到一个有序序列。将这个串merge到排序图中,merge的方法:
a.对每个字母,如果在中没有存在,则添加到中。若为中第一个字母,则添加边->,否则添加边->。
b. 如果在中已经存在,若边->(对于为->)不存在,添加此边。
对于首字母相同的中的串,去掉首字母后组成新的array ', 如果有空串,在空串处splitarray。 递归调用步骤1.
**结果生成: **
1. 如果中存在回路,输入有矛盾,无解
2. 如果中的字母节点小于26个,或者存在环(除1情况外),产生不唯一的解。
3. 如果是一条含有26个节点的无环路径,产生唯一解。