LeetCode[1] [13] [202]笔记

Oreo! 2022/1/21 算法STL

# 一、map和unordered_map

区别：

引用的有文件不同，map引入的头文件为#include<map>而unordered_map引入的头文件问#include<unordered_map>
内部实现原理不同：
- map：map内部实现了一个红黑树，其具有自动排序的功能，因此map内所有的元素都是有序的，其中每一个节点都表示map中的一个元素。因此可以理解为对map进行的增删改查等一系列操作都是对于红黑树的一种操作
- unordered_map：内部实现了一个哈希表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用，unordered_map内所有的元素都是无序的

优缺点：

map
- 优点：有序性，其元素的有序性在很多应用中都会简化很多的操作，内部实现的红黑树使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
- 缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
- 适用处：处理有序问题
unordered_map
- 优点：内部实现了哈希表，因此其查找速度非常的快
- 缺点：哈希表的建立比较耗费时间
- 适用处：对于查找问题unordered_map会更加高效，因此查找问题常会考虑使用unordered_map

# 二、快慢指针思想

在解决有诸如环形链表的问题是可以使用到的一种指针思想

在这个思想中，可以类比于两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的慢的称为 “乌龟”，跑得快的称为 “兔子”。找出循环，“快指针” 每次走两步，“慢指针” 每次走一步，当二者相等时，即为一个循环周期。一旦快指针与慢指针发生重合，说明该循环内出现“环”。

如下图所示

# 三、API小结

# 3.1创建map\unordered_map

可以直接使用大括号进行初始化：

unordered_map<char, int> dictionary = {
      {'I', 1},
      {'V', 5},
      {'X', 10},
      {'L', 50},
      {'C', 100},
      {'D', 500},
      {'M', 1000},
};

# 3.2string的length()和size()

在C++标准库中的string中两者的源代码如下

size_type __CLR_OR_THIS_CALL length() const{
  // return length of sequence
  return (_Mysize);   
}

size_type __CLR_OR_THIS_CALL size() const{
  // return length of sequence
  return (_Mysize);   
}

两者没有任何区别，length是因为沿用C语言的习惯而保留下来的，string类最初只有length，引入STL之后，为了兼容又加入了size，它是作为STL容器的属性存在的，便于符合STL的接口规则，以便用于STL的算法。

string类的size()/length()方法返回的是字节数，不管是否有汉字

# 3.3char单个字符转string

在cpp中可以使用string的构造方法

string(size_t n, char c)

其中size_t表示目标字符重复个数，c表示目标字符

# 3.4判断是否存在

注意STL中很多容器的find方法都适用于判断一个元素是否存在，当不存在时返回的是一个指向end的迭代器

所有以set为例：set.find(n)==set.end()表示该元素n不存在于set列表中

Oreo's Blog

Choose mode