请设计一个算法,给一个字符串进行二进制编码,使得编码后字符串的长度最短。
数据范围:字符串长度满足 ,本题有多组输入
import sys a = [] for line in sys.stdin: a += line.split() result = [] for item in a: temp = [] hashmap = {} # 字典转列表然后升序排序 for code in list(item): if code in hashmap: hashmap[code] += 1 else: hashmap[code] = 1 temp += sorted(hashmap.items(), key=lambda s: s[1]) # 列表转字典,并清空权重 b = temp.copy() for i in range(len(b)): b[i] = (b[i][0],0) b = dict(zip([x[0] for x in b], [x[1] for x in b])) # temp:value升序的元组列表 # b:1权重字典 def search(kv): # 输入元组列表,输出最小元组 min = kv[0][1] char = kv[0][0] index = 0 for i in range(len(kv)): if kv[i][1]<= min: min = kv[i][1] char = kv[i][0] index = i kv.pop(index) return min, char def hfm(): #哈夫曼树主体,选择value最小的节点, while len(temp) != 1: t1,c1 = search(temp) t2,c2 = search(temp) for any in c1: b[any] += 1 for any in c2: b[any] += 1 temp.append((c1+c2,t1+t2)) hfm() # 此时b是树权重字典 count = 0 for code in list(item): count += b[code] print(count)