推 walker2009:嗯~ 這就是 O(A*B) 的作法~ 謝囉:D 06/09 02:56
→ angleevil:= =感覺是patterm mining 06/09 09:35
→ softwind:明明就O(A) 跟B有關係嗎? 06/09 19:38
→ suhorng:因為pattern不是固定 "x--x" 06/09 20:02
※ 引述《walker2009 (不害怕。不後悔)》之銘言：
: 給個例子
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
: 如果 T = X - - - X - X X - - X X - - -
: P = X - - X
: ( - 表示任意非 X 字元)
: 我們求出來的解是 1, 2, 4, 5, 7, 8, 9, 11, 12 這幾個位置
: 因為當 P shift 到這幾個位置時, 都會有 X 對上 X 的情況
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
: T = X - - - X - X X - - X X - - -
: 1 P = X - - X
: 2 X - - X
: 4 X - - X
: 5 X - - X
: 7 X - - X
: 8 X - - X
: 9 X - - X
: 11 X - - X
: 12 X - - X
: 當然最暴力的做法的時間複雜度會是 O(A*B)
嗯~ 我先說 我演算法不熟~ so 我就略過你的 落落長需求...
直接看你給的例子
如果你的pattern 真的不會動 那這個問題 應該不是太難~
P = X - - X 如果你只考慮 左邊的X會"勾到"
那 答案是 1 4 5 7 8 11 12 很OK 反正就照抄就是了
then ...
考慮右邊的 X 會勾到... 那會勾到的點 就是 T的位置 -3
so 對照 左邊勾倒的點 1 4 5 7 8 11 12
右邊會勾到的點是 -2 1 2 4 5 8 9
把這兩個數列作聯集 你會得到
-2 1 2 4 5 7 8 9 11 12 去掉 -2(不合理)
好像就是你要的答案了...
不確定是不是你要的東西...
Ruby sample code:
my_set = Set.new
pos_x_of_T.each{ |t|
my_set << t
my_set << t-3
}
my_set.remove_if{ |x|
x<0
}
基本上 應該可以一對一轉成 STL...
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.120.96