代码随想录

哈希表

定义：一种利用特殊值直接访问数据的数据结构。

★ 使用场景：判断某个值是否出现在集合中/ 出现过。

拿空间换时间。时间复杂度：普通暴力寻找：O(n)，哈希法：O(1)

哈希函数？

哈希碰撞？

hashcode？

字符串

std::reverse()的范围是左开右闭 [first, last)，想要翻转第8个字符到第12个字符的话，应写

1 2	`std:reverse(str.begin() + 7, // 第8个字符下标为7 str.begin() + 12); // 第12个字符下标为11，但右闭需要向后移一格`

KMP算法

vector

公共接口

命名空间：std
头文件：<vector>

bool empty();
void push_back(...);  // 向最后添加元素
T at(int i);          // 返回下标为i的元素
operator[](int i);    // 索引器，同at()
void insert(...); // 添加元素
??? find(...);   // 查找元素，一般用法：if (set.find(val) != set.end())  // 则找到
void clear();    // 清空
??? begin();     // 返回指向第一个元素的迭代器
??? end();       // 返回指向最后一个元素**再下一个元素的**迭代器
int size();      // 元素个数

unordered_set

公共接口

命名空间：std
头文件：<unordered_set>

bool empty();
void insert(...); // 添加元素
??? find(...);   // 查找元素，一般用法：if (set.find(val) != set.end())  // 则找到
void clear();    // 清空
??? begin();     // 略，见上
??? end();       // 略，见上
int size();      // 元素个数

栈与队列

STL实现

STL（Standard Template Library）有三个常见的版本：

第一个C++ STL实现：HP STL，开源
Visual C++编译器使用：P.J.Plauger STL，闭源，蓝本是HP STL
Linux的GCC编译器使用：SGI STL，开源易读，蓝本还是HP STL，由美国硅图公司（Silicon Graphics Computer System）实现。

cpp的stack容器

公共接口

命名空间：std
头文件：<stack>

bool empty();
void pop();   // 无返回值！
T top();      // 返回栈顶元素。如果此时栈为空，则程序崩溃
void push();
int size();

cpp的queue容器

公共接口

命名空间：std
头文件：<queue>

bool empty();
void pop();   // 无返回值！
T front();  // 返回队列中最旧的元素，即：最后一个元素
T back();   // 返回队列中最新的元素，即：第一个元素
void push();
int size();

lc1047. 重复项删除

题目本身没什么好讲的，拿一个栈遍历字符串秒了。这道题可以让人联想到消消乐。值得讲的是一些数据结构操作的细节：

如何将一个stack中的字符放入一个string中？第一版代码（我写的）如下：

string ret(s.length(), '\0');
int i = 0;
while (!st.empty())
{
	ret[i++] = st.top();
	st.pop();
}
ret.resize(i);					// 再resize
reverse(ret.begin(), ret.end());  // 最后翻转，因为是stack
return ret;

第二版（看了代码随想录）：

string ret = "";
while (!st.empty())
{
    ret += st.top();   // c++的string重载了+= ，方便很多
    st.pop();
}
reverse(ret.begin(), ret.end());  // 这里就不用resize了，仅仅翻转就好
return ret;

★★★ 第三版（string直接作为栈来用）★★★

其中：

back(): 返回最后一个字符。对应的是front()返回第一个字符。
push_back(...): 往字符串末尾田间一个字符。
pop_back(): 弹出字符串最后一个字符。

// 下面是完整的本题代码！
string ret;
for (char ch : s)
{
    if (!ret.empty()
       && ret.back() == ch)
        ret.pop_back();
    else
        ret.push_back(ch);
}
return ret;