哈希表：勒索票据 hackerrank

Question

哈罗德是一名绑匪，他写了一张勒索信，但现在他担心通过他的笔迹可以追溯到他。他找到了一本杂志，想知道是否可以从其中剪下整个单词，并用它们来制作一份无法追踪的勒索信复制品。他的笔记中的单词区分大小写，并且他必须仅使用杂志中可用的完整单词。他无法使用子字符串或连接来创建他需要的单词。给定杂志中的文字和勒索信中的文字，如果他可以使用杂志中的整个单词准确地复制勒索信，请打印“是”；否则，打印编号。例如，注释是“黎明袭击”。该杂志只收录了《黎明的袭击》。该杂志的用词全部正确，但有一个大小写不匹配的地方。答案是 。样本输入06 4 今天晚上给我一盛 今天晚上给我一盛 示例输出 0是 样本输入 16 5 二乘三不等于四 二乘二等于四 样本输出 1不我的代码 5/22 测试用例失败:(我不明白为什么 5 失败了。static void checkMagazine(String[] magazine, String[] note) {    int flag = 1;    Map<String, Integer> wordMap = new HashMap<>();    for(String word: magazine) {        if(!wordMap.containsKey(word)) {            wordMap.put(word, 1);        } else            wordMap.put(word,wordMap.get(word)+1);    }    for(String word: note){        if(!wordMap.containsKey(word)){            flag = 0;            break;        }             else wordMap.remove(word, wordMap.get(word));           }    if(flag == 0)        System.out.println("No");    else      System.out.println("Yes");}

Answer 1

这可能是因为当您检索一本杂志时，您不是减少杂志中的单词计数，而是完全删除该单词的所有计数。尝试这个：

for(String word: note){

    if(!(wordMap.containsKey(word) && wordMap.get(word) > 0)){

        flag = 0;

        break;

    } 

    else wordMap.put(word, wordMap.get(word)-1);       

}

Answer 2

wordMap是一个频率表并给出字数。但是，对于注释中的每个单词，您必须减少字数，而不是完全删除该条目。只有当字数达到 0 时才能删除该条目。

另一个问题是区分大小写。根据要求，您可能需要将所有单词转换为小写。

        else {

            wordMap.computeIfPresent(word, (k, v) -> v <= 1? null : v - 1);       

        }

这会检查旧值是否v大于 1，然后减小它，否则返回空值，表示删除该条目。

可以进行频率计数：

Map<String, Integer> wordMap = new HashMap<>();

for(String word: magazine) {

    wordMap.merge(word, 1, Integer::sum);

}

Answer 3

我认为，这个实现更简单

static boolean checkMagazine(String[] magazine, String[] note) {

    List<String> magazineCopy = new ArrayList<>(Arrays.asList(magazine));

    for (String word : note)

    {

        if (magazineCopy.contains(word)) {

            magazineCopy.remove(word);

            continue;

        }

        return false;

    }

    return true;

}

我想你的错误在这里：

else wordMap.remove(word, wordMap.get(word));

您正在从地图中删除该单词，而不是减少此类单词的数量，并且只有当数量达到 0 时，您才应该从地图中删除该单词。

Answer 4

Python解决方案

def checkMagazine(magazine, ransom):

    magazine.sort()

    ransom.sort()

    for word in ransom:

        if word not in magazine:

            flag = False

            break

        else:

            magazine.remove(word)

        flag = True

    if (flag):

        print("Yes")

    else:

        print("No")