Day5休憩一天，今天继续来完成算法题~

JavaScript里面的哈希表理论基础

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要思考哈希法。哈希法一般有数组、set、map三种结构，是牺牲了空间来换取时间的一种数据结构。
下面的介绍内容引自MDN网站：

Set 集合

// ① 使用Set对象
const mySet1 = new Set();

mySet1.add(1); // Set(1) { 1 }
mySet1.add(5); // Set(2) { 1, 5 }
mySet1.add(5); // Set(2) { 1, 5 }
mySet1.add("some text"); // Set(3) { 1, 5,  some text  }
const o = { a: 1, b: 2 };
mySet1.add(o);

mySet1.add({ a: 1, b: 2 }); // o 是不同对象的引用，所以这是可以的

mySet1.has(1); // true
mySet1.has(3); // false，由于并未将 3 添加到集合中
mySet1.has(5); // true
mySet1.has(Math.sqrt(25)); // true
mySet1.has("Some Text".toLowerCase()); // true
mySet1.has(o); // true

mySet1.size; // 5

mySet1.delete(5); // 从集合中移除 5
mySet1.has(5); // false，5 已从集合中移除

mySet1.size; // 4，由于我们刚刚移除了一个值

mySet1.add(5); // Set(5) { 1,  some text , {...}, {...}, 5 }——先前删除的元素会作为新的元素被添加，不会保留删除前的原始位置

console.log(mySet1); // Set(5) { 1, "some text", {…}, {…}, 5 }

// ② 迭代集合
for (const item of mySet1) {
  console.log(item);
}
// 1、"some text"、{ "a": 1, "b": 2 }、{ "a": 1, "b": 2 }、5

for (const item of mySet1.keys()) {
  console.log(item);
}
// 1、"some text"、{ "a": 1, "b": 2 }、{ "a": 1, "b": 2 }、5

for (const item of mySet1.values()) {
  console.log(item);
}
// 1、"some text"、{ "a": 1, "b": 2 }、{ "a": 1, "b": 2 }、5

// 键和值是一样的
for (const [key, value] of mySet1.entries()) {
  console.log(key);
}
// 1、"some text"、{ "a": 1, "b": 2 }、{ "a": 1, "b": 2 }、5

// 使用 Array.from 将 Set 对象转换为数组对象
const myArr = Array.from(mySet1); // [1, "some text", {"a": 1, "b": 2}, {"a": 1, "b": 2}, 5]

// 如果在 HTML 文档中使用，也可以：
mySet1.add(document.body);
mySet1.has(document.querySelector("body")); // true

// 在 Set 和 Array 之间转换
const mySet2 = new Set([1, 2, 3, 4]);
console.log(mySet2.size); // 4
console.log([...mySet2]); // [1, 2, 3, 4]

// 可以通过如下代码模拟求交集
const intersection = new Set([...mySet1].filter((x) => mySet2.has(x)));

// 可以通过如下代码模拟求差集
const difference = new Set([...mySet1].filter((x) => !mySet2.has(x)));

// 使用 forEach() 迭代集合中的条目
mySet2.forEach((value) => {
  console.log(value);
});
// 1
// 2
// 3
// 4

Map 哈希表

// ① 使用Map对象
const myMap = new Map();

const keyString = "a string";
const keyObj = {};
const keyFunc = function () {};

// 添加键
myMap.set(keyString, "和键 a string 关联的值");
myMap.set(keyObj, "和键 keyObj 关联的值");
myMap.set(keyFunc, "和键 keyFunc 关联的值");

console.log(myMap.size); // 3

// 读取值
console.log(myMap.get(keyString)); // "和键 a string 关联的值"
console.log(myMap.get(keyObj)); // "和键 keyObj 关联的值"
console.log(myMap.get(keyFunc)); // "和键 keyFunc 关联的值"

console.log(myMap.get("a string")); // "和键 a string 关联的值"，由于 keyString ===  a string 
console.log(myMap.get({})); // undefined，由于 keyObj !== {}
console.log(myMap.get(function () {})); // undefined，由于 keyFunc !== function () {}

// ② 迭代 Map
const myMap = new Map();
myMap.set(0, "zero");
myMap.set(1, "one");

