代码随想录刷题-哈希表-赎金信

赎金信

本节对应代码随想录中：代码随想录，讲解视频：暂无

昨天写好忘了发到CSDN了o(╥﹏╥)o

习题

题目链接：383. 赎金信 - 力扣（LeetCode）

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

哈希表

这道简单题和之前的有效的字母异位词那题差不多，是写的最快的一道题了。

判断 ransomNote 能不能由 magazine 构成，只需要先遍历下 magazine 将每个字符出现的次数存起来，然后再遍历 ransomNote，遇到每个字符将其计数-1，如果计数小于0说明 ransomNote 中的这个字符比 magazine 的至少多一个，即不能由 magazine 构成。而如果遍历完 ransomNote 也没能找到计数小于0的则说明可以由 magazine 构成。

查找元素那肯定是用哈希表，解题的关键是选择数组、set、map 中的哪一个更优？首先，set 只能存放 key，而我们还要计数，那肯定是不合适的。而题目中说了 ransomNote 和 magazine 由小写英文字母组成，这就说明最多有26个字符，那么用一个26的数组就更合适。当然，也可以用 map，但是 map 要维护哈希表比数组费时，所以数组更优，后面我会给出两种解法的代码和比较。

首先是数组的解法

class Solution {public:bool canConstruct(string ransomNote, string magazine) {int nums[26] = {0};// 先遍历magazine计算每个字符的出现次数for (int i = 0; i < magazine.length(); i++) {nums[magazine[i] - 'a']++;  // 根据-'a'计算相对位置}// 再遍历ransomNotefor (int i = 0; i < ransomNote.length(); i++) {// 先将次数-1,这样如果<0(0-1<0)说明比magazine至少多一个nums[ransomNote[i] - 'a']--;if (nums[ransomNote[i] - 'a'] < 0) {return false;}}return true;}
};

• 时间复杂度：O(n)。其中 N 是 magazine 的长度，因为遍历 magazine 可以花费 O(N) 的时间，并且对于每个字符，可以在常数时间内更新 nums 数组。然后我们再遍历 ransomNote，有 N 个字符，对于每个字符，我们需要常数时间检查 nums 中是否存在当前字符的频率，因此总时间复杂度为O(N)
• 空间复杂度：O(1)。因为 nums 数组的大小始终都是常数级别的 (26)

优化：可以在最前面加一个判断，如果 ransomNote 比 magazine 更长，那一定无法由 magazine 构成，返回 false

map 的解法如下

class Solution {public:bool canConstruct(string ransomNote, string magazine) {unordered_map<char, int> hash_map;// 先遍历magazine计算每个字符的出现次数for (int i = 0; i < magazine.length(); i++) {hash_map[magazine[i]]++;    // 直接将相应元素做为key}// 再遍历ransomNotefor (int i = 0; i < ransomNote.length(); i++) {// 先将次数-1,这样如果<0(0-1<0)说明比magazine至少多一个hash_map[ransomNote[i]]--;if (hash_map[ransomNote[i]] < 0) {return false;}      }return true;}
};

• 时间复杂度：O(n)。其中n是magazine的长度加上ransomNote的长度，因为代码中包含两个for循环，每个循环执行次数不超过输入字符串的长度
• 空间复杂度：O(m)。其中 m 是 magazine 中不同字符的个数。在最坏的情况下，哈希表将包含 magazine 中的全部字符

可以看到两个解法其实就是存的 key 不太一样，数组用相对位置当 key，而 map 直接用对应元素当 key。下面是 LeetCode 两种解法的提交记录，从图中也可以看出数组的解法更优

IT男博客