hash算法的应用

发布时间：2020-12-20 09:51:12 所属栏目：Python 来源：网络整理

导读：一、单词模式匹配描述：单词模式字符串为“一二二一”，目标字符串为"苹果香蕉香蕉苹果"则匹配成功 a=[1,2,1,3 ]b =[ ' x ' , y z ' ] def word_pattern(a,b): # 如果a,b长度不一致则直接返回False if len(a)!= len(b): return False 用来存储映射关系

一、单词模式匹配

描述：单词模式字符串为“一二二一”，目标字符串为"苹果香蕉香蕉苹果"则匹配成功

a=[1,2,1,3]
b=['x',yz']
def word_pattern(a,b):
    #如果a,b长度不一致则直接返回False
    if len(a)!=len(b):
        return False
    用来存储映射关系
    例如{1:'x',2:'y',3:'z'}
    hash={}
    用来存储是否被使用
    如果a=[1,2],b=['x','y','z']
    那么1:'y'就重复使用了，就返回False
    used=for i in range(len(a)):
        if a[i]  hash:
            不是第一次出现，检查映射关系是否匹配
            if hash[a[i]]!=b[i]:
                 False
        else:
            检查这个单词是否使用过，使用过则返回False
            if b[i]  used:
                 False
        hash[a[i]]=b[i]
        used[b[i]]=True
     True
print(word_pattern(a,b))

?二、猜词游戏

比如秘密数字“2018”,猜测数字"8021"，我们可以看到0位置猜对了，我们记为A，其余数字虽然猜对了但是位置不对，我们每个记为B，输出则有1A3B；

在比如秘密数字“1123”，猜测数字“9111”，我们发现猜测数字第二个数字与秘密数字相匹配，于是我们有1A，匹配的数字就不会再被使用，由于还有1，所以我们有1B，最终我们返回1A1B；（注意，我们保证的是秘密数字和猜测数字的位数是一致的）

解法：对于A的个数，我们直接判断有多少位是相等的即可，对于B的判断，我们只需要每次取得匹配的最小的数目即可；

a="1123"
b=9111"
 gethint(a,b):
    A=0
    B=0
    a_dict={}
    b_dict=if b[i] == a[i]:
            A+=1
         b_dict:
                b_dict[b[i]]=b_dict[b[i]]+1
            :
                b_dict[b[i]]=1
             a_dict:
                a_dict[a[i]] = a_dict[a[i]] + 1
            :
                a_dict[a[i]]=1
    for digit  b_dict:
        if digit  a_dict:
            B+=min(a_dict[digit],b_dict[digit])
    return str(A)+A"+str(B)+Bprint(gethint(a,b))
输出：1A1B

三、神奇的词根

问题描述：给定一个由许多词根组成的字典和一个句子，你需要将句子的所有继承词用词根替换掉，如果继承词中有许多它的词根，则用最短的词根来替换掉它；

方法一：直接暴力法

a=[catt",1)">catbatrat,]
b=the cattle was rattled by the battery replacewords(a,b):
    b=b.split(" )
     a:
        for j  range(len(b)):
            if b[j][:len(i)]==i:
                b[j]=i
    return .join(b)
print(replacewords(a,b))

方法二：利用hash

a=[import collections
    b=b.split()
    a_dict=collections.defaultdict(set)
    b_dict=collections.defaultdict(int)
    for w  a:
        a_dict[w[0]].add(w)
        b_dict[w[0]]=max(b_dict[w[0]],len(w))
    (a_dict,b_dict)
    for i,w  enumerate(b):
         range(b_dict[w[0]]):
            if w[:j+1]  a_dict[w[0]]:
                b[i]=w[:j+1]
                break
    ".join(b)

a_dict：defaultdict(<class 'set'>,{'c': {'cat','catt'},'b': {'bat'},'r': {'rat'}})

b_dict：defaultdict(<class 'int'>,{'c': 4,'b': 3,'r': 3})

输出：the cat was rat by the bat

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!