作者darkgerm (黑駿)
看板Python
標題Re: [討論] 用python找出一串數字中最長的"二數數串"
時間Thu Sep 26 20:36:24 2013
※ 引述《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
1F：推 carlcarl:Good~ 09/27 00:36
2F：推 dadadavid:這裡有資工魂 09/27 08:26
3F：推 s0914714:解法真棒!不過#4 diff1_ptr的位置應該在第一個9吧? 09/27 11:15
恩恩標錯了XD 已修正，感謝提醒!
※ 編輯: darkgerm 來自: 140.113.235.135 (09/27 11:16)
4F：推 s860134:演算法上的勝利阿! 09/27 18:39
5F：推 mystea:謝謝大家的熱情回應, 獲益良多. :) 09/27 23:48
6F：推 cobrasgo:這就是value 09/28 13:55
8F：推 jlhc:感謝 09/30 01:35