今天學(xué)習(xí)哈希表
一般哈希表都是用來快速判斷一個元素是否出現(xiàn)集合里
242. 有效的字母異位詞
題目描述：
給定兩個字符串 s 和 t ，編寫一個函數(shù)來判斷 t 是否是 s 的字母異位詞。
注意：若 s 和 t 中每個字符出現(xiàn)的次數(shù)都相同，則稱 s 和 t 互為字母異位詞。
示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
解題思路
- 遍歷字符串s，利用map記錄各個字符出現(xiàn)的次數(shù)
- 遍歷字符串t，如果 t 中的字符在map中出現(xiàn)，則對應(yīng)數(shù)值減1，如果 t 中的字符沒有出現(xiàn)，或者直到數(shù)值小于0 ，則不為字母異位詞
- 否則互為字母異位詞
var isAnagram = function(s, t) {
if (s.length !== t.length) {
return false
}
let record = new Map()
for (let item of s) {
record.set(item, (record.get(item) || 0) + 1)
}
for (let item of t) {
if (!record.get(item) || record.get(item) < 0) {
return false
}
record.set(item, (record.get(item) || 0) - 1)
}
return true;
};
349. 兩個數(shù)組的交集
題目描述：
給定兩個數(shù)組 nums1 和 nums2 ，返回它們的交集 。輸出結(jié)果中的每個元素一定是唯一的。我們可以 不考慮輸出結(jié)果的順序 。
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]
示例 2：
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋：[4,9] 也是可通過的
解題思路
實現(xiàn)一
- 利用map記錄nums1中的元素
- 再遍歷nums2中的元素，如果存在map中，并且結(jié)果數(shù)組res中不存在，那么添加到結(jié)果數(shù)組中
var intersection = function(nums1, nums2) {
let res = [];
let record = new Map();
for (let i of nums1) {
record.set(i, 1)
}
for (let i of nums2) {
if (record.get(i) && !res.includes(i)) {
res.push(i)
}
}
return res;
};
實現(xiàn)二
- 直接利用set存儲結(jié)果值，不用考慮會出現(xiàn)重復(fù)的元素了
var intersection = function(nums1, nums2) {
let res = new Set();
let record = new Map();
for (let i of nums1) {
record.set(i, 1)
}
for (let i of nums2) {
if (record.get(i)) {
res.add(i)
}
}
return Array.from(res);
};
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。
示例 1：
輸入：n = 19
輸出：true
解釋：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
輸入：n = 2
輸出：false
提示：
1 <= n <= 2^31 - 1
解題思路
- 重復(fù)上述計算過程，如果出現(xiàn) 1 為快樂數(shù)，如果出現(xiàn)無限循環(huán)，則說明某個計算和會重復(fù)出現(xiàn)，如果重復(fù)出現(xiàn)且不為 1 ，那么則不為快樂數(shù)。
- 對 n 的各個位依次求和
- 記錄求和出現(xiàn)次數(shù)，判斷是否再次出現(xiàn)
var isHappy = function(n) {
let map = new Map()
// 求各個位的平方和
function getSum (n) {
let sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n = Math.floor(n / 10)
}
return sum;
}
while(true) {
if (map.has(n)) {
return false
}
if (n === 1) {
return true
}
map.set(n, 1)
n = getSum(n)
}
};
1. 兩數(shù)之和
題目描述：
給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
解題思路
- 使用 map 存儲元素，值為對應(yīng)索引
- 利用差值，與 map 中的元素進行比較，如果相等，則找到已存在的元素，及當(dāng)前比較元素的索引
var twoSum = function(nums, target) {
let map = new Map();
let res = [];
for (let i = 0; i < nums.length; i++) {
if (!map.has(target - nums[i])) {
map.set(nums[i], i)
} else {
res = [map.get(target - nums[i]), i]
}
}
return res;
};
