算法力扣刷题记录 十八【383. 赎金信】

前言

哈希篇，继续。
记录 十八【383. 赎金信】

一、题目阅读

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

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

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

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

二、尝试实现

思路

题目的意思：看ransomNote 中的字母有没有在 magazine 出现过，而且出现次数还要满足。比如ransomNote 中两个‘a’，那么magazine 中也得有两个‘a’。（和字母异位词定义一样）

“一个元素有没有在集合中出现过”，第一反应可以哈希法。

• 选择哈希结构。数组？set？map？

  • 提示中说由小写字母组成，就26个，用数组就可以。初始化元素都为0.

• 那么下标索引代表字母顺序，用ASCII码求；元素可以放该字母出现的次数。先遍历magazine ，字母出现一次对应位置就+1.

  • 此时遍历结束元素值代表magazine中字母出现的次数。如果元素==0，说明没有出现过该字母; 如果元素 ==n，说明该字母出现过n次。

• 遍历ransomNote ，先判断元素 == 0，magazine没出现但ransomNote出现，肯定不合题意，直接return false；如果元素不等于0，本次-1，代表用掉一次机会，直到减到0，机会用尽。如果还访问该位置，说明magazine中该字母次数不够，return false。

代码实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> charnum(26,0);	//n个元素，每个元素初始化为0
        for(int i = 0;i < magazine.size();i++){ //每个字母有几次机会可用
           charnum[magazine[i]-'a'] ++;
        }

        for(int i = 0;i < ransomNote.size();i++){

            if(charnum[ransomNote[i]-'a'] == 0){ //代表没有出现过或者次数已经用完
                return false;
            }
            charnum[ransomNote[i]-'a'] --;//用掉一次机会。
        }
        return true;
    }
};

三、代码随想录学习

学习内容

思路一致，只是实现有小区别。但意思一致。

四、总结

题目直接表明：“某元素在该集合中有没有出现过”，可以想到哈希法。

（欢迎指正，转载表明出处）