s**********1
发帖数: 73 | 1 Input是两个List，一个反应了equal的关系，比如A=B， B=C，另外一个反应
了not-equal的关系，比如A!=C
Output是判断这两个List有没有conflict……
感觉没有思路啊%>_<%能想到的就是用HashMap存所有的equal关系，然后遍历not-equal
的那个List来判断，但是如何存所有的equal关系呢? A就存B呢，还是A要存B,C？ | f********y
发帖数: 156 | | x*******9
发帖数: 138 | 3 把这题转化成图来看。
如果A==B => A和B之间连一条无向边
我们先处理完第一个List，建图
然后对于第二个List，每一个点对，我们判断一下这两个点是否联通。如果联通
，就conflict。 | M******i
发帖数: 468 | 4 为什么我连题目都看不懂？ 没刷过题的人真是不行啊 | q***a
发帖数: 26 | 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……
: 感觉没有思路啊%>_<%能想到的就是用HashMap存所有的equal关系，然后遍历not-equal
: 的那个List来判断，但是如何存所有的equal关系呢? A就存B呢，还是A要存B,C？
| b**g
发帖数: 25 | | I******c
发帖数: 163 | 7 我的想法和3楼类似，
不过第二个list可能很大，对每一对分别求联通可能比较耗时
我觉得应该先建一个表，表明每个节点所在对组。建表用一次遍历就可以了。
或者更简单，象2楼说的那样，用union find,连图都不需要建立。 | M***6
发帖数: 895 | 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。。
不知道对不对。 |
|
