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 |