for (const [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}
// 0 = zero
// 1 = one

for (const key of myMap.keys()) {
  console.log(key);
}
// 0
// 1

for (const value of myMap.values()) {
  console.log(value);
}
// zero
// one

for (const [key, value] of myMap.entries()) {
  console.log(`${key} = ${value}`);
}
// 0 = zero
// 1 = one

myMap.forEach((value, key) => {
  console.log(`${key} = ${value}`);
});
// 0 = zero
// 1 = one

// ③ Map 与数组对象的关系
const kvArray = [
  ["key1", "value1"],
  ["key2", "value2"],
];

// 使用常规的 Map 构造函数可以将一个二维的键值对数组转换成一个 Map 对象
const myMap = new Map(kvArray);

console.log(myMap.get("key1")); // "value1"

// 使用 Array.from 函数可以将一个 Map 对象转换成一个二维的键值对数组
console.log(Array.from(myMap)); // 输出和 kvArray 一样的数组

// 更简洁的方法来做如上同样的事情，使用展开运算符
console.log([...myMap]);

// 或者在键或者值的迭代器上使用 Array.from，进而得到只含有键或者值的数组
console.log(Array.from(myMap.keys())); // 输出 ["key1", "key2"]

242.有效的字母异位词

题目：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都一样，则称 s 和 t 互为字母异位词。
示例：

输入: s = "anagram", t = "nagaram"
输出: true

解题思路：

哈希表的基本应用，在同一个数组上遍历两次，第一次把s字符串的每一个出现的次数录入，第二次把t字符串出现的次数和s对应位置的次数相减，最后得到的数组如果全部是0的情况下就说明两个数组满足条件。

var isAnagram = function (s, t) {
    const arr = new Array(26).fill(0);
    const codeA =  a .charCodeAt();
    for (let i = 0; i < s.length; i++) {
        arr[s[i].charCodeAt() - codeA]++;
    }
    for (let i = 0; i < t.length; i++) {
        arr[t[i].charCodeAt() - codeA]--;
    }
    return arr.findIndex((item) => item !== 0) === -1 ? true : false
};

注意点：
关于获取字母的ASCII值可以参考这篇文章。

349. 两个数组的交集

题目：

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素必定是唯一的。我们可以不思考输出结果的顺序。
示例：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

解题思路：

1. Set 集合

先把一个数组转换成集合，再遍历第二个数组，如果遇到集合内的就加入到结果集合中，最后把结果集合转换为数组。

var intersection = function (nums1, nums2) {
    const set = new Set(nums1);
    const resultSet = new Set();
    for (let i = 0; i < nums2.length; i++) {
        if (set.has(nums2[i])) {
            resultSet.add(nums2[i]);
        }
    }
    return Array.from(resultSet);
};

2. 数组

由于用例最大值是1000所以可以定义一个稍大的数组，把nums1中有的数字放进数组，然后再遍历nums2把结果加入结果集合即可。

var intersection = function (nums1, nums2) {
    const arr = new Array(1005).fill(0);
    const resultSet = new Set();
    for (let i = 0; i < nums1.length; i++) {
        arr[nums1[i]] = 1;
    }
    for (let i = 0; i < nums2.length; i++) {
        if (arr[nums2[i]] === 1) {
            resultSet.add(nums2[i]);
        }
    }
    return Array.from(resultSet);
};

202. 快乐数

题目：

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题思路：

1. 直接模拟

可以用Set来判断已经进入无限循环，然后输出结果即可。

const getSum = (n) => {
    return Array.from(n.toString()).reduce((a, b) => a + b * b, 0)
}
var isHappy = function (n) {
    let set = new Set();
    while (true) {
        let sum = getSum(n);
        if (sum === 1) {
            return true;
        }
        if (set.has(sum)) {
            return false;
        } else {
            set.add(sum);
        }
        n = sum;
    }
}

2. 快慢指针

进入无限循环后，相当于进入环，可以用快慢指针解决链表有环问题的思路来进行解决。

const getSum = (n) => {
    return Array.from(n.toString()).reduce((a, b) => a + b * b, 0)
}
var isHappy = function (n) {
    let slow = n;
    let fast = getSum(n);
    while(fast !== 1 && fast !== slow){
        slow = getSum(slow);
        fast = getSum(getSum(fast))
    }
    return fast === 1;
}

1. 两数之和

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：由于 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路：
用Map来存放每一次遍历的nums，遍历Map过程中，如果在找到对应的数值，就返回。如果一直没找到就返回空数组。
这道题的四个重点在于：

这道题用哈希法的缘由：
本题需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出目前这个集合，就需要用哈希法。
用Map的缘由：
本题不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，key来存元素，value来存下标，使用map正合适。
Map的作用：
用来存放访问过的元素。
Map里面的key和value的作用：
map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值。

var twoSum = function (nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i);
        }
    }
    return []
};

文章版权归作者所有，未经允许请勿转载。如内容涉嫌侵权，请在本页底部进入<联系我们>进行举报投诉!

THE END