ARTS打卡第七周

Algorithm：每周至少做一个 leetcode 的算法题

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：
输入：
["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 ，（已移除）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-hashset
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码:

解法一：

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;

};

通过vector取值为常数时间的特性，保持哈希的取值常数性。缺点是1000000个vector的内存占用大

解法二：

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

public:
    vector<Node*> arr; //本题题点
                   /** 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;
    }
};

通过取余的哈希算法，将输入值存入vector中的列表中，缺点是：哈希冲突的值读取速度会慢，优点是：内存占用少

Review：阅读并点评至少一篇英文技术文章

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

目前很多的公司还在考C11的技术新点，这说明C11的进步是比较大的，同时也是比较稳定的，公认的可以一起使用的，不知道C20的特性何时能被广泛使用

Tip：学习至少一个技术技巧

class TestObject
{
    public:

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

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

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

输出结果：
this is FuncA
崩溃

因为成员函数的调用实际上是为成员函数添加一个this的隐式参数，使得程序知道需要调用哪个对象的成员变量。
TestA中没有使用this的任何变量，所以不会遇到空指针的崩溃问题。
TestB是一个虚函数，需要访问对象的虚函数指针，而对象为nullptr，导致无法寻找对应的函数，直接崩溃。

真实无法想象，这样的程序为什么要写，不使用成员变量的函数为什么定义在成员函数中，匪夷所思。

Share：分享一篇有观点和思考的技术文章

windbg调试确实是一个比较有意思的东西，包含堆栈信息，根据指令进行堆栈分析，让我更加的认识到程序运行的奥秘。
不过自己的反编译能力实在是有限，之后要学学汇编指令、争取在这方面能有所进步。