concept

  1. A data structure used to store unique values, usually as key-value pairs.
  2. Es6 has a dictionary data structure called a map. Map

Map Common Operations (Add, Delete, modify and Check)

increase

Const m = new Map() m.et ('a','aa') m.et ('b','bb'Copy the code

The query

M.geet ('a') // Query the value corresponding to the key by the get method and the keyCopy the code

delete

M.clear () m.clear() m.clear() m.clear() m.clear() m.clear() m.clear(Copy the code

Modify the

M.et ('a','aaa') // Call the set method again, passing in the key you want to change and the changed value, overriding the original valueCopy the code

Leetcode related algorithm problem

T349 Intersection of two arrays

  • Given two arrays, write a function to calculate their intersection.
  • Example 1:
  • Input: nums1 = [1,2,2,1], nums2 = [2,2]
  • Output: [2]
  • Example 2:
  • Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  • Output: [9, 4]

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking: the first array traversal, then traverse the array into the newly created map, k for this number, v is true, then traverse the second array, if the second, the number to invoke the get method can get the value is proved in the map already has this number, pushes it into the array, then the kv to delete

var intersection = function(nums1, nums2) {
    const map = new Map()
    nums1.forEach(item => {
        map.set(item,true)
    })
    const res = []
    nums2.forEach(item => {
        if(map.get(item)){
            res.push(item)
            map.delete(item)
        }
    })
    return res
};
Copy the code

T20 valid parentheses

  • Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

  • A valid string must meet the following requirements:

  • The opening parenthesis must be closed with a closing parenthesis of the same type.

  • The opening brackets must be closed in the correct order.

  •  

  • Example 1:

  • Input: s = “()”

  • Output: true,

  • Example 2:

  • Input: s = “()[]{}”

  • Output: true,

  • Example 3:

  • Input: s = “(]”

  • Output: false

  • Example 4:

  • Input: s = “([)]”

  • Output: false

  • Example 5:

  • Input: s = “{[]}”

  • Output: true,

Source: LeetCode link: leetcode-cn.com/problems/va… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

If map.get (I) is not flase, it is proved to be an open parenthesis; otherwise, it is a close parenthesis. Then, the top element of the stack is called get method to get the corresponding value for comparison, and the same is out of the stack

var isValid = function(s) { if(s.length % 2 ! = 0 ){return false} const stack = [] const map = new Map() map.set('(',')') map.set('{','}') map.set('[',']') for (let i = 0; i< s.length; i++){ let c = s[i] if(map.get(c)){ stack.push(c) }else{ const top = stack[stack.length-1] if ( map.get(top) === c){ stack.pop() }else{ return false } } } return stack.length === 0 };Copy the code

T1: Sum of two numbers:

  • Given an integer array nums and an integer target, find the two integers in the array whose sum is target and return their array indices.
  • You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.
  • You can return the answers in any order.
  • Example 1:
  • Nums = [2,7,11,15], target = 9
  • Output: [0, 1]
  • Return [0, 1] because nums[0] + nums[1] == 9

Source: LeetCode link: leetcode-cn.com/problems/tw… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source. Save the difference between the number and target -I to map for matching

var twoSum = function(nums, target) { const map = new Map() for(let i =0; i<nums.length; i++){ let tar = target - nums[i] if(map.has(tar)){ return([map.get(tar),i]) }else{ map.set(nums[i],i) } } };Copy the code

T3 no duplicate longest string

Given a string s, find the longest string that does not contain repeating characters.

Example 1:

Input: s = “abcabCBb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3. Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without duplicate characters is “b”, its length is 1. Example 3:

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Double pointer sliding window, and record the length of the current longest string, the data traversed into the map

var lengthOfLongestSubstring = function(s) { let l = res = 0 const map = new Map() for(let r = 0; r<s.length; r++){ if(map.has(s[r]) && map.get(s[r]) >= l){ l = map.get(s[r]) + 1 } res = Math.max(res,r-l+1) map.set(s[r],r) } return res };Copy the code