Hello, brave friends, Hello, everyone, I am your mouth strong king xiaowu, healthy body, brain is not sick.

I have a wealth of hair loss techniques that can make you a veteran.

A look will be a waste is my main purpose, food to scratch my feet is my characteristics, humble with a trace of strong, stupid people have silly fortune is the biggest comfort to me.

Welcome to the Set & Map of primary Five algorithms.

preface

This series of articles is based on two books, “Algorithm Diagrams” and “Learning JavaScript Algorithms”, with the rest of the material as a supplement, along with my own insights. Strive to take you to appreciate the magic of this algorithm world with simple and interesting language.

Collection – Set

🦅 features: Unordered and unique

Analog implementation

We simulate a collection with JS and add the following methods to it:

  • Add (Element) : Adds elements

  • Delete (Element) : Deletes an element

  • Has (Element) : Whether the element is in the collection

  • Clear () : Clears the collection

  • Size () : number of elements in the collection

  • Values () : Returns an array containing all the elements of the collection

Array to heavy

“Disordered and unique.” What’s the difference between that and having the word “deduplicate” printed on your face

  • Extension operator internal logic is for… Of can be used to deconstruct Set

  • The array. from method converts a Set structure to an Array

[...new Set(arr)]; // Extend the operator
Array.from(new Set(arr)); // Array.from
Copy the code

Set operations

Let’s realize several operations of the following set: union set, intersection set, difference set and subset

🦅 and set

Formula: A ∪ B = {x ∣ x ∈ ∨ x ∈ B} A ∪ B = \ {x | x ∈ ∨ x ∈ B \} A ∪ B = {x ∣ x ∈ ∨ x ∈ B}

const unionSet = (
  set1: Set<unknown>, set2: Set<unknown>
) = > {
  return new Set([...set1, ...set2]);
}
Copy the code

🦅 intersection

Formula: A studying B = {x ∣ x ∈ A Sunday afternoon x ∈ B} A studying B = \ {x | x ∈ A Sunday afternoon x ∈ B \} A studying B = {x ∣ x ∈ A Sunday afternoon x ∈ B}

const intersection = (
  set1: Set<unknown>, set2: Set<unknown>
) = > {
  return new Set(
    [...set1].filter(
      item= > set2.has(item)
    )
  );
}
Copy the code

🦅 difference set

Formula: A – B = {x ∣ x ∈ A Sunday afternoon x ∉ B} A – B = \ {x | x ∈ A Sunday afternoon x ∉ B \} A – B = {x ∣ x ∈ A Sunday afternoon x ∈ / B}

const difference = (
  set1: Set<unknown>, set2: Set<unknown>
) = > {
  return new Set(
    [...set1].filter(
      item= >! set2.has(item) ) ); }Copy the code

🦅 subset

Formula: A ⊆ B = {x ∣ ∈ x – x ∈ B} A ⊆ B = \ {x | x ∈ A – > x ∈ B \} A ⊆ B = {x ∣ ∈ x – x ∈ B}

const subSet = (
  set1: Set<unknown>, set2: Set<unknown>
) = > {
  for (let item of set1) {
    if(! set2.has(item))return false;
  }
  return true;
}
Copy the code

The dictionary – Map

🦅 class object, a collection of key-value pairs

Analog implementation

We simulate a simplified version of a dictionary with a string key as a js object and add the following methods to it:

  • Set (key, value) : adds elements

  • Get (key) : gets elements

  • Remove (key) : removes elements

  • Has (key) : Whether the element is in the dictionary

  • Clear () : Clears the dictionary

  • Size () : number of elements in the dictionary

  • Keys () : Returns an array of all keys in the dictionary

  • Values () : Returns an array of all values in the dictionary

🦅 ES6 Map Supplementary description

Its “key” can be any type of value, not just a string

const arr = [1.2.3];
const map = new Map([[arr, Yellow Knife Little Five], [arr, 'Two Dogs']]);
Copy the code

Note that only references to the same object are treated as the same key by the Map structure

const map = new Map[[[[1.2.3].Yellow Knife Little Five], [[1.2.3].'Two Dogs']]);
Copy the code

The sum of two Numbers

  • During the loop, Map is used to store the values and subscripts of the array

  • If target-current exists in the Map, fetch the subscript

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

Afterword.

🔗 Links to other articles in this series:

  • Sorting algorithm

  • The stack and queue

  • The list

  • Big talk prototype chain

🔗 Reference link: Ruan Yifeng – ECMAScript 6 Introduction – Set and Map data structures