哈希算法

哈希算法

• 什么是哈希：哈希及哈希的原理
• 两个数的和：快速寻找两个数的和
• 单词模式匹配：简单的模式匹配问题

一.两个数的和

from IPython.display import Image
Image(filename="./data/3_01.png",width=800,height=960)

原始方法

def twoSum(nums,target):
    # 存放结果编号数据
    res=[]
    # 深拷贝,把原数据复制到newnums里
    newnums=nums[:]
    # 对新数组排序
    newnums.sort()
    left=0
    right=len(newnums)-1
    
    while left<right:
        if newnums[left]+newnums[right]==target:
            for i in range(0,len(nums)):
                if nums[i]==newnums[left]:
                    res.append(i)
                    break
                for i in range(len(nums)-1,-1,-1):
                    if nums[i]==newnums[right]:
                        res.append(i)
                        break
            res.sort()
            break
        elif newnums[left]+newnums[right]<target:
            left=left+1
        elif newnums[left]+newnums[right]>target:
            right=right-1
    return (res[0]+1,res[1]+1)

nums=[3,7,10,4,5]
target=11
twoSum(nums,target)

(2, 2)

哈希算法

def twoSum(nums,target):
    dict={}
    for i in range(len(nums)):
        # 待查询数字
        m=nums[i]
        # target-m是否在字典中
        if target-m in dict:
            # 如果已存在,则返回这两个数的下标
            return (dict[target-m]+1,i+1)
        # 如果不存在则记录键值对
        dict[m]=i

twoSum(nums,target)

(2, 4)

三.单词模式匹配

def wordPattern(wordPattern,input):
    word=input.split(" ")
    if len(word)!=len(wordPattern):
        return False
    
    hash={}
    used={}
    
    for i in range(len(wordPattern)):
        if wordPattern[i] in hash:
            if hash[wordPattern[i]]!=word[i]:
                return False
        else:
            if word[i] in used:
                return False
            hash[wordPattern[i]]=word[i]
            used[word[i]]=True
    return True

三.猜词游戏

Image(filename="./data/3_02.png",width=800,height=960)

def getHint(secret,guess):
    secret_dict={}
    guess_dict={}
    
    A=0
    B=0
    
    for i in range(len(secret)):
        if secret[i]==guess[i]:
            A+=1
        else:
            if secret[i] in secret_dict:
                secret_dict[secret[i]]=secret_dict[secret[i]]+1
            else:
                secret_dict[secret[i]]=1
            if guess[i] in guess_dict:
                guess_dict[guess[i]]=guess_dict[guess[i]]+1
            else:
                guess_dict[guess[i]]=1
                
    for digit in secret_dict:
        if digit in guess_dict:
            B+=min(secret_dict[digit],guess_dict[digit])
    return str(A)+"A"+str(B)+"B"

secret="1123"
guess="9111"
getHint(secret,guess)

'1A1B'