哈希算法--猜数字游戏

1.题目要求

输入两个位数相同的数，判断对应位置的数字是否相等，返回两个数。第一个数是数字和位置完全猜对的数字个数，第二个数是数字大小猜对但位置不对的数字个数

2.逐步编程

2.1 定义函数

def g(secret,guess):sec_dic={}gue_dic={}# 定义两个字典，记录每个数组中数字出现的个数count1=0# 记录完全才对的数的个数count2=0# 记录大小猜对但位置不对的个数

2.2 遍历判断

    for i in range(len(secret)):if secret[i]==guess[i]:count1+=1# 如果位置和大小对应相等，count1数量加1else:if secret[i] in sec_dic:sec_dic[secret[i]]+=1# 若该数字包含在字典中，计数加1else:sec_dic[secret[i]]=1# 否则在字典中新建此数，初始数量为1if guess[i] in gue_dic:gue_dic[guess[i]]+=1else:gue_dic[guess[i]]=1

2.3 对count2取值

对于秘密数字1123，猜测数字9111 ，count2的数字为1。为什么呢？在秘密数字中，第2个已经算作全对的数量，而第1个数字1只能和猜测数字中的两个1中的某个对应，也就是说，最终只是数字对的数量是由该数在秘密数字中和在猜测数字中更小的那一个决定。为此，只需要记录秘密数字和猜测数字中未匹配的数字和它的个数，之后看相同数字的最小数即可。

    for j in sec_dic:if j in gue_dic:# 此数在两个字典中都存在count2+=min(sec_dic[j],gue_dic[j])return str(count1)+','+str(count2)

3.完整代码

def g(secret,guess):sec_dic={}gue_dic={}count1=0count2=0for i in range(len(secret)):if secret[i]==guess[i]:count1+=1else:if secret[i] in sec_dic:sec_dic[secret[i]]+=1else:sec_dic[secret[i]]=1if guess[i] in gue_dic:gue_dic[guess[i]]+=1else:gue_dic[guess[i]]=1for j in sec_dic:if j in gue_dic:count2+=min(sec_dic[j],gue_dic[j])return str(count1)+','+str(count2)
print(g([1,2,2,2,1,1],[8,2,1,1,0,0]))

4.过程解析

def g(secret,guess):sec_dic={}gue_dic={}count1=0count2=0for i in range(len(secret)):if secret[i]==guess[i]:count1+=1else:if secret[i] in sec_dic:sec_dic[secret[i]]+=1print(sec_dic,'sec_dic')else:sec_dic[secret[i]]=1print(sec_dic,'sec_dic')if guess[i] in gue_dic:gue_dic[guess[i]]+=1print(gue_dic,'gue_dic')else:gue_dic[guess[i]]=1print(gue_dic,'gue_dic')for j in sec_dic:if j in gue_dic:count2+=min(sec_dic[j],gue_dic[j])return str(count1)+','+str(count2)
print(g([1,2,2,2,1,1],[8,2,1,1,0,0]))# {1: 1} sec_dic
# {8: 1} gue_dic
# {1: 1, 2: 1} sec_dic
# {8: 1, 1: 1} gue_dic
# {1: 1, 2: 2} sec_dic
# {8: 1, 1: 2} gue_dic
# {1: 2, 2: 2} sec_dic
# {8: 1, 1: 2, 0: 1} gue_dic
# {1: 3, 2: 2} sec_dic        # 1的数量为3个
# {8: 1, 1: 2, 0: 2} gue_dic  # 1的数量为2个，返回最小值
# 1,2