Re: [問題] 一個演算法相關的問題

看板C_and_CPP作者softwind (software everywhere)時間14年前 (2011/06/09 01:44)推噓1(1推 0噓 3→)

留言4則, 4人參與討論串2/4 (看更多)

※ 引述《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

推

walker2009

06/09 02:56, , 1^F

06/09 02:56, 1^F

→

angleevil

06/09 09:35, , 2^F

06/09 09:35, 2^F

→

softwind

06/09 19:38, , 3^F

06/09 19:38, 3^F