今天阿里笔试凉凉，第一题求交流

今天阿里笔试凉凉，第一题求交流。虽然时间结束之后才写完写完，不知道能不能AC，求各位大佬指教。

用的方法比较暴力，可以把给的例子跑出结果来。

不知道还有什么不妥，请各位巨佬，大佬们指教。


import sys

def form_dict(info_lst):
    result_dict = {}
    for info in info_lst:
        if info[0] not in result_dict:
            result_dict[info[0]] = [info]
        else:
            result_dict[info[0]].append(info)
    return result_dict


info = sys.stdin.readline().strip().split(';')
info_dict = {}
for item in info:
    name, content = item.split('_')
    info_dict[name] = content.split('|')

keys = info_dict.keys()
for key in keys:
    info_dict[key] = form_dict(info_dict[key])

order = sys.stdin.readline().strip()
string = order
order = list(order)
result = []
i = 0
while i < len(order):
    for key in keys:
        if order[i] not in info_dict[key]:
            pass
        else:
            length = 0
            res = ''
            for name in info_dict[key][order[i]]:
                if ''.join(order[i: i + len(name)]) == name and len(name) > length:
                    res, length = name,len(name)
            if length > 0:
                result.append([i, i + length, key])
    i += 1


entity = []
status = []
for item in result:
    name = ''.join(order[item[0]: item[1]])
    if name not in entity:
        entity.append(name)
        index = entity.index(name)
    else:
        index = entity.index(name)
    if len(status) > index:
        status[index] += ';' + item[2]
    else:
        status.append(item[2])

for i in range(len(entity)):
    string = string.replace(entity[i], ' {}/{} '.format(entity[i], status[i]))
print(string)

代码运行的结果如下图：
图片说明

全部评论

推荐最新楼层

温酒写bug

Java

题目不一样..

送花回复

发布于 2018-09-07 21:46

李超201806201416200

C++

wordbreak

送花回复

发布于 2018-09-07 21:56

滴滴

校招火热招聘中

官网直投

wissing

算法工程师

import re def process_main3(): row1 = raw_input() datas = {} entity_str_list = row1.split(";") for entity_str in entity_str_list: entity_name, entity_values = entity_str.split("_") entity_value_list = entity_values.split("|") for entity_value in entity_value_list: if datas.has_key(entity_value): datas[entity_value].append(entity_name) else: datas[entity_value] = [entity_name] entity_list = sorted(datas.keys(), reverse=True) row2 = raw_input() words = row2 result = {} tmp_words = words temp_entity = "" count = 1 for entity_value in entity_list: if entity_value in tmp_words: location = re.search(entity_value, words) local_tuple = location.span() if temp_entity == "": temp_entity = entity_value temp_tuple = local_tuple else: result[temp_entity] = datas[temp_entity] tmp_words = tmp_words.replace(temp_entity, "|&{}&|".format(count)) count += 1 temp_entity = entity_value temp_tuple = local_tuple else: if temp_entity != "": result[temp_entity] = datas[temp_entity] tmp_words = tmp_words.replace(temp_entity, "|&{}&|".format(count)) count += 1 temp_entity = "" if temp_entity != "": result[temp_entity] = datas[temp_entity] tmp_words = tmp_words.replace(temp_entity, "|&{}&|".format(count)) final_list = sorted(result.keys(), reverse=True) for index in xrange(len(final_list)): st = ",".join(result[final_list[index]]) new_str = " " + final_list[index] + "/" + st + " " tmp_words = tmp_words.replace("|&{}&|".format(index + 1), new_str) print " ".join(tmp_words.split()) if __name__ == '__main__': # main_process() process_main3() # singer_周杰|周杰伦|刘德华|王力宏;song_冰雨|北京欢迎你|七里香;actor_周杰伦|孙俪 # 请播放周杰伦的七里香给周杰伦周杰孙俪听周杰王力宏

送花回复

发布于 2018-09-07 22:26

金蛇郎君

算法工程师

我的方法也很暴力。。。 # coding=utf-8 import sys # 求特征的最大长度和最短长度 def max_min_ftv_length(features): max = 0 min = 1000 for ftvs in features.values(): for ftv in ftvs: if max < len(ftv): max = len(ftv) if min > len(ftv): min = len(ftv) return max, min # 最大正向匹配 def max_length_fit(fts, seq, mxfl, mnfl): res_seq = '' num = 0 # 统计实体属于特征类型的种类数 mid = 0 for i in range(len(seq)): left = right = 0 if i+mxfl<len(seq) and i+mnfl<len(seq): left = i + mnfl right = i + mxfl + 1 elif i+mxfl>=len(seq) and i+mnfl<len(seq): left = i + mnfl right = len(seq) + 1 else: continue if(num != 0): #说明已经匹配到输入字符串最右端 break; #print(left,right) for j in range(left,right):# 只对特征最小长度到最大长度的区间进行搜索 #print(i,j,seq[i:j]) for ftk in fts.keys(): if num==0:# 判定条件1：当前字符串能够匹配特征，多加一个字符就匹配不上，便是最大匹配 # 判定条件2：当前字符串能够匹配特征，且已经到输入字符串最右端，便是最大匹配 if (seq[i:j] in fts[ftk] and j!=len(seq) and seq[i:j+1] not in fts[ftk]) or (seq[i:j] in fts[ftk] and j==len(seq)): res_seq = res_seq + seq[mid:i] + ' ' + seq[i:j] + '/' + ftk num = num + 1 mid = j elif (seq[i:j] in fts[ftk] and j!=len(seq) and seq[i:j+1] not in fts[ftk]) or (seq[i:j] in fts[ftk] and j==len(seq)): res_seq = res_seq + ',' + ftk if num != 0 and j!=len(seq): #print('num',num,'j',j) res_seq = res_seq + ' ' num = 0 break; if mid != len(seq)-1: res_seq = res_seq + seq[mid:] return res_seq if __name__ == '__main__': #feature = sys.stdin.readline().strip() #sequence = sys.stdin.readline().strip() feature = "singer_周杰|周杰伦|刘德华|王力宏;song_冰雨|北京欢迎你|七里香;actor_周杰伦|孙俪" sequence = "请播放周杰伦的七里香给周杰伦周杰孙俪听周杰王力宏" features = {} feature = feature.split(';') for ft in feature: ft = ft.split('_') features[ft[0]] = ft[1].split('|') mxfl, mnfl = max_min_ftv_length(features) result = max_length_fit(features, sequence, mxfl, mnfl) print(result)

送花回复

发布于 2018-09-07 22:42

求杭州收留

C++

同样交卷了才写完 what the *** whatever # -*- coding=utf-8 -*- import sys from collections import defaultdict def main(string, word): res = defaultdict(list) for item in word: if string.startswith(item): length = len(item) res[item].append(item) process(string[length:], word, res[item]) return get_best(res) def process(string, word, res_item): if string == '': return for item in word: if string.startswith(item): length = len(item) res_item.append(item) process(string[length:], word, res_item) def get_best(res): values = res.values() max_sum = (0, 0) for item in values: cur_sum = 0 for _ in item: cur_sum += len(_) ** 2 max_sum = (cur_sum, item) if max_sum[0] < cur_sum else max_sum return ' '.join(max_sum[-1]) if __name__ == "__main__": # string = sys.stdin.readline().strip() # n = int(sys.stdin.readline().strip()) # word = [] # for i in range(n): # word.append(sys.stdin.readline().strip()) string = 'asdfjkl' word = ['as', 'asd', 'df', 'fjkl', 'jkl'] print(main(string, word))

送花回复

发布于 2018-09-07 22:43

金蛇郎君

算法工程师