【哈希表算法题记录】383. 赎金信-数组

本文主要是介绍【哈希表算法题记录】383. 赎金信-数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
map的用法：将magazine里字母作为key，出现次数作为value存放在map里，然后遍历ransomNote中的每个字母，首先判断它是否出现在map中，如果在则减去一次其value（可以看作是该字母能够使用的次数），如果不在则返回false。再判断其value是否已经用完，也就是value==-1，那么这次使用是无效的，所以返回false。

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {std::unordered_map<int, int> map;for(int m : magazine){map[m]++;}for(int r : ransomNote){if(map.find(r)==map.end()) return false; //如果字母r不在map中，则返回falsemap[r]--;   //减去一次map[r]的使用值if(map[r] < 0) return false; //如果使用值用完了，那么返回false}return true;}
};

但是这题实际上和242.有效的字母异位词差不多，用map来制作哈希表空间消耗比较大，且费时，这题说了只有小写字母，所以哈希表长度只有26，我们用数组会更加高效：

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int record[26];for(int m : magazine){record[m-'a']++; //记录magazine中每个字母出现次数}for(int r : ransomNote){if(record[r-'a']==0) return false; //如果字母r在record中出现次数为0，则返回falserecord[r-'a']--;}return true;}
};

这篇关于【哈希表算法题记录】383. 赎金信-数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---