一道公司面试题解决思路
一道公司面试题
如何判断两个循环链表是否相等?如“aabbcc”和"ccaabb"是相等的。请教有什么比较好的算法?
------解决方案--------------------
根据链表构造有向图?
------解决方案--------------------
用双指针
O(N)复杂度
aabbcc 和 ccaabb
i=0, j=0;
i=0, j=1;
i=0, j=2;
i=1, j=3;
i=2, j=4;
i=3, j=5;
i=4, j=0;(j %= str.Length)
一直能将i走到结尾即相等,否则不等
------解决方案--------------------
------解决方案--------------------
把两个循环链表都变成不循环,如aabbcc变成aabbccaabbcc
ccaabb变成ccaabbccaabb
然后判断变化后的两个链表的最大相同字串长度,如果>=n就相同反之...
复杂度参照最大公告字串复杂度
------解决方案--------------------
想到另一个方法
先把其中一个str = str + str,拼接起来成
然后判断别一个是否存在新拼接的str中就能实现了。
------解决方案--------------------
最次循环memcmp就解决了,比选择最大子串快多了
如何判断两个循环链表是否相等?如“aabbcc”和"ccaabb"是相等的。请教有什么比较好的算法?
------解决方案--------------------
根据链表构造有向图?
------解决方案--------------------
用双指针
O(N)复杂度
aabbcc 和 ccaabb
i=0, j=0;
i=0, j=1;
i=0, j=2;
i=1, j=3;
i=2, j=4;
i=3, j=5;
i=4, j=0;(j %= str.Length)
一直能将i走到结尾即相等,否则不等
------解决方案--------------------
------解决方案--------------------
把两个循环链表都变成不循环,如aabbcc变成aabbccaabbcc
ccaabb变成ccaabbccaabb
然后判断变化后的两个链表的最大相同字串长度,如果>=n就相同反之...
复杂度参照最大公告字串复杂度
------解决方案--------------------
想到另一个方法
先把其中一个str = str + str,拼接起来成
然后判断别一个是否存在新拼接的str中就能实现了。
------解决方案--------------------
最次循环memcmp就解决了,比选择最大子串快多了