leetcode每天5题-Day31

哈希碰撞的两种解决办法：拉链法和线性探测法。
常见的三种哈希结构：数组、set(集合)、map(映射)。
空间换时间：要使用额外的数组，set或者是map来存放数据

1.有效的字母异位词

242. 有效的字母异位词-简单
b站视频-代码随想录
数组在哈希表里的经典应用
①数组作哈希
数组其实就是一个简单的哈希表，定义数组hash来记录字符串s里字符出现的次数，数组长度为26，初始化为0。在这里，字符a映射为下标0，相应的字符z映射为下标25。
什么时候用数组？
当哈希值比较小，范围可控且比较小，就用数组。

var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
    // hash记录每个字符出现的频率
    const hash = new Array(26).fill(0);

    let base = "a".charCodeAt();

    for(const c of s){
        hash[c.charCodeAt() - base]++;
    }
    for(const c of t){
        hash[c.charCodeAt() - base]--;
    }
    for(let k = 0;k < 26;k++){
        if(hash[k] !== 0) return false;
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度为O(n)
空间复杂度为O(1)，因为空间上定义的是一个常量大小的辅助数组。
②排序

var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};

1
2
3
4

2.赎金信

383. 赎金信-简单
跟1.有效的字母异位词这道题思路一模一样

var canConstruct = function(ransomNote, magazine) {
    const hash = new Array(26).fill(0);
    let base = "a".charCodeAt();
    for(const c of magazine){
        hash[c.charCodeAt() - base]++;
    }
    for(const c of ransomNote){
        if(!hash[c.charCodeAt() - base]) return false;
        hash[c.charCodeAt() - base]--;
        if(hash[c.charCodeAt() - base] < 0) return false;
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3.字母异位词分组

49. 字母异位词分组-中等
对strs中的每个字符都新建一个长度26的数组来判断

var groupAnagrams = function(strs) {
    const map=new Object();
    for(let str of strs){
        const count=new Array(26).fill(0);
        for(let c of str){
            count[c.charCodeAt()-'a'.charCodeAt()]++;
        }
        console.log(map);
        map[count]?map[count].push(str):map[count]=[str];
    }
    return Object.values(map);
};
1
2
3
4
5
6
7
8
9
10
11
12

4.找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词-中等
①滑动窗口+哈希数组
思路：使用数组来存储字符串p和滑动窗口中每种字母的数量

var findAnagrams = function(s, p) {
    if(p.length > s.length) return [];

    const sHash = new Array(26).fill(0);
    const pHash = new Array(26).fill(0);
    let ans=[];

    for(let i = 0;i < p.length;i++){
        sHash[s.charCodeAt(i) - 'a'.charCodeAt()]++;
        pHash[p.charCodeAt(i) - 'a'.charCodeAt()]++;
    }
    if(sHash.toString() === pHash.toString()){
        ans.push(0);
    }
   
    
    for(let i = 0;i < s.length - p.length;i++){
    	 // 窗口的滑动过程  窗口长度为p.length
        sHash[s.charCodeAt(i) - 'a'.charCodeAt()]--; // 窗口左边出去一个字符 
        sHash[s.charCodeAt(i+p.length) - 'a'.charCodeAt()]++; // 窗口右边进来一个字符 

        if(sHash.toString() === pHash.toString()){
            ans.push(i+1);
        } 
    }
    return ans;
};
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

力扣官方👇