http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx问题 假设有4×4的方阵（里面可放字符串），给现定一个序列，检查这个序列是否在方阵的“连续对角线”上面： 例如：从左上到右下的连续对角线序列可能是： 1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16 1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16 分析 刚刚看到此题目，可能有点晕，“连续对角线”是啥？仔细一看，其实就是方阵里面的曲线序列（如下图），我就叫它“方曲序列”吧。 再一想，这样的序列应该有8条。考试的时候时间紧，只能大概写写思路了，回来用VS08调试着搞感觉好很多:(CommunityServer 2.1 SP2 (Build: 61120.2)http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx#1322Mon, 28 Dec 2009 16:31:49 GMT97d5f9e5-5fdb-457a-82c8-4eed578e0215:1322hhb<p>强人，先膜拜一下。。</p> <p>看完以后想到一个小问题。。</p> <p>给定一个整数n，事实上可以在O(1)的时间内找到它在序列中的位置的。</p> <p>给定序列中的某个元素，可以在O(1)时间及空间内找到它的下一个元素的。</p> <p>因此若要判定一个长为n的序列是否在连续对角线上，存在O(n)的算法。而这显然是理论复杂度下限……</p> http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx#1326Mon, 28 Dec 2009 17:46:51 GMT97d5f9e5-5fdb-457a-82c8-4eed578e0215:1326hhb<p>并行处理8种方向其实并不能提高性能。因为前两项一定能唯一确定一种可能的方向。</p> http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx#1327Tue, 29 Dec 2009 02:21:33 GMT97d5f9e5-5fdb-457a-82c8-4eed578e0215:1327hhb<p>嗯。。只针对里面按顺序放数字的情况……放的是随机字符串就没办法了。。</p> http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx#1328Tue, 29 Dec 2009 02:30:40 GMT97d5f9e5-5fdb-457a-82c8-4eed578e0215:1328hhb<p>随机数据情况下比较好的方法可能还是预处理hash矩阵中的数据。每次找到子串中每个元素出现的位置，得到坐标序列。验证坐标序列是否为方曲序列。</p> <p>预处理需要平方的复杂度，不过对每个子串保持线性。。</p> http://yishan.cc/blogs/gpww/archive/2009/11/04/1274.aspx#1329Tue, 29 Dec 2009 02:34:47 GMT97d5f9e5-5fdb-457a-82c8-4eed578e0215:1329hhb<p>。。。如果还包含重复字符串，那就没法了。。。假设字符串重复得很少好了。。。。</p>