ARTS打卡第七周
Algorithm：每周至少做一個 leetcode 的算法題
705. 設(shè)計哈希集合
不使用任何內(nèi)建的哈希表庫設(shè)計一個哈希集合（HashSet）漫拭。
實現(xiàn) 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有龄坪。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處复唤。
代碼:
解法一：
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取值為常數(shù)時間的特性健田，保持哈希的取值常數(shù)性。缺點是1000000個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; //本題題點
/** 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中的列表中妓局，缺點是：哈希沖突的值讀取速度會慢，優(yōu)點是：內(nèi)存占用少
Review：閱讀并點評至少一篇英文技術(shù)文章
[C++變得更加python化]](https://preshing.com/20141202/cpp-has-become-more-pythonic/)
目前很多的公司還在考C11的技術(shù)新點呈宇，這說明C11的進(jìn)步是比較大的好爬，同時也是比較穩(wěn)定的，公認(rèn)的可以一起使用的甥啄，不知道C20的特性何時能被廣泛使用
Tip：學(xué)習(xí)至少一個技術(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
崩潰
因為成員函數(shù)的調(diào)用實際上是為成員函數(shù)添加一個this的隱式參數(shù)存炮，使得程序知道需要調(diào)用哪個對象的成員變量。
TestA中沒有使用this的任何變量蜈漓，所以不會遇到空指針的崩潰問題穆桂。
TestB是一個虛函數(shù)，需要訪問對象的虛函數(shù)指針融虽，而對象為nullptr享完，導(dǎo)致無法尋找對應(yīng)的函數(shù)，直接崩潰衣形。
真實無法想象驼侠，這樣的程序為什么要寫姿鸿，不使用成員變量的函數(shù)為什么定義在成員函數(shù)中，匪夷所思倒源。
Share：分享一篇有觀點和思考的技術(shù)文章
windbg調(diào)試確實是一個比較有意思的東西苛预，包含堆棧信息，根據(jù)指令進(jìn)行堆棧分析笋熬，讓我更加的認(rèn)識到程序運行的奧秘热某。
不過自己的反編譯能力實在是有限，之后要學(xué)學(xué)匯編指令胳螟、爭取在這方面能有所進(jìn)步昔馋。
