2018-08-22 华为笔试3-DNA最长重复序列

image.png
image.png

from collections import Counter

def slice_window(one_str,w=1):
  res_list=[]
  for i in range(0,len(one_str)-w+1):
    res_list.append((one_str[i:i+w],i))
  return res_list


def main_func(one_str):
  all_sub=[]
  for i in range(1,len(one_str)):
    newString = slice_window(one_str,i)
    for newSubString in newString:
        flag = True
        for subString in all_sub:
             if subString[0] == newSubString[0] and subString[1] + len(subString[0]) > newSubString[1]:
                 flag = False
        if flag == True:
            all_sub.append(newSubString)

  all_sub = [i[0] for i in all_sub]

  res_dict={}

  threshold=Counter(all_sub).most_common(1)[0][1]

  slice_w=Counter(all_sub).most_common(1)[0][0]

  for one in all_sub:

    if one in res_dict:

      res_dict[one]+=1

    else:

      res_dict[one]=1

  for key in list(res_dict):
       if res_dict[key] == 1:
           res_dict.pop(key)


  sorted_list=sorted(res_dict.items(), key=lambda e:(len(e[0]),e[1]),reverse=True)

  print(sorted_list[0][0]," ",len(sorted_list[0][0]))




if __name__ == '__main__':

  one_str='AGCTAGCT'

  two_str='abcabcabd'

  three_str='bbbbbbb'

  main_func(one_str)

  main_func(two_str)

  main_func(three_str)

借鉴了这位大兄弟的代码：http://www.erongda.com/dynamic.html?id=232 非常感谢。
一个半小时才做了一道题T_T