Re: [討論] 用python找出一串數字中最長的"二數數串"

看板Python作者darkgerm (黑駿)時間12年前 (2013/09/26 20:36)推噓8(8推 0噓 0→)

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

※ 引述《mystea (mystea)》之銘言： : 這是一個軟體公司過往的面試題目. : 給定一個任意的數串, 比方說: : numstring = '889988899278392520771323543282829292222943485709' : 請用python找出最長的, 只有兩種數字的子數列. 在前述的例子裡, : 答案是889988899 和 292922229. 保留題目~ 上面的解法都是 O(n^2)，但這題其實有 O(n) 解概念與 "最大連續整數合" 的題型很像以下是我的解法，如果有 bug 也請大家不吝指正！演算法：用 i 走過 numstring 一次，在走訪時要維護 diff1_ptr: 從 i 往前的第一個不同數字的起始位置 diff2_ptr: 從 i 往前的第二個不同數字的起始位置 num_set: 從 i 往前到 diff2_ptr 間的數字 (必定只有 2 個) num_set 是維護 diff1_ptr diff2_ptr 用的 [diff2_ptr: i+1] 一定會是一個合法字串，沿途記錄最大即可 ex: 7 7 9 9 9 8 8 7 8 8 8 5 #1 7 1 <-- 1 表示 diff1_ptr 位置 2 表示 diff2_ptr 位置 #2 7 7 1 #3 7 7 9 2 1 <-- diff2_ptr 到 "現在走訪到的位置" 因此 779 會是一個合法子字串 #4 7 7 9 9 2 1 #5 7 7 9 9 9 2 1 <-- 此時的合法字串為 77999 比以前都長所以會被記錄下來 #6 7 7 9 9 9 8 2 1 <-- 8 不在之前的 set 裡(79) 所以 ptr 會換位置，此時合法字串是 9998 #7 7 7 9 9 9 8 8 2 1 #8 7 7 9 9 9 8 8 7 2 1 <-- 在 ptr 換位前，合法字串是 99988 只有跟 77999 同長而已 #9 7 7 9 9 9 8 8 7 8 2 1 #10 7 7 9 9 9 8 8 7 8 8 2 1 #11 7 7 9 9 9 8 8 7 8 8 8 2 1 <-- 此時合法字串是 887888，比 99988 更長因此答案更新 #12 7 7 9 9 9 8 8 7 8 8 8 5 2 1 <-- 結束於是在走訪時會有三種狀況： 1. aabbb c 走到一個以前沒出現過的字 2 1 現在走到 c 與前一個元素 b 不同，因此 diff1_ptr 要更新到 c 的位置因為 c 以前沒出現過(和 a 不同)，因此 diff2_ptr 也要更新而 diff2_ptr 新的位置就會是 diff1_ptr 舊的位置，也就是變成 aabbbc 2 1 2. aabbb b 走到跟上個一樣的字 2 1 毫無反應，diff1_ptr diff2_ptr 皆不用更新 3. aabbb a 走到跟上個不同的字，但以前出現過 2 1 跟上次不同 diff1_ptr 就一定會更新，但沒有出現新字所以 diff2_ptr 不用動如此做是為了讓接下來如果出現新字，diff2_ptr 更新時可以一口氣丟掉有 b 的部份(遇到新字就是狀況 1，diff2_ptr 會更新到 diff1_ptr 的位置) aabbba 2 1 講了半天，以下是 code numstring = "889988899278392520771323543282829292222943485709" ans = [''] num_set = set() diff2_ptr, diff1_ptr = 0, 0 for i in range(len(numstring)): if numstring[i] not in num_set: # cond 1 diff2_ptr, diff1_ptr = diff1_ptr, i num_set = set([numstring[i], numstring[diff2_ptr]]) elif numstring[i] == numstring[i-1]: # cond 2 pass else: # cond 3 diff1_ptr = i # replace ans if longer if i+1 - diff2_ptr > len(ans[0]): ans = [ numstring[diff2_ptr:i+1] ] # append to ans if equal long elif i+1 - diff2_ptr == len(ans[0]): ans.append( numstring[diff2_ptr:i+1] ) print ans -- 光明的背後是黑暗黑暗的背後還是黑暗由此可知黑暗 > 光明 Q.E.D. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.235.135