1. Introduction to dictionaries
-
Like collections, a dictionary is a data structure that stores unique values, but it is stored as key-value pairs.
-
Use the Map for ES6
1.1 Common operations of dictionaries
const m = new Map(a);/ / to add
m.set('a'.'aa');
m.set('b'.'bb');
/ / delete
m.delete('b');
m.clear();
/ / change
m.set('a'.'aaa')
/ / check
m.get('a');
Copy the code
2. LeetCode:349. Intersection of two arrays
2.1 Solution ideas
- Find both nums1 and nums2
- Create a dictionary mapping that records the values in NUMs1
- Walk through nums2 to find values that are also in nums1
2.2 Steps to solve the problem
- Create a new dictionary, iterate through NUMs1, and populate the dictionary
- Iterate through NUMs2, select and delete values from the dictionary as they come across them.
/ * * *@param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}* /
var intersection = function (nums1, nums2) {
// Set Set implementation
// return [...new Set(nums1)].filter(item => nums2.includes(item))
const map = new Map(a); nums1.forEach(n= > {
map.set(n, true)})const res = [];
nums2.forEach(n= > {
if(map.get(n)) { res.push(n); map.delete(n); }})return res
};
Copy the code
3. LeetCode:20. Valid brackets
/ * * *@param {string} s
* @return {boolean}* /
var isValid = function (s) {
if (s.length % 2= = =1) { return false }
const stack = [];
const map = new Map(a); map.set('('.') ')
map.set('['.'] ')
map.set('{'.'} ')
for (let i = 0; i < s.length; i += 1) {
const c = s[i];
if (c === '(' || c === '{' || c === '[') {
stack.push(c)
} else {
const t = stack[stack.length - 1];
if (
map.get(t) === c
) {
stack.pop();
} else {
return false; }}}return stack.length === 0;
};
Copy the code
4. LeetCode: 1. Sum of two numbers
4.1 Solution idea
Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code
- Think of NUMs as kissers
- Think of target as a matching condition
- Set up a marriage agency with a dictionary to store the numbers and subscripts of your loved ones
4.2 Steps to solve the problem
- Create a new dictionary as a marriage agency
- Nums in the value, one by one to introduce looking for objects, no more than the first register, there is the right hand
/ * * *@param {number[]} nums
* @param {number} target
* @return {number[]}* /
var twoSum = function (nums, target) {
const map = new Map(a)for (let i = 0; i < nums.length; i += 1) {
const n = nums[i];
const n2 = target - n;
if (map.has(n2)) {
return [map.get(n2), i]
} else {
map.set(n, i)
}
}
};
Copy the code
Execution time: 56 ms, beating 99.77% of all JavaScript commits
Memory consumption: 39.9 MB, beating 37.04% of all JavaScript commits
The memory consumption is O(n), and we can do it by binary search, time for space
5. LeetCode: 3. The oldest string without repeating characters
6. LeetCode: 76. Minimum coverage substring
7. Conclusion:
- A dictionary, like a collection, is a data structure that stores unique values, but it does not
Key/value pair
In the form of - ES6 has a dictionary named Map
- Dictionary common operations: add, delete, change and check key – value pairs