1. What is a set

A set is a collection of unordered and unique (that is, unrepeatable) items. You can think of a set as an array with neither repeating elements nor any notion of order. In JavaScript, the implementation of a collection is Set()

Set common operations:

  1. duplicate removal
  2. Determines whether an element is in the set
  3. Find the intersection/difference/union
/ / to heavy
const arr = [1.1.2.2];
const arr2 = [...new Set(arr)];

// Determine if the element is in the set
const set = new Set(arr);
const has = set.has(3);

/ / intersection
const set2 = new Set([2.3]);
const set3 = new Set([...set].filter(item= > set2.has(item)));
Copy the code

2. Implement a collection

We tried to implement collections ourselves, and here are the common apis for collections.

  • Add (Element) : Adds a new element to the collection.
  • Delete (Element) : Removes an element from the collection.
  • Has (Element) : Returns true if the element is in the collection, false otherwise.
  • Clear () : Removes all elements from the collection.
  • Size () : Returns the number of elements contained in the collection. It is similar to the length property of an array.
  • Values () : Returns an array containing all the values(elements) in the collection.
class Set {
    constructor () {
        this.items = {}
    }

    has (element) {
        return Object.prototype.hasOwnProperty.call(this.items, element)
    }

    add (element) {
        if (!this.has(element)) {
            this.items[element] = element
            return true
        }
        return false
    }

    delete (element) {
        if (this.has(element)) {
            delete this.items[element]
            return true
        }
        return false
    }

    clear () {
        this.items = {}
    }

    size () {
        return Object.keys(this.items).length
    }

    values () {
        return Object.values(this.items)
    }
}
Copy the code

JAVA Set implementation: docs.oracle.com/en/java/jav…

3. Set operation

  • Union: For a given set of two sets, a new set containing all the elements of both sets is returned.
  • Intersection: For a given set of two sets, returns a new set containing elements in both sets.
  • Difference set: For a given set of two sets, return a new set containing all elements that exist in the first set and not in the second.
  • Subset: Verifies whether a given set is a subset of another set.

3.1 o and set

let union = a.concat(b.filter(v= >! a.includes(v)))new Set([...setA, ...setB])
Copy the code

3.2 masked

Intersection of two arrays

Intersection of two arrays (multiple solution)

3.3 difference set

let difference = a.concat(b).filter(v= >a.includes(v) && ! b.includes(v))new Set([...setA].filter(x= >! setB.has(x)))Copy the code

3.4 o subset

var intersection = function(nums1, nums2) {
    if (nums2.length < nums1.length) {
        return false
    }

    return nums1.every(value= > {
        return nums2.include(value)
    })
}
Copy the code

What is a dictionary

Dictionaries are similar to collections. Collections store elements as values. Dictionaries store elements as keys. Dictionaries are also called maps, symbol tables, or associative arrays. The dictionary in JS is realized by hash table, and the expression form of dictionary is Object and Map.

5. Implement a dictionary

defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } if (item === undefined) {
        return 'UNDEFINED';
    } if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString();
}

class ValuePair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    toString() {
        return ` [#The ${this.key}: The ${this.value}] `; }}class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }

    set(key, value) {
        if(key ! =null&& value ! =null) {
            const tableKey = this.toStrFn(key);
            this.table[tableKey] = new ValuePair(key, value);
            return true;
        }
        return false;
    }

    get(key) {
        const valuePair = this.table[this.toStrFn(key)];
        return valuePair == null ? undefined : valuePair.value;
    }

    hasKey(key) {
        return this.table[this.toStrFn(key)] ! =null;
    }

    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

    values() {
        return this.keyValues().map(valuePair= > valuePair.value);
    }

    keys() {
        return this.keyValues().map(valuePair= > valuePair.key);
    }

    keyValues() {
        return Object.values(this.table);
    }

    forEach(callbackFn) {
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break; }}}isEmpty() {
        return this.size() === 0;
    }

    size() {
        return Object.keys(this.table).length;
    }

    clear() {
        this.table = {}; }}Copy the code

JAVA Map implementation: docs.oracle.com/en/java/jav…

6. Leetcode

6.1 simple

1. Intersection of two arrays

Difficulty: Easy

Intersection of two arrays (multiple solution)

2. The sum of two Numbers

Difficulty: Easy

The sum of two numbers (dictionary)

3. Valid letter heterotopic word

Difficulty: Easy

Solution: valid letter heterotopic words

6.2 medium

1. The oldest string without repeating characters

Difficulty: Medium

Maximum string without repeating characters (sliding window)

2. Grouping of letter ectopic words

Difficulty: Medium

Solution: grouping of letter allotopic words

6.3 difficult

1. Minimum coverage substring

Difficulty: difficulty

Minimum coverage substring (sliding window)

For details, please refer to: Leetcode brush problem path

Keep updating ing…