ARTS打卡第七周

Algorithm：每周至少做一個(gè) leetcode 的算法題

705. 設(shè)計(jì)哈希集合

不使用任何內(nèi)建的哈希表庫(kù)設(shè)計(jì)一個(gè)哈希集合（HashSet）。

實(shí)現(xiàn) MyHashSet 類：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在這個(gè)值 key 。
void remove(key) 將給定值 key 從哈希集合中刪除。如果哈希集合中沒(méi)有這個(gè)值，什么也不做。

示例：
輸入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
輸出：
[null, null, null, true, false, null, true, null, false]

解釋：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/design-hashset
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

代碼:

解法一：

class MyHashSet {
public:
    /** Initialize your data structure here. */
    MyHashSet() {
        m_vec = vector<int>(1000001,-1);
    }

    void add(int key) {
        m_vec[key] = 1;
    }

    void remove(int key) {
        m_vec[key]= -1;
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return m_vec[key] == 1;
    }

    private:
        vector<int> m_vec;

};

通過(guò)vector取值為常數(shù)時(shí)間的特性，保持哈希的取值常數(shù)性。缺點(diǎn)是1000000個(gè)vector的內(nèi)存占用大

解法二：

struct Node {
int val;
Node *next;
Node(int val) : val(val), next(nullptr) {}
};
const int len = 100;
class MyHashSet {

public:
    vector<Node*> arr; //本題題點(diǎn)
                   /** Initialize your data structure here. */
    MyHashSet() {
        arr = vector<Node*>(len, new Node(-1));
    }

    void add(int key) {
        int haval = key % len;
        Node* temp = arr[haval];
        if (temp->val != -1) {
            while (temp) {
                if (temp->val == key)  return;
                if (!(temp->next)) {
                    Node *node = new Node(key);
                    temp->next = node;
                    return;
                }
                temp = temp->next;
            }
        }
        else {
            temp->val = key;
            return;
        }
    }

    void remove(int key) {
        int haval = key % len;
        Node* temp = arr[haval];
        if (temp->val != -1) {
            while (temp) {
                if (temp->val == key) {
                    temp->val = -1;
                    return;
                }
                temp = temp->next;
            }
        }
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int haval = key % len;
        Node* temp = arr[haval];
        while (temp) {
            if (temp->val == key)    return true;
            temp = temp->next;
        }
        return false;
    }
};

通過(guò)取余的哈希算法，將輸入值存入vector中的列表中，缺點(diǎn)是：哈希沖突的值讀取速度會(huì)慢，優(yōu)點(diǎn)是：內(nèi)存占用少

Review：閱讀并點(diǎn)評(píng)至少一篇英文技術(shù)文章

[C++變得更加python化]](https://preshing.com/20141202/cpp-has-become-more-pythonic/)

目前很多的公司還在考C11的技術(shù)新點(diǎn)，這說(shuō)明C11的進(jìn)步是比較大的，同時(shí)也是比較穩(wěn)定的，公認(rèn)的可以一起使用的，不知道C20的特性何時(shí)能被廣泛使用

Tip：學(xué)習(xí)至少一個(gè)技術(shù)技巧

class TestObject
{
    public:

    void TestA()
    {
        printf("this is FuncA");
    }

    virtual void TestB()
    {
        printf("this is FuncB");
    }
}

TestObject* A = nullptr;
A.TestA();
A.TestB();

輸出結(jié)果：
this is FuncA
崩潰

因?yàn)槌蓡T函數(shù)的調(diào)用實(shí)際上是為成員函數(shù)添加一個(gè)this的隱式參數(shù)，使得程序知道需要調(diào)用哪個(gè)對(duì)象的成員變量。
TestA中沒(méi)有使用this的任何變量，所以不會(huì)遇到空指針的崩潰問(wèn)題。
TestB是一個(gè)虛函數(shù)，需要訪問(wèn)對(duì)象的虛函數(shù)指針，而對(duì)象為nullptr，導(dǎo)致無(wú)法尋找對(duì)應(yīng)的函數(shù)，直接崩潰。

真實(shí)無(wú)法想象，這樣的程序?yàn)槭裁匆獙?，不使用成員變量的函數(shù)為什么定義在成員函數(shù)中，匪夷所思。

Share：分享一篇有觀點(diǎn)和思考的技術(shù)文章

windbg調(diào)試確實(shí)是一個(gè)比較有意思的東西，包含堆棧信息，根據(jù)指令進(jìn)行堆棧分析，讓我更加的認(rèn)識(shí)到程序運(yùn)行的奧秘。
不過(guò)自己的反編譯能力實(shí)在是有限，之后要學(xué)學(xué)匯編指令、爭(zhēng)取在這方面能有所進(jìn)步。