(Disclaimer: All questions are non-member questions in LeetCode)
In ES2015, JavaScript has added two new data structure implementations, they are Set and Map. Here is a review of the basic usage of these two data structures
1. Basic usage of Set (from MDN)
concept
The Set object allows you to store a unique value of any type, either a primitive value or an object reference.
grammar
new Set([iterable]);
Iterable If you pass an iterable, all of its elements are added to a new Set without repeating. If this parameter is not specified or its value is null, the new Set is null.
Instance attributes
-
Set.prototype.constructorReturns the constructor of the instance. The default is Set.
-
Set.prototype.sizeReturns the number of values of a Set object.
Instance methods
Set.prototype.add(value)
Adds an element to the end of the Set. Returns the Set object.
Set.prototype.clear()
Removes all elements from Set.
Set.prototype.delete(value)
Returns set.prototype. has(value) the value that would have been returned before this operation (that is, true if the element exists, false otherwise). Set.prototype.has(value) will then return false.
Set.prototype.entries()
Returns a new iterator object that contains the [value, value] array of the values of all elements in Set in insertion order. To keep the method similar to the Map object, the keys and values of each value are equal.
Set.prototype.forEach(callbackFn[, thisArg])
CallBackFn is called once for each value in the Set, in insertion order. If thisArg argument is provided, this in the callback will be that argument.
Set.prototype.has(value)
Returns a Boolean value indicating whether the value exists in the Set.
Set.prototype.keys()
As with the values() method, returns a new iterator object containing the values of all elements in Set in insertion order.
Set.prototype.values()
Returns a new iterator object that contains the values of all elements in Set in insertion order.
Set.prototype[@@iterator]()
Returns a new iterator object that contains the values of all elements in Set in insertion order.
2. Basic usage of Map (from MDN)
concept
The Map object holds key-value pairs and can remember the original insertion order of the keys. Any value (object or raw value) can be a key or a value.
A Map object iterates based on the insertion order of the elements in the object – a for… The of loop returns an array of the form [key, value] after each iteration
grammar
new Map([iterable])
Iterable can be an array or any other Iterable object whose elements are key-value pairs (an array of two elements, for example: [[1, ‘one’],[2, ‘two’]]). Each key-value pair is added to the new Map. Null will be treated as undefined.
Instance attributes
Map.prototype.constructor
Returns a function that creates a prototype of the instance. The default is the Map function.
Map.prototype.size
Returns the number of key/value pairs for the Map object.
Instance methods
Map.prototype.clear()
Removes all key/value pairs from the Map object.
Map.prototype.delete(key)
If the element exists in the Map object, remove it and return true; Otherwise return false if the element does not exist. A subsequent call to map.prototype. has(key) returns false.
Map.prototype.entries()
Returns a new Iterator containing the [key, value] array of each element in the Map, in insertion order.
Map.prototype.forEach(callbackFn[, thisArg])
The callbackFn function is called once for each key-value pair in the Map, in insertion order. If thisArg is provided to forEach, it will be used as this in each callback.
Map.prototype.get(key)
Returns the value of the key, or undefined if none exists.
Map.prototype.has(key)
Returns a Boolean value indicating whether the Map instance contains the value corresponding to the key.
Map.prototype.keys()
Returns a new Iterator containing the keys of each element in the Map in insertion order.
Map.prototype.set(key, value)
Sets the value of the key in the Map object. Returns the Map object.
Map.prototype.values()
Returns a new Iterator containing the values of each element in the Map in insertion order.
Map.prototype[@@iterator]()
Returns a new Iterator containing the [key, value] array of each element in the Map, in insertion order.
3. LeetcodeMapRelated topics
Leetcode 1. Sum of two numbers
Add two numbers
/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
var map = new Map(a);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); }}};Copy the codeSolution two: violence solution
/** * @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[]}.Copy the codeLeetcode 49. Grouping of letter heterotopic words
Topic address: letter allotopic word grouping
/** * @param {string[]} strs * @return {string[][]} */
var groupAnagrams = function(strs) {
const len = strs.length
const res = []
const map = new Map(a)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
};
Copy the codeLeetcode 146. LRU caching mechanism
LRU caching mechanism
this.map.keys().next()
/**
* @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) */
Copy the codeLeetcode 149. Maximum number of points on a line
Title address: maximum number of points on a line
/** * @param {number[][]} points * @return {number} */
var maxPoints = function(points) {
const len = points.length
if (len <= 2) {
return len
}
// There are at least two points on a straight line
let count = 2
// Store the number of similarities
let same = 0
for (let i = 0; i < len; i++) {
const p1 = points[i]
// Save the maximum number of points on a line for each cycle
let max = 0
// Use a map to store up to a few points on the same line
const map = new Map(a)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)
})
// If Max is 0, all points are the same, and len is returned
if (max) {
max += same
} else {
return len
}
// Remember that at the end of each loop same returns to zero and count is updated
same = 0
count = Math.max(count, max)
}
return count
};
// Get the parameters of the line equation according to two points
function getLinerfunction (p1, p2) {
// Make a scale to prevent data from crossing boundaries
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}`
}
// Check whether the two points are the same point
function isSamePoint (p1, p2) {
return (p1[0] === p2[0]) && (p1[1] === p2[1])}Copy the codeLeetcode 205. Isomorphic string
Subject address: isomorphic string
/** * @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(a)const mapt = new Map(a)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
};
Copy the codeSolution 2: Use 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;
};
Copy the codeLeetcode 260. The number III that occurs only once
Title address: the number III that appears only once
/** * @param {number[]} nums * @return {number[]} */
var singleNumber = function(nums) {
const len = nums.length
const map = new Map(a)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
};
Copy the codeLeetcode 290. Word rules
The rules of words
/** * @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(a)const mapS = new Map(a)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
};
Copy the codeLeetcode 350. Intersection of two arrays II
Topic address: intersection of two arrays II
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */
var intersect = function(nums1, nums2) {
if(! nums1.length || ! nums2.length) {return[]}const map1 = new Map(a)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
};
Copy the codeLeetcode 389. Look different
Title address: Find different
Map
/** * @param {string} s * @param {string} t * @return {character} */
var findTheDifference = function(s, t) {
const map = new Map(a);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); }}};Copy the codeFor example
/** * @param {string} s * @param {string} t * @return {character} */
var findTheDifference = function(s, t) {
// Change the original data
for(let item of s){
t = t.replace(item, ' ')}return t
};
Copy the codeLeetcode 409. Longest palindrome string
Title address: longest palindrome string
/** * @param {string} s * @return {number} */
var longestPalindrome = function(s) {
const map = new Map(a)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
};
Copy the codeLeetcode 447. Number of boomerangs
Number of boomerangs
/** * @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]
// Use a map to store the number of possible distances from other points to point1
const map = new Map(a)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
};
// Calculate the distance between two points. There is no need to take the square root
function getDistance (p1, p2) {
const distance = Math.sqrt(Math.pow(p1[0] - p2[0].2) + Math.pow(p1[1] - p2[1].2))
return distance
}
// Count permutations
function getArrangementNum (n) {
return n * (n - 1)}Copy the codeLeetcode 451. Sort by frequency of occurrence of characters
Title address: Sort by character frequency
/** * @param {string} s * @return {string} */
var frequencySort = function(s) {
const len = s.length
if(! len) {return s
}
const map = new Map(a)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
};
Copy the codeLeetcode 454. Addition of four numbers II
Add four numbers 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(a)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
};
Copy the codeLeetcode 560. And a subarray of K
Subject address: and subarray of K
/ / nums [I] +... [j] + nums = 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
}
Copy the codeLeetcode 575. Divide the candy
Title address: Share the candy
/** * @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
};
Copy the codeLeetcode 697. Degree of array
Title address: the degree of the array
/** * @param {number[]} nums * @return {number} */
var findShortestSubArray = function(nums) {
const len = nums.length
const map = new Map(a)const temp = []
let max = 0
let res = Infinity
// Count different numbers of indexed array
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)
}
// Find the number with the smallest index difference between the beginning and end of the compound array degree
map.forEach(item= > {
if (item.length === max) {
res = Math.min(res, item[item.length - 1] - item[0] + 1)}})return res
};
Copy the codeLeetcode 771. Gems and Stones
Gems and Stones
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(a)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
};
Copy the codeSolution 2: Use the string 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
};
Copy the codeLeetcode 884. Uncommon words in two sentences
Topic address: Uncommon words in two sentences
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(a)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
};
Copy the codeSolution 2: Use the array 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));
};
Copy the codeLeetcode 953. Verify the alien language dictionary
Subject address: Verification of alien language dictionary
/** * @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(a)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}}// The latter word is the prefix of the previous word, and returns false
if (cur.length > next.length && cur.replace(next, ' ') !== cur){
return false}}return true
};
Copy the codeLeetcode 961. Element repeated N times
Title address: element repeated N times
/** * @param {number[]} A * @return {number} */
var repeatedNTimes = function(A) {
const len = A.length
const map = new Map(a)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
}
}
};
Copy the codeLeetcode 1128. Number of pairs of equivalent dominoes
Number of equivalent pairs of dominoes
/** * @param {number[][]} dominoes * @return {number} */
// If there are two, form a pair.
// If there are three pairs, form three pairs.
/ /...
// If there are n pairs, form n(n-1)/2 pairs.
var numEquivDominoPairs = function(dominoes) {
const len = dominoes.length
if (len < 2) {
return 0
}
const map = new Map(a)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
};
Copy the codeLeetcode 1160. Spell words
Title address: Spelling words
/** * @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;
}
Copy the codeLeetcode 1331. Array number conversion
Title address: array number conversion
/** * @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)
// Use a map to record sorting information
const map = new Map(a)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
};
Copy the codeLeetcode 1346. Check if integers and their double multiples exist
Check if integers and their multiples exist
Solution 1: violent solution
/** * @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
};
Copy the codeSolution 2: Use map cache to calculate results
/** * @param {number[]} arr * @return {boolean} */
var checkIfExist = function(arr) {
const len = arr.length
const map = new Map(a);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;
};
Copy the codeLeetcode 1365. How many numbers are smaller than the current number
Title address: How many numbers are smaller than the current number
/** * @param {number[]} nums * @return {number[]} */
var smallerNumbersThanCurrent = function(nums) {
const len = nums.length
const map = new Map(a)let temp = [...nums]
temp.sort((a, b) = > a - b)
const tLen = temp.length
const res = []
for (let i = 0; i < tLen; i ++) {
constitem = 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
};
Copy the code4. LeetcodeSetRelated topics
Leetcode 202. Happiness number
Title address: happiness number
/** * @param {number} n * @return {boolean} */
var isHappy = function(n) {
if (n < 1) {
return false
}
const set = new Set(a)let str = n.toString()
let sum = getSum(str)
set.add(sum)
while(sum ! = =1) {
sum = getSum(sum.toString())
// If the sum is not 1, then it must not be 1 again and return 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
}
Copy the codeLeetcode 349. Intersection of two arrays
Subject address: intersection of two arrays
/** * @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]
};
Copy the codeLeetcode 500. Keyboard line
Subject address: keyboard line
Set
/** * @param {string[]} words * @return {string[]} */
var findWords = function(words) {
const len = words.length
const res = []
if(! len) {return res
}
// Initialize set to hold information for each line of the keyboard
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
// Use the first letter of the word to determine what line it should be
let line = first
if (second.has(char)) {
line = second
} else if (third.has(char)) {
line = third
}
for (let j = 1; j < wLen; j++) {
// If a letter not in the line is found, the word is not finally returned
if(! line.has(word[j].toUpperCase())) { inSameLine =false}}if (inSameLine) {
res.push(word)
}
}
return res
};
Copy the codeSolution 2: Regular expression
/** * @param {string[]} words * @return {string[]} */
var findWords = function(words) {
return words.filter((word) = > /^[qwertyuiop]+$|^[asdfghjkl]+$|^[zxcvbnm]+$/.test(word.toLowerCase()))
};
Copy the codeLeetcode 820. Compressed encoding of words
Topic address: compressed coding of words
/** * @param {string[]} words * @return {number} */
var minimumLengthEncoding = function (words) {
let set = new Set(words)
for (word of set) {
// Iterate over each word in set
for(let i = 1; i < word.length; i ++) {
// Take a subword of the word, delete it if it exists in set
let item = word.slice(i)
set.has(item) && set.delete(item)
}
}
let count = 0
set.forEach(item= > count += item.length + 1)
return count
};
Copy the code5. Syndicate on LeetcodeMapandSetRelated topics
381. O(1) Time to insert, remove and get random elements – allow repetition
O(1) Time to insert, remove, and get random elements – allow repetition
/** * Initialize your data structure here. */
var RandomizedCollection = function() {
this.list = []
// Maintain different value indexes
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)) {
// Use set to maintain an index for each value
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)
// The value to be removed is stored in the index of the list.
const arr = Array.from(set)
const index1 = arr.pop()
set.delete(index1)
this.map.set(val, set)
// Delete not the last value in the list
if (index1 < this.list.length - 1) {
const lastVal = this.list[this.list.length - 1]
// Update the index in the set (move the last value to the place where the value is to be deleted)
this.map.get(lastVal).delete(this.list.length - 1)
this.map.get(lastVal).add(index1)
// This is equivalent to swapping the value to be deleted with the last value in the list
this.list.splice(index1, 1, lastVal)
}
// Remove the last value in the 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]
};
Copy the codeMaximum number of “balloons”
Title address: maximum number of “balloons”
/** * @param {string} text * @return {number} */
var maxNumberOfBalloons = function(text) {
const map = new Map(a)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 some letters are missing, return directly
if (map.size < 5) {
return false
}
map.forEach((item, key) = > {
// Notice that there are two l's and o's in one word
if (key === 'l' || key === 'o') {
item = Math.floor(item / 2)
}
min = Math.min(item, min)
})
return min
};
Copy the code