Redian新闻
>
求帮忙解答一个面试算法题==
avatar
求帮忙解答一个面试算法题==# JobHunting - 待字闺中
s*1
1
Input是两个List,一个反应了equal的关系,比如A=B, B=C,另外一个反应
了not-equal的关系,比如A!=C
Output是判断这两个List有没有conflict……
感觉没有思路啊%>_的那个List来判断,但是如何存所有的equal关系呢? A就存B呢,还是A要存B,C?
avatar
f*y
2
貌似用Union find
avatar
x*9
3
把这题转化成图来看。
如果A==B => A和B之间连一条无向边
我们先处理完第一个List,建图
然后对于第二个List,每一个点对,我们判断一下这两个点是否联通。如果联通
,就conflict。
avatar
M*i
4
为什么我连题目都看不懂? 没刷过题的人真是不行啊
avatar
q*a
5
A, B... 都hash到对应的group
比如若A=B=C, 则hash(A)=hash(B)=hash(C)

equal

【在 s**********1 的大作中提到】
: Input是两个List,一个反应了equal的关系,比如A=B, B=C,另外一个反应
: 了not-equal的关系,比如A!=C
: Output是判断这两个List有没有conflict……
: 感觉没有思路啊%>_: 的那个List来判断,但是如何存所有的equal关系呢? A就存B呢,还是A要存B,C?

avatar
b*g
6
看不懂题
avatar
I*c
7
我的想法和3楼类似,
不过第二个list可能很大,对每一对分别求联通可能比较耗时
我觉得应该先建一个表,表明每个节点所在对组。建表用一次遍历就可以了。
或者更简单,象2楼说的那样,用union find,连图都不需要建立。
avatar
M*6
8
只包含字母吗?如果是的话,我的想法是创建一个 int[] equalTable = new int[26];
// java 默认初始化后全部为0.
int count = 0;//用于计数有多少个不同的等式,这里A=B, B=C,C=F, 属于同一个等
式。所以我们就把equalTable里A, B, C, F位置的index的值都设成某一个一样数字,
比如1。
然后扫描equal list,遇到一组等式比如 M = Z, 就看equalTable['M' - 'A' ] 和
equalTable['Z' - 'A' ] 是否都为0,如果是的话,
count++;
equalTable['M' - 'A' ] = count;
equalTable['Z' - 'A' ] = count;
如果有一个不为0,那么就把另一个为0的也设为这个非0值。
如果两个都不为0,且不相等,比如一个为2,一个为3,那么就把equalTable数组里全
部为2的都变成3(或者全部3都变成2也行)。
如果都不为0,且相等,不管,跳过。
然后扫描了一趟equal list后就得到一个大概长这样的table:
【1, 1, 2, 3, 2, 1, 0, 0, 0, 0, 1, 3, 3, 2 ....】.
然后再扫一遍not-equal那个list,看每个不等式,比如,W != Y, 在equalTable里
equalTable['W' - 'A' ] 和equalTable['Y' - 'A' ] 的数字是否相等,如果相等返回
有conflict。。
不知道对不对。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。