(声明：所有题目都是leetcode上非会员题目）
在ES2015中，JavaScript新增了两种数据结构的实现，它们是Set和Map，这里首先复习下这两种数据结构的基本用法
1. Set基本用法(选自MDN)
概念
Set 对象允许你存储任何类型的唯一值，无论是原始值或者是对象引用。
语法
new Set([iterable]);
iterable如果传递一个可迭代对象，它的所有元素将不重复地被添加到新的 Set中。如果不指定此参数或其值为null，则新的 Set为空。
实例属性
-
Set.prototype.constructor返回实例的构造函数。默认情况下是Set。
-
Set.prototype.size返回Set对象的值的个数。
实例方法
Set.prototype.add(value)
在Set对象尾部添加一个元素。返回该Set对象。
Set.prototype.clear()
移除Set对象内的所有元素。
Set.prototype.delete(value)
移除Set的中与这个值相等的元素，返回Set.prototype.has(value)在这个操作前会返回的值（即如果该元素存在，返回true，否则返回false）。Set.prototype.has(value)在此后会返回false。
Set.prototype.entries()
返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值的[value, value]数组。为了使这个方法和Map对象保持相似， 每个值的键和值相等。
Set.prototype.forEach(callbackFn[, thisArg])
按照插入顺序，为Set对象中的每一个值调用一次callBackFn。如果提供了thisArg参数，回调中的this会是这个参数。
Set.prototype.has(value)
返回一个布尔值，表示该值在Set中存在与否。
Set.prototype.keys()
与values()方法相同，返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。
Set.prototype.values()
返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。
Set.prototype[@@iterator]()
返回一个新的迭代器对象，该对象包含Set对象中的按插入顺序排列的所有元素的值。
2. Map基本用法(选自MDN)
概念
Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值(对象或者原始值) 都可以作为一个键或一个值。
一个Map对象在迭代时会根据对象中元素的插入顺序来进行 — 一个 for...of 循环在每次迭代后会返回一个形式为[key，value]的数组
语法
new Map([iterable])
Iterable 可以是一个数组或者其他 iterable 对象，其元素为键值对(两个元素的数组，例如: [[ 1, 'one' ],[ 2, 'two' ]])。 每个键值对都会添加到新的Map。null 会被当做 undefined。
实例属性
Map.prototype.constructor
返回一个函数，它创建了实例的原型。默认是Map函数。
Map.prototype.size
返回Map对象的键/值对的数量。
实例方法
Map.prototype.clear()
移除Map对象的所有键/值对 。
Map.prototype.delete(key)
如果 Map 对象中存在该元素，则移除它并返回 true；否则如果该元素不存在则返回 false。随后调用 Map.prototype.has(key) 将返回 false。
Map.prototype.entries()
返回一个新的 Iterator 对象，它按插入顺序包含了Map对象中每个元素的 [key, value] 数组。
Map.prototype.forEach(callbackFn[, thisArg])
按插入顺序，为 Map对象里的每一键值对调用一次callbackFn函数。如果为forEach提供了thisArg，它将在每次回调中作为this值。
Map.prototype.get(key)
返回键对应的值，如果不存在，则返回undefined。
Map.prototype.has(key)
返回一个布尔值，表示Map实例是否包含键对应的值。
Map.prototype.keys()
返回一个新的 Iterator对象， 它按插入顺序包含了Map对象中每个元素的键 。
Map.prototype.set(key, value)
设置Map对象中键的值。返回该Map对象。
Map.prototype.values()
返回一个新的Iterator对象，它按插入顺序包含了Map对象中每个元素的值 。
Map.prototype[@@iterator]()
返回一个新的Iterator对象，它按插入顺序包含了Map对象中每个元素的 [key, value] 数组。
3. Leetcode上Map相关题目
leetcode 1. 两数之和
题目地址：两数相加
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var map = new Map();
var len = nums.length;
var diff = 0;
var res = [];
for(var i=0;i<len;i++){
diff = target - nums[i];
var diffVal = map.get(diff);
if(map.has(diff) && diffVal!=i){
res.push(i);
res.push(diffVal);
return res;
}else{
map.set(nums[i],i);
}
}
};
解法二：暴力求解
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
return []
};
leetcode 49. 字母异位词分组
题目地址：字母异位词分组
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
const len = strs.length
const res = []
const map = new Map()
for (let i = 0; i < len; i++) {
const str = strs[i].split('').sort().join('')
if (!map.has(str)) {
const arr = []
arr.push(strs[i])
map.set(str, arr)
} else {
const arr = map.get(str)
arr.push(strs[i])
map.set(str, arr)
}
}
map.forEach(value => {
res.push(value)
})
return res
};
leetcode 146. LRU缓存机制
题目地址：LRU缓存机制
this.map.keys().next()使用迭代器取到map第一个元素，也就是最近最少使用的元素
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity
this.map = new Map()
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.map.has(key)) {
let temp = this.map.get(key)
this.map.delete(key);
this.map.set(key, temp);
return temp;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.map.has(key)) {
this.map.delete(key);
} else if (this.map.size === this.capacity) {
this.map.delete(this.map.keys().next().value);
}
this.map.set(key, value);
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
leetcode 149. 直线上最多的点数
题目地址：直线上最多的点数
/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function(points) {
const len = points.length
if (len <= 2) {
return len
}
// 至少有两个点在一条直线上
let count = 2
// 存储相同点个数
let same = 0
for (let i = 0; i < len; i++) {
const p1 = points[i]
// 保存每一轮循环在一条直线上的最大点数量
let max = 0
// 用一个map来存储包括当前点最多可以有几个点同在直线
const map = new Map()
for (let j = 0; j < len; j++) {
if (i != j) {
const p2 = points[j]
if (isSamePoint(p1, p2)) {
same ++
} else {
const arg = getLinerfunction(p1, p2)
if (!map.has(arg)) {
map.set(arg, 2)
} else {
map.set(arg, map.get(arg) + 1)
}
}
}
}
map.forEach(arg => {
max = Math.max(max, arg)
})
// 如果max为0，说明所有点都是相同点，则直接返回len
if (max) {
max += same
} else {
return len
}
// 记得每次循环结束same归零，更新count
same = 0
count = Math.max(count, max)
}
return count
};
// 根据两点得到直线方程参数
function getLinerfunction (p1, p2) {
// 防止数据越界，对数据做一个缩放
const maxInt = 0xffffff
const k = ((p1[1] - p2[1]) % maxInt * maxInt) / (p1[0] - p2[0])
const b = p1[1] - k * p1[0]
return `${k}+${b}`
}
// 判断两个点是否是同一个点
function isSamePoint (p1, p2) {
return (p1[0] === p2[0]) && (p1[1] === p2[1])
}
leetcode 205. 同构字符串
题目地址：同构字符串
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function(s, t) {
const sLen = s.length
const tLen = t.length
if (sLen !== tLen) {
return false
}
if (!sLen && !tLen) {
return true
}
const maps = new Map()
const mapt = new Map()
for (let i = 0; i < sLen; i++) {
const sChar = s[i]
const tChar = t[i]
if (!maps.has(sChar)) {
maps.set(sChar, tChar)
} else {
if (maps.get(sChar) !== tChar) {
return false
}
}
if (!mapt.has(tChar)) {
mapt.set(tChar, sChar)
} else {
if (mapt.get(tChar) !== sChar) {
return false
}
}
}
return true
};
解法二：使用indexOf
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function(s, t) {
for(var i = 0; i< s.length; i++) {
if(s.indexOf(s[i]) !== t.indexOf(t[i]))
return false
}
return true;
};
leetcode 260. 只出现一次的数字 III
题目地址：只出现一次的数字 III
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumber = function(nums) {
const len = nums.length
const map = new Map()
const res = []
for (let i = 0; i < len; i++) {
const num = nums[i]
if (map.has(num)) {
map.delete(num)
} else {
map.set(num, 1)
}
}
map.forEach((val, key) => {
res.push(key)
})
return res
};
leetcode 290. 单词规律
题目地址：单词规律
/**
* @param {string} pattern
* @param {string} str
* @return {boolean}
*/
var wordPattern = function(pattern, str) {
const pArr = pattern.split('')
const sArr = str.split(' ')
const pLen = pArr.length
const sLen = sArr.length
if (pLen !== sLen) {
return false
}
const mapP = new Map()
const mapS = new Map()
for (let i = 0; i < pLen; i++) {
const pat = pArr[i]
const s = sArr[i]
if (!mapP.has(pat)) {
mapP.set(pat, s)
} else {
if (mapP.get(pat) !== s) {
return false
}
}
if (!mapS.has(s)) {
mapS.set(s, pat)
} else {
if (mapS.get(s) !== pat) {
return false
}
}
}
return true
};
leetcode 350. 两个数组的交集 II
题目地址：两个数组的交集 II
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
if (!nums1.length || !nums2.length) {
return []
}
const map1 = new Map()
const res = []
nums1.forEach(num => {
if (map1.has(num)) {
map1.set(num, map1.get(num) + 1)
} else {
map1.set(num, 1)
}
})
nums2.forEach(num => {
if (map1.has(num) && map1.get(num) > 0) {
res.push(num)
map1.set(num, map1.get(num) - 1)
}
})
return res
};
leetcode 389. 找不同
题目地址：找不同
Map
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
const map = new Map();
for(let i = 0; i < s.length; i++) {
const val = map.get(s[i]);
map.set(s[i], val ? val + 1 : 1);
}
for(let i = 0; i < t.length; i++) {
const val = map.get(t[i]);
if(val === 0 || val === undefined) {
return t[i];
} else {
map.set(t[i], val - 1);
}
}
};
解法二：for of
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
// 取巧方法， 改变了原数据
for(let item of s){
t = t.replace(item, '')
}
return t
};
leetcode 409. 最长回文串
题目地址：最长回文串
/**
* @param {string} s
* @return {number}
*/
var longestPalindrome = function(s) {
const map = new Map()
let max = 0
for(let char of s){
map.set(char, map.has(char) ? map.get(char) + 1 : 1)
if(map.get(char) === 2){
max += 2
map.set(char, 0)
}
}
return max == s.length ? max : max+1
};
leetcode 447. 回旋镖的数量
题目地址：回旋镖的数量
/**
* @param {number[][]} points
* @return {number}
*/
var numberOfBoomerangs = function(points) {
const len = points.length
if (len < 3) {
return 0
}
let count = 0
for (let i = 0; i < len; i++) {
const point1 = points[i]
// 用一个map存储其它点距离当前点point1有多少种距离可能
const map = new Map()
for (let j = 0; j < len; j++) {
if (i != j) {
const point2 = points[j]
const distance = getDistance(point1, point2)
if (!map.has(distance)) {
map.set(distance, 1)
} else {
map.set(distance, map.get(distance) + 1)
}
}
}
map.forEach(value => {
if (value > 1) {
const num = getArrangementNum(value)
count += num
}
})
}
return count
};
// 计算两点之间距离，这里其实没必要开根号
function getDistance (p1, p2) {
const distance = Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2))
return distance
}
// 计算排列数
function getArrangementNum (n) {
return n * (n - 1)
}
leetcode 451. 根据字符出现频率排序
题目地址：根据字符出现频率排序
/**
* @param {string} s
* @return {string}
*/
var frequencySort = function(s) {
const len = s.length
if (!len) {
return s
}
const map = new Map()
const temp = []
let str = ''
for (let i = 0; i < len; i++) {
const char = s[i]
if (!map.has(char)) {
map.set(char, 1)
} else {
map.set(char, map.get(char) + 1)
}
}
map.forEach((val, key) => {
temp.push({ val, key })
})
temp.sort((a, b) => b.val - a.val)
temp.forEach(item => {
str += item.key.repeat(item.val)
})
return str
};
leetcode 454. 四数相加 II
题目地址：四数相加 II
/**
* @param {number[]} A
* @param {number[]} B
* @param {number[]} C
* @param {number[]} D
* @return {number}
*/
var fourSumCount = function(A, B, C, D) {
const N = A.length
if (!N) {
return 0
}
let count = 0
const map = new Map()
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
const sum = C[i] + D[j]
if (!map.has(sum)) {
map.set(sum, 1)
} else {
map.set(sum, map.get(sum) + 1)
}
}
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
const sumCD = 0 - A[i] - B[j]
if (map.has(sumCD)) {
count += map.get(sumCD)
}
}
}
return count
};
leetcode 560. 和为K的子数组
题目地址：和为K的子数组
// nums[i]+…+nums[j]=prefixSum[j]−prefixSum[i−1]
// i === 0 => prefixSum[-1] = 0
var subarraySum = function (nums, k) {
const len = nums.length
let map = { 0: 1}
let prefixSum = 0
let ans = 0
for (let i = 0; i < len; i ++) {
prefixSum += nums[i]
if (map[prefixSum - k]) {
ans += map[prefixSum - k]
}
if (map[prefixSum]) {
map[prefixSum] ++
} else {
map[prefixSum] = 1
}
}
return ans
}
leetcode 575. 分糖果
题目地址：分糖果
/**
* @param {number[]} candies
* @return {number}
*/
var distributeCandies = function(candies) {
const len = candies.length
if (!len) {
return 0
}
const map = new Map()
candies.forEach((item) => {
map.set(item, map.has(item) ? map.get(item) + 1 : 1)
})
const count = map.size
if (count >= (len / 2)) {
return len / 2
}
return count
};
leetcode 697. 数组的度
题目地址：数组的度
/**
* @param {number[]} nums
* @return {number}
*/
var findShortestSubArray = function(nums) {
const len = nums.length
const map = new Map()
const temp = []
let max = 0
let res = Infinity
// 统计不同数的索引数组
for (let i = 0; i < len; i++) {
const num = nums[i]
let arr
if (map.has(num)) {
arr = map.get(num)
} else {
arr = []
}
arr.push(i)
map.set(num, arr)
max = Math.max(max, map.get(num).length)
}
// 找到复合数组度的数字中，首尾索引差值最小的
map.forEach(item => {
if (item.length === max) {
res = Math.min(res, item[item.length - 1] - item[0] + 1)
}
})
return res
};
leetcode 771. 宝石与石头
题目地址：宝石与石头
Map
/**
* @param {string} J
* @param {string} S
* @return {number}
*/
var numJewelsInStones = function(J, S) {
const jLen = J.length
const sLen = S.length
if (!jLen || !sLen) {
return 0
}
let count = 0
const map = new Map()
for (let i = 0; i < jLen; i++) {
map.set(J[i], true)
}
for (let j = 0; j < sLen; j++) {
if (map.has(S[j])) {
count ++
}
}
return count
};
解法二：使用字符串API
/**
* @param {string} J
* @param {string} S
* @return {number}
*/
var numJewelsInStones = function(J, S) {
let sarr = S.split("");
return sarr.filter(item=>J.includes(item)).length
};
leetcode 884. 两句话中的不常见单词
题目地址：两句话中的不常见单词
Map
/**
* @param {string} A
* @param {string} B
* @return {string[]}
*/
var uncommonFromSentences = function(A, B) {
const aArr = A.split(' ')
const bArr = B.split(' ')
const aLen = aArr.length
const bLen = bArr.length
const map = new Map()
const res = []
if (aLen) {
for (let i = 0; i < aLen; i++) {
map.set(aArr[i], map.has(aArr[i]) ? map.get(aArr[i]) + 1 : 1)
}
}
if (bLen) {
for (let i = 0; i < bLen; i++) {
map.set(bArr[i], map.has(bArr[i]) ? map.get(bArr[i]) + 1 : 1)
}
}
map.forEach((value, word) => {
if (map.get(word) === 1) {
res.push(word)
}
})
return res
};
解法二：使用数组API
/**
* @param {string} A
* @param {string} B
* @return {string[]}
*/
var uncommonFromSentences = function(A, B) {
let arr = (A + ' ' + B).split(' ');
return arr.filter(i => arr.indexOf(i) == arr.lastIndexOf(i));
};
leetcode 953. 验证外星语词典
题目地址：验证外星语词典
/**
* @param {string[]} words
* @param {string} order
* @return {boolean}
*/
var isAlienSorted = function(words, order) {
const wLen = words.length
if (wLen <= 1) {
return true
}
const map = new Map()
const len = order.length
for (let i = 0; i < len; i++) {
map.set(order[i], i)
}
for (let i = 0; i < wLen - 1; i++) {
const cur = words[i]
const next = words[i + 1]
const min = Math.min(cur.length, next.length)
for (let j = 0; j < min; j++) {
if (map.get(cur[j]) > map.get(next[j])) {
return false
} else if (map.get(cur[j]) < map.get(next[j])) {
break
}
}
// 后一个词是前一个词的前缀，返回false
if (cur.length > next.length && cur.replace(next, '') !== cur){
return false
}
}
return true
};
leetcode 961. 重复 N 次的元素
题目地址：重复 N 次的元素
/**
* @param {number[]} A
* @return {number}
*/
var repeatedNTimes = function(A) {
const len = A.length
const map = new Map()
for (let i = 0; i < len; i++) {
const item = A[i]
map.set(item, map.has(item) ? map.get(item) + 1 : 1)
if (map.get(item) === len / 2) {
return item
}
}
};
leetcode 1128. 等价多米诺骨牌对的数量
题目地址：等价多米诺骨牌对的数量
/**
* @param {number[][]} dominoes
* @return {number}
*/
// 如果有两个时，构成 1 对。
// 如果有三个时，构成 3 对。
// ……
// 如果有 n 个时，构成 n(n - 1)/2 对。
var numEquivDominoPairs = function(dominoes) {
const len = dominoes.length
if (len < 2) {
return 0
}
const map = new Map()
let count = 0
for (let i = 0; i < len; i++) {
const item = dominoes[i].sort((a, b) => a - b).join('')
if (!map.has(item)) {
map.set(item, 1)
} else {
map.set(item, map.get(item) + 1)
}
}
map.forEach(val => {
const increase = (val * (val - 1)) / 2
count += increase
})
return count
};
leetcode 1160. 拼写单词
题目地址：拼写单词
/**
* @param {string[]} words
* @param {string} chars
* @return {number}
*/
var countCharacters = function(words, chars) {
let needs = new Map(), res = 0;
for (let n of chars) {
needs.set(n, needs.has(n) ? needs.get(n) + 1 : 1);
}
for (let s of words) {
if (help(s, new Map(needs))) {
res += s.length;
}
}
return res;
};
function help(s, hash) {
for (let n of s) {
if (!hash.has(n)) {
return false;
} else {
hash.set(n, hash.get(n) - 1);
if (hash.get(n) < 0) return false;
}
}
return true;
}
leetcode 1331. 数组序号转换
题目地址：数组序号转换
/**
* @param {number[]} arr
* @return {number[]}
*/
var arrayRankTransform = function(arr) {
const len = arr.length
if (len === 0) {
return []
}
if (len === 1) {
return [1]
}
const temp = [...arr]
temp.sort((a, b) => a - b)
// 使用一个map记录排序信息
const map = new Map()
let index = 1
for (let i = 0; i < len; i++) {
if (!map.has(temp[i])) {
map.set(temp[i], index++)
}
}
const res = []
for (let i = 0; i < len; i++) {
if (map.has(arr[i])) {
res.push(map.get(arr[i]))
}
}
return res
};
leetcode 1346. 检查整数及其两倍数是否存在
题目地址：检查整数及其两倍数是否存在
解法一：暴力解法
/**
* @param {number[]} arr
* @return {boolean}
*/
var checkIfExist = function(arr) {
const len = arr.length
for (let i = 0;i < len - 1;i ++) {
for (let j = i + 1;j < len;j ++) {
if (arr[i] === arr[j] * 2 || arr[j] === arr[i] * 2) {
return true
}
}
}
return false
};
解法二：使用map缓存计算结果
/**
* @param {number[]} arr
* @return {boolean}
*/
var checkIfExist = function(arr) {
const len = arr.length
const map = new Map();
for (let i = 0; i < len; i++) {
const num1 = 2 * arr[i];
const num2 = arr[i] / 2;
if (map.has(num1) || map.has(num2)) {
return true;
}
map.set(arr[i], i);
}
return false;
};
leetcode 1365. 有多少小于当前数字的数字
题目地址：有多少小于当前数字的数字
/**
* @param {number[]} nums
* @return {number[]}
*/
var smallerNumbersThanCurrent = function(nums) {
const len = nums.length
const map = new Map()
let temp = [...nums]
temp.sort((a, b) => a - b)
const tLen = temp.length
const res = []
for (let i = 0; i < tLen; i ++) {
const item = temp[i]
!map.has(item) && map.set(item, i)
}
for (let i = 0; i < len; i ++) {
const item = nums[i]
res.push(map.get(item))
}
return res
};
4. Leetcode上Set相关题目
leetcode 202. 快乐数
题目地址：快乐数
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
if (n < 1) {
return false
}
const set = new Set()
let str = n.toString()
let sum = getSum(str)
set.add(sum)
while (sum !== 1) {
sum = getSum(sum.toString())
// 如果过程中出现已经得到过的和，且不是1，那么必然不会再出现1了，直接返回false
if (set.has(sum)) {
return false
}
set.add(sum)
}
return true
};
function getSum (n) {
let sum = 0
let nArr = n.split('')
nArr.forEach(num => {
sum += (num * 1 * num)
})
return sum
}
leetcode 349. 两个数组的交集
题目地址：两个数组的交集
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
if (!nums1.length || !nums2.length) {
return []
}
const set1 = new Set(nums1)
const set2 = new Set()
nums2.forEach(num => {
if (set1.has(num)) {
set2.add(num)
}
})
return [...set2]
};
leetcode 500. 键盘行
题目地址：键盘行
Set
/**
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(words) {
const len = words.length
const res = []
if (!len) {
return res
}
// 初始化set保存键盘每一行的信息
const first = new Set(['Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'])
const second = new Set(['A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'])
const third = new Set(['Z', 'X', 'C', 'V', 'B', 'N', 'M'])
for (let i = 0; i < len; i++) {
const word = words[i]
const wLen = word.length
const char = word[0].toUpperCase()
let inSameLine = true
// 用单词第一个字母确定它应该是第几行
let line = first
if (second.has(char)) {
line = second
} else if (third.has(char)) {
line = third
}
for (let j = 1; j < wLen; j++) {
// 发现不在该行的字母，则这个单词不在最终返回
if (!line.has(word[j].toUpperCase())) {
inSameLine = false
}
}
if (inSameLine) {
res.push(word)
}
}
return res
};
解法二：正则表达式
/**
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(words) {
return words.filter((word) => /^[qwertyuiop]+$|^[asdfghjkl]+$|^[zxcvbnm]+$/.test(word.toLowerCase()))
};
leetcode 820. 单词的压缩编码
题目地址：单词的压缩编码
/**
* @param {string[]} words
* @return {number}
*/
var minimumLengthEncoding = function (words) {
let set = new Set(words)
for (word of set) {
// 遍历set中的每个单词
for(let i = 1; i < word.length; i ++) {
// 取这个单词的子单词，如果set中存在则删除
let item = word.slice(i)
set.has(item) && set.delete(item)
}
}
let count = 0
set.forEach(item => count += item.length + 1)
return count
};
5. Leetcode上联合Map和Set的相关题目
381. O(1) 时间插入、删除和获取随机元素 - 允许重复
题目地址：O(1) 时间插入、删除和获取随机元素 - 允许重复
/**
* Initialize your data structure here.
*/
var RandomizedCollection = function() {
this.list = []
// 维护不同值索引
this.map = new Map()
};
/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.insert = function(val) {
this.list.push(val)
if (!this.map.has(val)) {
// 使用set维护每个值的索引
const set = new Set()
set.add(this.list.length - 1)
this.map.set(val, set)
return true
} else {
const set = this.map.get(val)
set.add(this.list.length - 1)
this.map.set(val, set)
return false
}
};
/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.remove = function(val) {
if (this.list.length && this.map.has(val) && this.map.get(val).size) {
const set = this.map.get(val)
// 要移除的值存储在list中的index(多个任选一个)
const arr = Array.from(set)
const index1 = arr.pop()
set.delete(index1)
this.map.set(val, set)
// 删除的不是list中最后一个值
if (index1 < this.list.length - 1) {
const lastVal = this.list[this.list.length - 1]
// 更新set里的索引（把本来最后一个值移动到要删除值的位置）
this.map.get(lastVal).delete(this.list.length - 1)
this.map.get(lastVal).add(index1)
// 这一步相当于，把要删除的值和list最后一个值交换
this.list.splice(index1, 1, lastVal)
}
// 移除list中最后一个值
this.list.pop()
return true
}
return false
};
/**
* Get a random element from the collection.
* @return {number}
*/
RandomizedCollection.prototype.getRandom = function() {
const index = Math.floor(Math.random() * this.list.length)
return this.list[index]
};
1189. “气球” 的最大数量
题目地址：“气球” 的最大数量
/**
* @param {string} text
* @return {number}
*/
var maxNumberOfBalloons = function(text) {
const map = new Map()
const set = new Set(['b', 'a', 'l', 'o', 'n'])
const len = text.length
let min = Infinity
for (let i = 0; i < len; i++) {
const str = text[i]
set.has(str) && map.set(str, map.has(str) ? map.get(str) + 1 : 1)
}
// 如果缺少部分字母，直接返回
if (map.size < 5) {
return false
}
map.forEach((item, key) => {
// 注意一个单词里有两个l和o
if (key === 'l' || key === 'o') {
item = Math.floor(item / 2)
}
min = Math.min(item, min)
})
return min
};
