Day5休息一天劫谅，今天繼續(xù)來完成算法題~

JavaScript里面的哈希表理論基礎(chǔ)

當(dāng)我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候见坑，就要考慮哈希法嚷掠。哈希法一般有數(shù)組、set荞驴、map三種結(jié)構(gòu)不皆，是犧牲了空間來換取時間的一種數(shù)據(jù)結(jié)構(gòu)。
下面的介紹內(nèi)容引自MDN網(wǎng)站：

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 對象轉(zhuǎn)換為數(shù)組對象
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 之間轉(zhuǎn)換
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'關(guān)聯(lián)的值");
myMap.set(keyObj, "和鍵 keyObj 關(guān)聯(lián)的值");
myMap.set(keyFunc, "和鍵 keyFunc 關(guān)聯(lián)的值");

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

// 讀取值
console.log(myMap.get(keyString)); // "和鍵'a string'關(guān)聯(lián)的值"
console.log(myMap.get(keyObj)); // "和鍵 keyObj 關(guān)聯(lián)的值"
console.log(myMap.get(keyFunc)); // "和鍵 keyFunc 關(guān)聯(lián)的值"

console.log(myMap.get("a string")); // "和鍵'a string'關(guān)聯(lián)的值"叫惊，因為 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 與數(shù)組對象的關(guān)系
const kvArray = [
  ["key1", "value1"],
  ["key2", "value2"],
];

// 使用常規(guī)的 Map 構(gòu)造函數(shù)可以將一個二維的鍵值對數(shù)組轉(zhuǎn)換成一個 Map 對象
const myMap = new Map(kvArray);

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

// 使用 Array.from 函數(shù)可以將一個 Map 對象轉(zhuǎn)換成一個二維的鍵值對數(shù)組
console.log(Array.from(myMap)); // 輸出和 kvArray 相同的數(shù)組

// 更簡潔的方法來做如上同樣的事情霍狰，使用展開運(yùn)算符
console.log([...myMap]);

// 或者在鍵或者值的迭代器上使用 Array.from，進(jìn)而得到只含有鍵或者值的數(shù)組
console.log(Array.from(myMap.keys())); // 輸出 ["key1", "key2"]

242.有效的字母異位詞

題目：

給定兩個字符串 s 和 t 饰及，編寫一個函數(shù)來判斷 t 是否是 s 的字母異位詞蔗坯。
注意：若 s 和 t 中每個字符出現(xiàn)的次數(shù)都相同，則稱 s 和 t 互為字母異位詞燎含。
示例：

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

解題思路：

哈希表的基本應(yīng)用宾濒，在同一個數(shù)組上遍歷兩次，第一次把s字符串的每一個出現(xiàn)的次數(shù)錄入屏箍，第二次把t字符串出現(xiàn)的次數(shù)和s對應(yīng)位置的次數(shù)相減绘梦，最后得到的數(shù)組如果全部是0的情況下就說明兩個數(shù)組滿足條件橘忱。

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
};

注意點(diǎn)：
關(guān)于獲取字母的ASCII值可以參考這篇文章。

349. 兩個數(shù)組的交集

題目：

給定兩個數(shù)組 nums1 和 nums2 卸奉，返回它們的交集 钝诚。輸出結(jié)果中的每個元素一定是唯一的。我們可以不考慮輸出結(jié)果的順序榄棵。
示例：

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

解題思路：

1. Set 集合

先把一個數(shù)組轉(zhuǎn)換成集合敲长，再遍歷第二個數(shù)組，如果遇到集合內(nèi)的就加入到結(jié)果集合中秉继，最后把結(jié)果集合轉(zhuǎn)換為數(shù)組。

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. 數(shù)組

因為用例最大值是1000所以可以定義一個稍大的數(shù)組泽铛，把nums1中有的數(shù)字放進(jìn)數(shù)組尚辑，然后再遍歷nums2把結(jié)果加入結(jié)果集合即可。

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. 快樂數(shù)

題目：

編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)盔腔。
「快樂數(shù)」 定義為：

• 對于一個正整數(shù)杠茬，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
• 然后重復(fù)這個過程直到這個數(shù)變?yōu)?1弛随，也可能是 無限循環(huán) 但始終變不到 1瓢喉。
• 如果這個過程 結(jié)果為 1，那么這個數(shù)就是快樂數(shù)舀透。
  如果 n 是 快樂數(shù) 就返回 true 栓票；不是，則返回 false 愕够。
  示例：

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

解題思路：

1. 直接模擬

可以用Set來判斷已經(jīng)進(jìn)入無限循環(huán)走贪，然后輸出結(jié)果即可。

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. 快慢指針

進(jìn)入無限循環(huán)后惑芭，相當(dāng)于進(jìn)入環(huán)坠狡，可以用快慢指針解決鏈表有環(huán)問題的思路來進(jìn)行解決。

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. 兩數(shù)之和

題目：

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target遂跟，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)逃沿，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案幻锁。但是凯亮，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案越败。
示例：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 触幼，返回 [0, 1] 。

解題思路：
用Map來存放每一次遍歷的nums究飞，遍歷Map過程中置谦，如果在找到對應(yīng)的數(shù)值堂鲤，就返回。如果一直沒找到就返回空數(shù)組媒峡。
這道題的四個重點(diǎn)在于：

• 這道題用哈希法的原因：
  本題需要一個集合來存放我們遍歷過的元素瘟栖，然后在遍歷數(shù)組的時候去詢問這個集合，某元素是否遍歷過谅阿，也就是是否出現(xiàn)在這個集合半哟，就需要用哈希法。
• 用Map的原因：
  本題不僅要知道元素有沒有遍歷過签餐，還要知道這個元素對應(yīng)的下標(biāo)寓涨，key來存元素，value來存下標(biāo)氯檐，使用map正合適戒良。
• Map的作用：
  用來存放訪問過的元素。
• Map里面的key和value的作用：
  map中的存儲結(jié)構(gòu)為 {key：數(shù)據(jù)元素冠摄，value：數(shù)組元素對應(yīng)的下標(biāo)}糯崎。在遍歷數(shù)組的時候，只需要向map去查詢是否有和目前遍歷元素匹配的數(shù)值河泳。

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 []
};