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