零、哈希表概述
【哈希表概述】
【哈希表】是根据关键码值(Key value)而直接进行访问的数据结构。优势在于查找的时间复杂度为 O(1) ，用于快速判断一个元素是否出现。在哈希表构建的时候，存在【哈希碰撞】的问题，不过不是本篇的重点。
【哈希表的分类】
【哈希表】常用的数据结构有：【数组】【set】【map】三种。【数组】不必多说，本篇主要讲解后两者。
- 【集合 set】是使用数字索引，但是最大的特征是【不重复】，可以用于数据的去重。
- 【映射 map】是一种键值对结构，有键
key作为索引，查询值value数据。
一、哈希表
类型概述
【哈希表】常用的三种数据结构分别是【数组】【set】【map】，它们对应不同的应用场景，具体如下。虽然说【map】可以把前两者全部代替，但是适合前两者还是应该了解的，所以本篇将给出前两者的特色题，通用题都用 map 处理。
| 类型 | 优势 | 劣势 |
|---|---|---|
| 数组 | 直接高效 | 大小受限制，如果哈希值较少，且跨度较大，会造成空间的浪费。 |
| set | 自动去重 | 只能记录一个 key 值 |
| map | 万用 | 空间消耗较大 |
题型一 | 数组类型
题型串联
1 赎金信
【概述】哈希表 数组
【题目描述**】
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
【题目示例**】
canConstruct("a", "b") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true
【查找是否出现】已知 magazine ，判断 ransom 中元素是否都存在于 magazine 。
【哈希表】本题最大的特征查找的是字母，因为一共就 26 个字母，所以可以使用数组作为哈希表。
- 【key】字母编号
【value】出现次数
var isAnagram = function(s, t) { const mono = new Array(26).fill(0); for( let c of s ) mono[c.charCodeAt()-'a'.charCodeAt()]++; for( let c of t ) mono[c.charCodeAt()-'a'.charCodeAt()]--; for( let count of mono ){ if( count !== 0 ) return false; } return true; };2 有效的字母异位词
【概述】哈希表 数组
【题目描述**】
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
【题目示例**】输入: s = "anagram", t = "nagaram" 输出: true【查找是否出现】已知
s，判断t中元素是否都存在于s。
【哈希表】本题最大的特征查找的是字母，因为一共就26个字母，所以可以使用数组作为哈希表。【key】字母编号
- 【value】出现次数
var isAnagram = function(s, t) { const mono = new Array(26).fill(0); for( let c of s ) mono[c.charCodeAt()-'a'.charCodeAt()]++; for( let c of t ) mono[c.charCodeAt()-'a'.charCodeAt()]--; for( let count of mono ){ if( count !== 0 ) return false; } return true; };
题型二 | 集合类型
题型串联
1 两个数组的交集
【概述】哈希表 集合
【题目描述**】**
给定两个数组，编写一个函数来计算它们的交集。
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
【题目示例**】**
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
【查找是否出现】已知 nums1 ，判断 nums2 中元素是否存在于 nums1 ，如果存在即为交集。
【哈希表】本题要求输出的交集元素唯一，且不看顺序，都在暗示使用集合处理。集合只存储【key】，对应数字。
var intersection = function(nums1, nums2) {
const mono = new Set(nums1);
const res = new Set();
for( let num of nums2 ){
if(mono.has(num)) res.add(num);
}
return Array.from(res)
};
2 快乐数
【概述】哈希表 集合
【题目描述**】
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
【题目示例**】
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
【查找是否出现】判断当前求和 sum 是否出现过 ，如果出现过说明开始循环，只要不到循环，总有一天会到 1 。
【哈希表】由于我们只需要存一个求和值，所以不用 map 如此麻烦，用 set 即可。需要熟悉取各位数值的操作，具体将会在【数学相关】那篇讲解。
var isHappy = function(n) {
const mono = new Set();
let sum = n;
while(sum !== 1){
let tmp = 0 ;
while( sum ){
tmp += (sum%10)*(sum%10);
sum = sum / 10 | 0;
}
if(mono.has(tmp)) return false;
mono.add(tmp);
sum = tmp;
}
return true;
};
题型三 | map 类型
题型串联
1 两数之和
【概述】哈希表 map
【题目描述**】
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
【题目示例**】
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
【查找是否出现】已知 nums[i] ，查找 target-nums[i] 是否存在。
【哈希表】由于我们要记录两个值，索引下标和索引指向的数据，所以选择 map 实现。
- 【key】数字
【value】下标
var twoSum = function(nums, target) { const mono = new Map(); for(let i = 0 ; i < nums.length ; i++){ const tmp = target - nums[i]; if(mono.has(tmp)) return [mono.get(tmp),i]; mono.set(nums[i],i) } return []; };2 缺失的第一个正数
【概述】哈希表
【题目描述**】
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
【查找是否出现】从0开始计数i，查找i是否存在于数组nums。
【哈希表】**【key】数字【value】boolean
=> 直接使用 Array.includes() 判断是否包含（JS），常规来说可以使用哈希表（除去数组） 。var firstMissingPositive = function(nums) { let res = 1; while(nums.includes(res)) res++; return res; };3 矩阵置零
【概述】哈希表
【题目描述**】
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
【记录是否出现】记录0出现的行或者列，之后统一置零 。
【哈希表】**【key】行/列【value】booleanvar setZeroes = function(matrix) { const m = matrix.length , n = matrix[0].length; const col = [] , row = []; for( let i = 0 ; i < m ; i++){ for( let j = 0 ; j < n ; j++){ if(!matrix[i][j]) col.push(i),row.push(j); } } for( let i of col ) { for( let j = 0 ; j < n ; j++){ if(matrix[i][j]) matrix[i][j] = 0; } } for( let i of row ) { for( let j = 0 ; j < m ; j++){ if(matrix[j][i]) matrix[j][i] = 0; } } return matrix; };4 有效的数独
【概述】哈希表
【题目描述**】
判断一个9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
【查找是否出现**】查询数字是否在【同行】、【同列】以及【同框】出现过。
【哈希表】【同行】【key】行+数字【value】boolean
- 【同列】【key】列+数字【value】boolean
【同框】【key】boxIndex+数字【value】boolean ，其中
boxIndex = Math.floor(x/3)*3 + Math.floor(y/3)。var isValidSudoku = function(board) { const row = {} , col = {} , box = {}; for(let i = 0 ; i < 9 ; i++){ for(let j = 0 ; j < 9 ; j++){ if(board[i][j]!== '.'){ const num = board[i][j] , boxIdx = Math.floor(i / 3) * 3 + Math.floor(j/3); if(row[`${i}-${num}`] || col[`${j}-${num}`] || box[`${boxIdx}-${num}`]) return false; row[`${i}-${num}`] = col[`${j}-${num}`] = box[`${boxIdx}-${num}`] = true; } } } return true; };5 直线上最多的点数
【概述】哈希表
【题目描述**】
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
【记录次数】**遍历每一个点与另一个点的所有斜率，并统计每个斜率经过的点。- 【重复点】需要判断是否相同，之后直接叠加。
- 【斜率不存在】即使不存在，也会除出一个数，我们需要对其缩小（除余）。
【哈希表】**【key】斜率【value】**经过的点数
var maxPoints = function(points) {
const n = points.length
if (n <= 2) return n
let res = 2 ;
for (let i = 0; i < n; i++) {
let max = 0 , dup = 0;
const map = new Map()
for (let j = 0; j < n; j++) {
if (i != j) {
if (isSame(points[i], points[j])) dup++;
else {
const key = ((points[i][1] - points[j][1]) % 10000) / (points[i][0] - points[j][0])% 10000;
if (!map.has(key)) map.set(key, 2);
else map.set(key, map.get(key) + 1);
}
}
}
max = Math.max(max,...map.values())
if (max) max += dup;
else return n;
res = Math.max(res, max)
}
return res;
};
const isSame = (p1, p2)=>(p1[0] === p2[0]) && (p1[1] === p2[1]);
6 字母异位词分组
【概述】哈希表
【题目描述**】
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
【记录是否出现】对于同分异构体，排完序后是相同的，可以利用这一点，将同分异构体存在同一处 。
【哈希表】**【key】排序后的字符串【value】它的同分异构体数组
var groupAnagrams = function(strs) {
const map = new Map();
for( let str of strs){
const tmp = str.split('').sort().join('');
if(map.has(tmp)) map.set(tmp,[...map.get(tmp),str]);
else map.set(tmp,[str]);
}
return [...map.values()];
};
若有收获，就点个赞吧
0 人点赞
