# DSA: Build DS

## Hash Table

[705. Design HashSet (Easy)](https://leetcode.com/problems/design-hashset/)

> Design a HashSet without using any built-in hash table libraries. Implement MyHashSet class:
> - `void add(key)` Inserts the value `key` into the HashSet.
> - `bool contains(key)` Returns whether the value `key` exists in the HashSet or not.
> - `void remove(key)` Removes the value `key` in the HashSet. If `key` does not exist in the HashSet, do nothing.

:::spoiler Solution (Complexity irrelevant)
建一个 vector，每个 vector element 都塞一个 linked list，避免 collision，这是法一（法二为 open address），当 vector 太小时，用 expand 去扩增（Java 的扩增时机为当哈希表 75% 满时扩增为两倍）。思路详解可以参考下方链接。另外是 constructor 那边要习惯 C++ 的做法。[706. Design HashMap设计哈希映射【LeetCode单题讲解系列】](https://www.youtube.com/watch?v=UFCLHxgQa8w)

class MyHashSet {
private:
    vector<list<int>> hashSet;
    static const int hashSetSize = 800;
    // static constexpr float loadFactor = 0.75f;
    static int hash(int key){
        return key % hashSetSize;
    }
    // int currentSize = 0;
public:
    MyHashSet(): hashSet(hashSetSize) {}
    
    // void expand() {
    //     int newHashSetSize = hashSetSize * 2;
    //     vector<list<int>> newHashSet(newHashSetSize); 

    //     for (int i = 0; i < hashSetSize; ++i) {
    //         for (int value: hashSet[i]) {
    //             int h = i % newHashSetSize;
    //             newHashSet[h].push_back(value);
    //         }
    //     }
    //     hashSet = std::move(newHashSet);
    //     // hashSetSize = newHashSetSize;
    // }

    void add(int key) {

        // // If the load factor exceeds the threshold, expand the table
        // if (currentSize >= hashSetSize * loadFactor) {
        //     expand();
        // }

        int h = hash(key);
        for (auto i = hashSet[h].begin(); i != hashSet[h].end(); ++i) {
            if (*i == key) {
                return;
            }
        }
        hashSet[h].push_back(key);
        // currentSize++;
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto i = hashSet[h].begin(); i!= hashSet[h].end(); ++i) {
            if (*i == key) {
                hashSet[h].erase(i);
                return;
                // currentSize--;
            }
        }

    }
    
    bool contains(int key) {
        int h = hash(key);
        for (auto i = hashSet[h].begin(); i != hashSet[h].end(); ++i) {
            if (*i == key) {
                return true;
            }
        }
        return false;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

:::

[706. Design HashMap (Easy)](https://leetcode.com/problems/design-hashmap/description/)

> Design a HashMap without using any built-in hash table libraries. Implement the MyHashMap class:
> - `MyHashMap()` initializes the object with an empty map.
> - `void put(int key, int value)` inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
> - `int get(int key)` returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
> - `void remove(key)` removes the key and its corresponding value if the map contains the mapping for the key.

:::spoiler Solution (Time `O(n^2)`, Space `O(n)`)

同 705 题，只是现在不只 key，多加了 value，变成 key-value pair。

class MyHashMap {
private:
    vector<list<pair<int, int>>> hashMap;
    static const int hashMapSize = 800;
    // static constexpr float loadFactor = 0.75f;
    static int hash(int key){
        return key % hashMapSize;
    }
    // int currentSize = 0;

public:
    MyHashMap(): hashMap(hashMapSize) {}
    
    void put(int key, int value) {
        int h = hash(key);
        for (auto i = hashMap[h].begin(); i != hashMap[h].end(); ++i) {
            if ((*i).first == key) {
                (*i).second = value;
                return;
            }
        }
        hashMap[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hash(key);
        for (auto i = hashMap[h].begin(); i != hashMap[h].end(); ++i) {
            if ((*i).first == key) {
                return (*i).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto i = hashMap[h].begin(); i != hashMap[h].end(); ++i) {
            if ((*i).first == key) {
                hashMap[h].erase(i);
                return;
            }
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

:::

[707. Design Linked List (Medium)](https://leetcode.com/problems/design-linked-list/description/)

> Design your implementation of the linked list. You can choose to use a singly or doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
>
> Implement the `MyLinkedList` class:
>
> - `MyLinkedList()` Initializes the `MyLinkedList` object.
> - int get(int index) Get the value of the `index-th` node in the linked list. If the index is invalid, return `-1`.
> `void addAtHead(int val)` Add a node of value `val` before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
> `void addAtTail(int val)` Append a node of value `val` as the last element of the linked list.
> `void addAtIndex(int index, int val)` Add a node of value `val` before the `index-th` node in the linked list. If `index` equals the length of the linked list, the node will be appended to the end of the linked list. If `index` is greater than the length, the node will not be inserted.
> `void deleteAtIndex(int index)` Delete the `index-th` node in the linked list, if the `index` is valid.

:::spoiler

:::