作者uranusjr (←这人是超级笨蛋)
看板Python
标题Re: [讨论] 用python找出一串数字中最长的"二数数串"
时间Thu Sep 26 15:02:17 2013
我前阵子 (PyConTW 的时候) 才知道 collections 有一个很 IMBA 的东西叫 Counter
import sys
from collections import Counter
numstr = sys.argv[-1] # 这里读入要算的字串
matches = ['']
for start in range(len(numstr)):
for end in range(start + 1, len(numstr) + 1):
substring = numstr[start:end]
counter = Counter(substring)
if len(counter) != 2:
continue
if len(matches[0]) < len(substring):
matches = [substring]
elif len(matches[0]) == len(substring):
matches.append(substring)
print('{count} matches (of length {length}):'
.format(count=len(matches), length=len(matches[0])))
for match in matches:
print match
浅显易懂
※ 引述《dadadavid (大大大卫)》之铭言：
: numstring = "889988899278392520771323543282829292222943485709"
: def ngram(n, iter_tokens):
: """Return a generator of n-gram from an iterable"""
: z = len(iter_tokens)
: return (iter_tokens[i:i+n] for i in xrange(z-n+1))
: for i in range(len(numstring), 1, -1):
: results = [ng for ng in ngram(i, numstring) if len(set(ng))==2]
: if len(results) > 0:
: print results
: break
: ※ 引述《mystea (mystea)》之铭言：
: : 这是一个软体公司过往的面试题目.
: : 给定一个任意的数串, 比方说:
: : numstring = '889988899278392520771323543282829292222943485709'
: : 请用python找出最长的, 只有两种数字的子数列. 在前述的例子里,
: : 答案是889988899 和 292922229.
: : 我个人的解答如下:
: : numstring = '889988899278392520771323543282829292222943485709'
: : slen = len(numstring)
: : candidate={}
: : length_of_string=[]
: : next_i = 0
: : start_index=[]
: : ii=0
: : while (next_i + ii != slen-1):
: : record = True
: : candidate = {}
: : start_index.append(next_i)
: : for ii, j in enumerate(s[next_i:]):
: : if j in candidate: candidate[j] += 1
: : else: candidate[j] = 1
: : if (len(candidate) == 2 and record):
: : next_i += ii
: : record = False
: : if len(candidate) > 2: break
: : length_of_string.append(ii+1)
: : smax = max(length_of_string)
: : sstarts = [start_index[i] for i in range(len(length_of_string)) if length_of_string[i]==smax]
: : finalresult = [s[a:a+smax-1] for a in sstarts]
: : print(finalresult)
: : 想请教版友们有没有其他的方法? 另外, 由於我台接触python不久, 想请问我的
: : 方法是否有多余的地方? 谢谢.
--
"问おう、贵方が私のマスターか？"
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.94.57
※ 编辑: uranusjr 来自: 140.112.94.57 (09/26 15:03)
1F：推 dadadavid:Counter的确很好用,但是len(counter)==len(set), 09/26 15:32
2F：→ dadadavid:用counter就多余了 09/26 15:33
3F：→ uranusjr:但是 dict 不会自己帮你 group, 还要另外实作 09/26 16:08
4F：推 dadadavid:我是拿Counter和set比,不是跟dict比, 09/26 16:22
5F：→ dadadavid:而且这题用不到group啊~~ 09/26 16:22