【代码随想录 | day05】(JavaScript) 哈希表理论基础以及相关算法题

theme: cyanosis
highlight: androidstudio

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第2天，点击查看活动详情

• 哈希表理论基础
• 242.有效的字母异位词
• 349.两个数组的交集
• 202.快乐数
• 两数之和

24.两两交换链表中的节点

哈希表理论基础

要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。

1. 什么是哈希表?

   百度百科解释：

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

2. 什么是哈希函数?

   百度百科解释：

   给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

3. 什么是哈希碰撞？

   当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

4. 常见的三种哈希结构：数组、set（集合）、map（映射）

   • ES6 提供了新的数据结构 Set（集合）。它类似于数组，但成员的值都是唯一的，集合实现了 iterator接口，所以可以使用『扩展运算符』和『for…of…』进行遍历，集合的属性和方法：

     • size 返回集合的元素个数；

     • add 增加一个新元素，返回当前集合；

     • delete 删除元素，返回 boolean 值；

     • has 检测集合中是否包含某个元素，返回 boolean 值；

     • clear 清空集合，返回 undefined；

     • let s1 = new Set(["大哥","二哥","三哥","四哥","三哥"]);
       console.log(s1); // 自动去重
       

   • ES6 提供了 Map 数据结构。它类似于对象，也是键值对的集合。但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。Map 也实现了iterator 接口，所以可以使用『扩展运算符』和『for…of…』进行遍历；Map 的属性和方法：

     • size 返回 Map 的元素个数；
     • set 增加一个新元素，返回当前 Map；
     • get 返回键名对象的键值；
     • has 检测 Map 中是否包含某个元素，返回 boolean 值；
     • clear 清空集合，返回 undefined；

5. 那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

6. 什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 这句话很重要，大家在做哈希表题目都要思考这句话。

242.有效的字母异位词

题目链接：242. 有效的字母异位词 – 力扣（LeetCode）

我的解法

思路：

• 如果字符串长度不相等，那么字母出现的次数不可能完全相等
• 统计字符串中的字符出现次数，并且转为对象
• 判断两个对象的值是否相等

// 统计字符串中的字符出现次数，并且转为对象
var strToObj = function(str) {
    let obj = {};
    for(let i = 0; i < str.length; i++) {
        let chars = str.charAt(i); // chars是字符串的每一个字符
        if(obj[chars]) {
            obj[chars]++;
        } else {
            obj[chars] = 1;
        }
    }
    return obj
}

var isAnagram = function(s, t) {
    // 如果字符串长度不相等，那么字母出现的次数不可能完全相等
    if(s.length != t.length) return false

    let objS = strToObj(s);
    let objT = strToObj(t);

    // 判断两个对象的值是否相等
    
    let sProps = Object.getOwnPropertyNames(objS); //取对象的属性名，组成数组
    // let tProps = Object.getOwnPropertyNames(objT);

    for(let i = 0; i < sProps.length; i++) {
        var propName = sProps[i]; // propName就是属性名，即为一个个的字母
        // 判断两个对象中，相同字母出现的次数是不是一样
        if( objS[propName] !== objT[propName] ) {
            return false 
        }
    }
    return true

};

其中使用到的方法：

• charAt(index) —— 返回指定位置的字符(index字符串的索引号)

• Object.getOwnPropertyNames() —— 方法返回一个由指定对象的所有自身属性的属性名（包括不可枚举属性但不包括 Symbol 值作为名称的属性）组成的数组。

卡神解法

思路：

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

1. 用数组来统计第一个字符串里面字母出现的频率。那么如何统计呢？
2. 需要定义一个多大的数组呢，定一个数组叫做==resSet==，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。
3. 需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
4. 遍历字符串 s，将字符串中字母出现的次数统计出来。
5. 检查字符串 t 中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
    const resSet = new Array(26).fill(0);
    const base = "a".charCodeAt();
    for(const i of s) {
        resSet[i.charCodeAt() - base]++;
    }
    for(const i of t) {
        if(!resSet[i.charCodeAt() - base]) return false; // 这一步可以好好捋一捋
        resSet[i.charCodeAt() - base]--;
    }
    return true;
};

• const resSet = new Array(26).fill(0);

  解读： fill() 函数提供将数组中给定范围内的所有元素更改为特定值的功能，那么现在数组长度为26，且元素目前都为 0

• const base = "a".charCodeAt();

  解读：charCodeAt() 方法可返回指定位置的字符的 Unicode 编码。这里返回 a 的 ASCII 码。

• for(const i of s) { resSet[i.charCodeAt() - base]++; }

  解读： 如果第一个字母是 a ，那么 a – base 就是 0 ，这样 a 的索引就为 0 。依次遍历字符串 s ，那么字符串里面每一个字母都有唯一的索引。
  for… of 方法在这里可以遍历数组中的每一项。

• :star: if(!resSet[i.charCodeAt() - base])

  解读： 首先 i.charCodeAt() - base 返回字符串 t 中当前字母对应的索引。可以这样理解，如果字符串 s 为 “abbc”，那么在数组 resSet 中，字母 d 所对应的引索就是 3 ，就有 resSet[3] = 0 。但是，如果字母 d 在字符串 t 中出现一次，那么当遍历到 d 的时候，resSet[i.charCodeAt() – base] 就相当于 resSet[3]，值为 0 。前面加 ！则 if 括号中的语句就变成了 true 了。
  关键就在于：如果字符串 t 中出现的字母和字符串 s 中一样，那么 if 语句中条件就一定是假，这一步就不会走。

• resSet[i.charCodeAt() - base]--;

  解读： 遍历字符串 t ，每遇到和字符串 s 中相同的字母时，该字母所对应的索引中的元素值都会减去 1 。

