这是一个创建于 3952 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定一个文件，里面有10000个数字，数字只从{1，2，3，4}里面选取。这些数字排成100*100的网格。找出里面序列 1234 以顺时针出现的次数（闭环）。
例子：
3 3 1 2
1 2 3 4
4 3 2 3
1 1 1 4
比如这个例子里面，1234 以顺时针出现了两次。
我能想到的只能是遍历了...大家有什么好的思路么？
例子：
3 3 1 2
1 2 3 4
4 3 2 3
1 1 1 4
比如这个例子里面，1234 以顺时针出现了两次。
我能想到的只能是遍历了...大家有什么好的思路么？
第 1 条附言 · 2014-03-06 00:00:34 +08:00
谢谢大家的回复呀。
决定看下Rabin–Karp algorithm，感觉可以用在这种情况。
决定看下Rabin–Karp algorithm，感觉可以用在这种情况。
22 条回复 • 1970-01-01 08:00:00 +08:00
 |
1
cxe2v 2014-03-05 14:12:42 +08:00
不在一行的顺时针也算么？
|
 |
3
nigelvon 2014-03-05 14:16:52 +08:00
遍历复杂度应该也不高哇。
|
 |
4
ETiV 2014-03-05 14:17:56 +08:00
* * * *
1 2 * * 3 4 * * * * * * 我肉眼只看到了这一个呀, 那个呢? |
 |
5
alsotang 2014-03-05 14:19:28 +08:00
遍历的复杂度是 O(n)的吧，还能少？
|
 |
6
lsylsy2 2014-03-05 14:19:41 +08:00
100*100……遍历也很快吧？
|
 |
8
chenggiant OP |
 |
9
a591826944 2014-03-05 14:22:03 +08:00  1
从 行里面 遍历相邻的两个数字 相加 等于 3/5/7 如果是 记位置，看下一行这个位置的两个数字 是不是能组成符合规则的，如果不是 下一行的这个位置 就不用看了 肯定不行
这样就不用便利全部的矩阵了 |
 |
10
justfindu 2014-03-05 14:26:12 +08:00
@a591826944 这样下一行的这个位置也有可能是下下行的符合要求的~ 还是要遍历的啊
|
 |
11
forestkeeper 2014-03-05 14:59:54 +08:00 1
@alsotang 能的，和kmp算法差不多的方案来剪枝，可以跳着遍历
|
 |
12
binux 2014-03-05 15:30:49 +08:00 1
顺时针，还要闭环，总共就4种可能，这太简单了吧。。
读一行，缓存下一行，如果第一行相邻两个数字满足，判断下一行是否一样满足。O(n)而已 要不我们来改一下，只要4个数字相连（4/8个方向），能组成1234即可，有多少种。 |
 |
13
marklrh 2014-03-05 16:01:59 +08:00
@a591826944 只看相加的值可以么？有可能是逆时针的啊
|
 |
14
shibo501c 2014-03-05 17:50:14 +08:00
感觉可以预处理一下，数组存起来，可以计算四个相邻位置的和，如果是10，就存起来，然后再统一看下是不是顺序的，这样会优化一些吧
|
 |
15
Sdhjt 2014-03-05 17:56:47 +08:00
还是遍历吧，反正复杂度不高
|
 |
16
hongdengdao 2014-03-05 21:29:35 +08:00
开始只要找通过找到1的上边或者右边为2的位置，在这些为2的位置对应的顺时针位置。。。直到找到4
|
|
17
hongdengdao 2014-03-05 21:31:32 +08:00 1
总之只要先找1即可
|
 |
18
acros 2014-03-05 21:40:16 +08:00
最好的情况一时想不到，因为这个要求2x2的，肯定能跳着好些···
|
 |
19
laoyang945 2014-03-06 11:45:51 +08:00
我遇到一个相同的题目，不过是在10000*10000的矩阵里面找一个3*3 的模式出现的次数，该模式正中央那格无需匹配
|
|
20
chenggiant OP @laoyang945 感觉你这个更复杂啊。有想到好的方法么？
|
 |
21
RobinFai 2014-03-06 15:02:16 +08:00
|
 |
22
momou 2014-03-06 18:55:08 +08:00
刚学JS，试着做了下
https://gist.github.com/9387095 |
Select Language