时间戳

首页 > 解决方案 > 哈希表：赎金票据（超过时间限制）

python - 哈希表：赎金票据（超过时间限制）

问题描述

哈罗德是一个绑匪，他写了一张赎金单，但现在他担心会通过他的笔迹追溯到他。他找到了一本杂志，想知道他是否可以从中剪下整个单词，并用它们来制作一份无法追踪的赎金记录复制品。他的笔记中的单词是区分大小写的，他只能使用杂志中可用的整个单词。他不能使用子字符串或连接来创建他需要的单词。

给定杂志上的文字和赎金信中的文字，如果他能准确地使用杂志上的整个文字复制他的赎金信，则打印 Yes；否则，打印编号。

示例 =“黎明攻击”=“黎明攻击”

杂志上的字都是对的，但有一个大小写不匹配的地方。答案是 。

功能说明

在下面的编辑器中完成 checkMagazine 功能。如果可以使用杂志形成便笺，则必须打印，或者。

checkMagazine 有以下参数：

字符串杂志[m]：杂志中的单词字符串注释[n]：赎金票据中的单词打印

string: 或者 , 没有返回值 输入格式

第一行包含两个以空格分隔的整数， 和 ，分别是 和 中的单词数。第二行包含空格分隔的字符串，每个 . 第三行包含以空格分隔的字符串，每个 .

约束

. 每个单词都由英文字母组成（即 to 和 to ）。样本输入 0

6 4 今天晚上给我一个盛大今天给一个盛大样本输出 0

是 样本输入 1

6 5 二乘三不是四 二乘二是四 采样输出 1

无解释 1

“二”在杂志中只出现一次。

样本输入 2

7 4 我得到了一堆可爱的椰子 我得到了一些椰子 样本输出 2

不

解释2

哈罗德的杂志没有这个词。

# Complete the checkMagazine function below.
def checkMagazine(magazine, note):
    hash_table = [[] for _ in range(5)]
    test=0
    for a in magazine:
        length=len(a)
        key=(length-1)%5
        hash_table[key].append(a)
    for a in note:
        key=(len(a)-1)%5
        
        if a not in hash_table[key]:
            test=1
            break
        else:
            hash_table[key].remove(a)
    if test==1:
        print("No")
    else:
        print("Yes")

我的案例 16 和 17 超出了我的时间限制。请帮助如何改进它

标签： pythondata-structureshashtable

解决方案

介绍 Python 计数器

来自文档： Counter 是dict用于计数hashable对象的子类。它是一个集合，其中元素存储为字典键，它们的计数存储为字典值。

from collections import Counter

def checkMagazine(magazine, note):
    magazine_counter = Counter(magazine)
    note_counter = Counter(note)
    return "Yes" if magazine_counter & note_counter == note_counter else "No"

两个计数器之间的逻辑&将为您提供相应计数的最小值。将结果与note您想要的结果进行比较。

推荐阅读