349.两个数组的交集

题目链接：349. 两个数组的交集 – 力扣（LeetCode）

我的解法

利用 set 的自动去重和has方法，其中也使用了for…of 循环（详情见参考文章里面的链接）

var intersection = function(nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);
    // set1, set2 自动去重
    let commonNum = [];
    for (let val of set1) {
        if (set2.has(val)) {
            commonNum.push(val)
        }
    }
    return commonNum
};

卡神解法

遇到哈希的问题一定要先考虑数据量的大小，再决定用什么哈希结构。

使用数组来做哈希的题目，是因为题目都限制了数值的大小。 而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    // 根据数组大小交换操作的数组
    if(nums1.length < nums2.length) {
        const _ = nums1;
        nums1 = nums2;
        nums2 = _;
    }
    const nums1Set = new Set(nums1);
    const resSet = new Set();
    // for(const n of nums2) {
    //     nums1Set.has(n) && resSet.add(n);
    // }
    // 循环 比 迭代器快
    for(let i = nums2.length - 1; i >= 0; i--) {
        nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
    }
    return Array.from(resSet);
};

• 首先判断数组大小，让 num1 表示长一点的数组。
• 数组 num1 去重。
• Array.from ()方法就是将一个类数组对象或者可遍历对象转换成一个真正的数组，也是ES6的新增方法。

202.快乐数

题目链接：202. 快乐数 – 力扣（LeetCode）

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

• 如果这个过程 结果为 1，那么这个数就是快乐数。

  如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

注意点：数字相加的过程可能会无线循环，那么代码中怎么写才能避免运行时间超出限制呢。

我的解法

计算正整数 n 的各位的平方和 sum，若 sum等于1，则返回true，若不等，则将sum赋值给n，重复上述步骤。

不过有可能sum始终不为1，我们设置一个最大循环次数，次数使用完时，sum还是不为1，就说明这个正整数不是快乐数。

var isHappy = function(n) {
    var sum;
    var count = 50; // 最多循环50次
    while(count >= 0) {
        var remainder; // 余数
        sum = 0;
        while(n !== 0) {
            remainder = n % 10;
            sum += remainder * remainder;
            n = parseInt(n / 10);
        }
        if (sum === 1) return true;
        n = sum;
        count--;
    }
    return false;
};

• 通过第二个while语句，实现各个位数上面的数字平方相加。

卡神解法

var isHappy = function (n) {
    let m = new Map()

    const getSum = (num) => {
        let sum = 0
        while (n) {
            sum += (n % 10) ** 2
            n = Math.floor(n / 10)
        }
        return sum
    }

    while (true) {
        // n出现过，证明已陷入无限循环
        if (m.has(n)) return false
        if (n === 1) return true
        m.set(n, 1) // 添加新的key-value
        n = getSum(n)
    }
}

• getSum() 能返回各个位上数字的平方和。

• has 检测 Map 中是否包含某个元素，返回 boolean 值；

• Map中的set()方法能增加一个新元素，返回当前Map

// 使用Set()，求和用reduce
var isHappy = function(n) {
    let set = new Set();
    let totalCount;
    while(totalCount !== 1) {
        let arr = (''+(totalCount || n)).split('');
        totalCount = arr.reduce((total, num) => {
            return total + num * num
        }, 0)
        if (set.has(totalCount)) {
            return false;
        }
        set.add(totalCount);
    }
    return true;
};

其他JavaScript解法：代码随想录 (programmercarl.com)

两数之和

题目链接：代码随想录 (programmercarl.com)

我的解法

使用了双重 for 循环，暴力相加。

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            let sum = nums[i] + nums[j];
            if (sum !== target) {
                continue
            } else {
                let arr = [i, j];
                return arr
            }
        }
    }
};

• 注意点：i 从0开始取，而 j = i + 1 。时间复杂度是 O(n^2) 。

卡神解法

:star:首先Carl老师再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

要把遍历过的元素加到一个集合里，然后每次遍历一个新的位置之后，就判断想要寻找的这个元素是否在这个集合里出现过。如果在这个集合里面出现过，就说我们之前遍历过。

用==map==来存放数据，元素是 key ，下标是 value 。

var twoSum = function (nums, target) {
  let hash = {};
  for (let i = 0; i < nums.length; i++) {
    let s = target - nums[i]; // target 减去当前遍历的元素
    if (hash[s] !== undefined) {
      return [i, hash[s]];
    }
    hash[nums[i]] = i;
  }
  return [];
};

• 这里定义一个对象 hash ，因为 js 中对象有 key ，有 value 。

• hash[s] !== undefined

  解读： 如果对象 hash 中想要的元素 s 不存在，那么，hash[s] 就得不到相应的 value ， 则 hash[s] 为 undefined 。如果存在，那么直接返回这个元素所对呀的下标即可。

• hash[nums[i]] = i;

  解读： 元素是 key ，下标是 value 。因为要考虑的是元素是否出现过，所以用元素作为 key

参考文章

• 哈希碰撞和哈希冲突 – 探歌 – 博客园 (cnblogs.com)
• 来吧！一文彻底搞定哈希表！_庆哥Java的博客-CSDN博客
• 代码随想录 (programmercarl.com)
• js判断两个对象的值是否相等_松重丰的博客-CSDN博客
• JS——charAt() 方法_weixin_30750335的博客-CSDN博客
• Object.getOwnPropertyNames() – JavaScript | MDN (mozilla.org)
• 简单理解Arrays.fill()函数_iDragonLong的博客-CSDN博客
• for of 循环详解_wflynn的博客-CSDN博客
• JavaScript取各个位数的方法_抹茶摩卡的博客-CSDN博客_js取个位数