作者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