Leecode刷题 383.赎金信——哈希表

题目：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ransom-note
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

哈希表

生动的理解哈希表
哈希表（散列表）原理详解

百度百科：
“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值，这个值就是数据存放的位置，我们就可以根据这个值快速的找到我们想要的数据，哈希表本质上就是一个数组，只不过数组存放的是单一的数据，而哈希表中存放的是键值对（key - value pair）。

键值对和Entry

哈希表本质上是个数组，难道就跟数组的基本使用那样，存个数值，然后通过下表读取之类的嘛？当然不是啦，对于哈希表，它经常存放的是一些键值对的数据，啥是键值对啊，就是我们经常说的key-value啊，简单点说就是一个值对应另外一个值，比如a对应b，那么a就是key，b是value，哈希表存放的就是这样的 键值对 ，在哈希表中是通过哈希函数将一个值映射到另外一个值的，所以在哈希表中，a映射到b，a就叫做键值，而b呢？就叫做a的哈希值，也就是hash值。

如何存储数据

哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是用来确定这个Entry要存放在哈希表中的位置的，实际上这个值就是一个下标值，来确定放在数组的哪个位置上。数组中1的位置存放的是一个Entry，它不是一个简单的单个数值，而是一个键值对，也就是存放了key和value。我们经过哈希函数计算得出的1只是为了确定这个Entry该放在哪个位置而已。

哈希冲突

主要讲了hash冲突

题目对应

放到这个题里，先附上解法：

bool canConstruct(char * ransomNote, char * magazine)
{
    //使用哈希表的方式解决
    int hash[26] = {0};
    for(int i = 0;magazine[i] != '\0';i++)
        hash[magazine[i] - 'a']++;
    for(int i = 0;ransomNote[i] != '\0';i++)
    {
        if(hash[ransomNote[i] - 'a']-- == 0)//先判断，再--，所以不会跳过相等的时候
            return false;
    } 
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

bool canConstruct(char * ransomNote, char * magazine){
    //先判断数量，如果目标数组长度大于源数组，return false
    int r = strlen(ransomNote);
    int m = strlen(magazine);
    if(r > m)
        return false;
    //如果r <= m，通过一个26位的数组，每位代表这个字母出现在两个字符串中的次数，
    // 在r中出现就加1，在m中出现就减1，即看26个字母出现在目标数组中的字母对应的个数和同样的提供方数组的元素的个数，前者是正数后者是负数
    int ans[26] = {0};
    for(int i = 0;i < r;i++)
    {
        ans[ransomNote[i] - 'a']++;
        ans[magazine[i] - 'a']--;
    }
    //在判断一下r是不是小于m，就需要对m多出来的几位额外的处理
    if(r < m)
    {
        for(int i = r;i < m;i++)
            ans[magazine[i] -'a']--; 
        //这么写是错误的，可能会越界，超出数组范围
        // for(int i = m;i > r;i--)
        //     ans[magazine[i] -'a']--; 
    }
    //检测是不是数组的元素有大于0的，只要有1个大于0，就说明源数组中没有这个字母
    for(int i = 0;i < 26;i++)
    {
        if(ans[i] > 0)
            return false;
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

1. 键值：就是字符串中的单个字母，也即magzine[i]和ransomNote[i]
2. hashfunction，哈希函数：要将键值转换为数组的下标，也即：magazine[i] -‘a’ 和 ransomNote[i] - ‘a’
3. value值：也就是单个字母的匹配个数，value值大于0（针对第二种解法）就说明不能满足题目要求。