待整理知识点

标签：知识点 map 队列元素二叉树 key 整理指针

排序函数

sort(begin,end,cmp)：

根据数量级不同，自动选择合适的排序方法（快排，堆排等）
cmp可省略，默认是从小到大排序，从大到小则将cmp换成 greater<类型>()
升序：sort(begin,end,less())
降序：sort(begin,end,greater())
begin 为指向数组第一个元素的指针，end 为指向数组尾后的指针（最后一个元素的下一个位置）
头文件要包含 #include<algorithm>
可以根据需求进行自定义排序cmp

快慢指针or双指针

双指针技术本质上是依赖速度或起始位置不同的两个指针对于链表的遍历来实现对问题的快速解决
链表多使用双指针，其余题目使用双指针提高效率，节约空间

双指针解题：
1.指针相邻：删除某个结点，或交换两个结点
2.指针不相邻，快满指针间隔n步，或者速度相差n倍

滑动窗口

问号表达式

<表达式1>?<表达式2>:<表达式3> fg： result=a>b? a:b;

vector声明二维数组

vector<vector<int>> table(size1, vector<int>(size2, 0)); // size1 是外围容器大小， size2是内部容器大小，0是赋的初值。
//                即 容器（  大小，    内容）

数组总结

数组元素不能删除，只能覆盖，整体移动元素
数组和双指针真是相配
vectort插入二维数组
v.insert({2,3,4});

链表基本知识

一种线性结构，依靠指针进行连接，分为单链表、双向链表（可向前向后查询）和循环链表（首尾相连）
单链表，每个节点由一个数据域和指针域构成，指针指向下一个节点，尾节点指向null（空指针），第一个节点称为head 头节点。
双向链表，每个节点由一个数据域和两个指针域构成，两个指针分别指向前一个节点和后一个节点。
链表在内存中不是连续存储的，是散乱分布在内存中（具体分配机制取决于系统内存管理）
★链表的定义★
面试会考，要会

struct ListNode{
    int val;
    ListNode *next;  //指针是存储地址的变量，声明的类型是告诉编译器该如何解析所存储的地址的
    ListNode(int x) ：val(x),next(NULL){}  /*节点的构造函数，c++系统有一个构默认造函数，
                                             但是初始化的时候不能给变量赋值了，所以自定义构造函数。*/
}

哈希表

哈希表理论基础

哈希表是hash table 又叫散列表，多用于快速判断某意思元素是否在集合里。（数组是一个哈希表。）
哈希函数hash function把实际的目标映射到哈希表上。
哈希碰撞（冲突）实际目标映射到了相同索引下标的位置。解决方法：
①拉链法：冲突的元素存储在链表中
②线性探测法：要保证tableSize 大于dataSize，冲突的元素存储在冲突位置往后的空位上。

常见的哈希结构

数组
set（集合）
map（映射）
set和map的底层实现及优劣表

集合set	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，
如果需要集合是有序的，那么就用set，
如果要求不仅有序还要有重复数据的话，那么就用multiset。

映射map	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

红黑树
红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

set集合
C++ STL unordered_set容器

成员方法	功能
find(key)	查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（一个与end() 方法相同的迭代器）。
count(key)	在容器中查找值为 key 的元素的个数。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有元素的个数。

范围for循环

范围循环：
for (类型 element : myVector) {
    std::cout << element << " ";
}

map相关
C++之STL整理（3）之map 用法（创建、赋值、方法）整理
STL 中的map是一个关联容器，它存储的元素都是键值对（key-value pair），并且根据键（key）自动排序的容器。map不允许键重复，每个键在map中只能出现一次。
map容器的每一个元素都是一个pair结构（pair<t1,t2>）的数据。
map容器的迭代器first和second，分别对应key 和value。通过map->first;获得对应的值
pair结构
pair 通常用于将两个值组合成一个单一的实体，以便可以作为一个整体进行传递或返回。
这两个元素分别被称为 first 和 second。
包含头文件：#include

迭代器

迭代器是一种检查容器内元素并遍历元素的数据类型，通常用于对C++中各种容器内元素的访问，但不同的容器有不同的迭代器，

C++ 迭代器(iterator)超详解
迭代器的通用功能

比较两个迭代器是否相等（==、!=）。
前置和后置递增运算（++）。
读取元素的解引用运算符（*）。只能读元素，也就是解引用只能出现在赋值运算符的右边。
箭头运算符（->），解引用迭代器，并提取对象的成员。

map的操作

插入、查找、删除，遍历
插入
map<int,int> map

pair
map.insert(pair<int,int>(1,2));
make_pair
map.insert(make_pair<int,int>(1,3));
value_type
map.insert(map<int,int>::value_type(2,3));
[]
map[3]=4 ; //插入key为3，value为4

在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。

string

访问string对象中的每一个元素
一个string对象表示一个字符序列，可以使用范围for循环，
访问string对象中的单个字符

使用下标
使用迭代器
字符串扩充
str.resize(k,c); //c可省
s.resize(s.size() + count * 5);
k:指定的字符数，若原字符串长度>k，则，原字符串删减到只有k个
若原字符串长度<k，则，原字符串扩大到k个
c:如果 k 大于字符串的长度，则 c 是要添加到新空格中的新字符。这是可选参数。
字符串长度
c++中使用s.length()和s.size() 获取长度，二者区别不大，返回的都是无符号类型。
字符串类型转换
1.[数字] 转换 “字符串”
【函数名】
to_string(数字类型)； //数字类型 int long float 等
2.“字符串” 转换 [数字]
【函数名】
stoi() 对应 int
stol() 对应 long
stoll() 对应 long long

字符串总结

字符串是若干字符组成的有限序列，也叫字符数组。
C语言和c++中字符串的区别
C语言中，把字符存入数组，以结束符'\0'为结束标志，'\0'可作为判断依据
c++中，提供string类，string类提供各种接口，其中size（）可作为结束判断标志。
vector< char > 和 string 相差不大，string类提供处理字符串的接口更多
c++中String类的常用函数

长度
size()和length()：返回string对象的字符个数，他们执行效果相同。
插入
push_back()：尾部插入
insert(pos,char):在制定的位置pos前插入字符char
比较
C ++字符串支持常见的比较操作符（>,>=,<,<=,==,!=）
删除
iterator erase(iterator p);//删除字符串中p所指的字符

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。
双指针法是字符串处理的常客。
KMP算法是字符串查找最重要的算法，

哈希总结

一般来说哈希表都是用来快速判断一个元素是否出现集合里

三种常见哈希结构
根据情况分析适用哪种

双指针去重

库函数

刷题时库函数的使用
题目的关键部分尽量不使用库函数
但使用时，要考虑明白库函数的时间复杂度

库函数reverse
主要用来反转数组和字符串的函数

反转数组就是reverse（数组名，数组名+你想让他反转的数组长度）
反转字符串是reverse（s.begin(),s.end()）;

左闭右开
一般编程的库函数都是左闭右开
max和min
函数定义在头文件中
std::max: 返回两个或更多参数中的最大值。
std::min: 返回两个或更多参数中的最小值

栈和队列

1.栈和队列是STL（C++标准库）里面的两个数据结构。常使用SGI STL版（开源，可读性高，被GCC所采用）。
2.二者以底层容器来实现所有工作，对外提供统一接口，所以二者不是容器，属于container adapter 容器适配器。
3.因二者的进出特性，不提供迭代器进行访问。
栈stack
stack<类型> 变量名；

一头通，先进后出
底层实现可使用容器deque，vector，list，没有指定底层实现，默认deque为缺省情况下栈的底层结构
deque是一个双向队列，封住一段，只开通另一端就可以实现栈的逻辑了。
对外提供接口
push(x) -- 元素 x 入栈、
empty() -- 返回栈是否为空
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
size() -- 返回栈内元素的大小；

可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

队列queue

两头通，先进先出
SGI STL中队列一样是以deque为缺省情况下的底部结构
对外提供接口
push(x) -- 在末尾加入一个元素
empty() -- 如果队列空则返回真
front() -- 返回第一个元素
pop() -- 删除第一个元素
back() -- 返回最后一个元素
size() -- 返回队列中元素的个数

可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

涉及左右，相邻匹配的问题，使用栈

队列类型

单调队列保持单调递减或递增的原则的队列
双向队列deque

可以在队列的两端进行元素的插入和删除操作，deque是C++STL（标准模板库）中的一种容器，
包含#include
常用函数

push_back()//在队列的尾部插入元素。
emplace_front()//与push_front()的作用一样 
push_front()//在队列的头部插入元素。
emplace_back()//与push_back()的作用一样 
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素。
back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器
rbegin()//返回逆头位置的迭代器 
rend()//返回逆尾-1位置的迭代器 
insert()//在指定位置插入元素 
erase()//在指定位置删除元素

优先级队列
一般队列是先进先出，从队尾入队，从队首出队。
优先级队列（priority_queue）：给元素赋予优先级，优先级高的先出队。像数据结构堆。
优先级队列的底层是最大堆或最小堆。大顶堆（堆头是最大元素，较小的元素下沉，less<），小顶堆（堆头是最小元素，较大的元素下沉greater>）

优先级队列的定义如下：

首先要包含头文件#include<queue>
priority_queue<typename, container, functional>

·typename是数据的类型；
·container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；
·functional是比较的方式，默认大顶堆（元素越大，优先级越高），（c++可以直接使用自带的less和greater函数，默认的大顶堆是less函数，元素小于当前节点下沉）
使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

//重写仿函数，完成less的功能，也可以用class定义类，此时需要将运算符重载函数设为public
//结构体struct中默认是访问类型是public
struct cmp    
{
	bool operator() ( Data &a, Data &b) {
		return a.getId() < b.getId();
	}
};

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。
和队列基本操作相同:

top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 ( **并排序** )
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容

栈与队列总结

栈与队列的特性和基本操作
底层实现
单调队列
优先级队列
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

二叉树基础知识

二叉树种类

满二叉树
满二叉树：如果一棵二叉树只有度为0和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树（子节点要么为0，要么为2）
若满二叉树的深度为k（即k层，从1开始），则其节点个数为：2^k-1
完全二叉树
完全二叉树：从上到下，从左到右，都是连续的。满二叉树一定是完全二叉树。
优先级队列是一个堆，堆就是完全二叉树
二叉搜索树
节点是有顺序的，
若左子树不为空，左子树上节点的值小于根节点，
若右子树不为空，右子树上节点的值大于根节点
平衡二叉（搜索）树
它是一颗空树或左右子数的高度差绝对值不超过1.并且左右子数都是一颗平衡二叉（搜索）树。
map、set、multimap、multiset 的底层实现都是平衡二叉树，所以是有序的。

二叉树的存储方式

链式存储
使用指针来连接左子树和右子树，一般用链式
线性存储（内存连续分布）
使用数组来村存储
计算孩子节点：若父节点数组下标为n，则左孩子节点为2n+1，右孩子节点为2n+2；

二叉树的遍历

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
1.前序遍历（递归法，迭代法（就是非递归方法））中左右
2.中序遍历（递归法，迭代法）左中右
3.后序遍历（递归法，迭代法）左右中
深度优先遍历，一般使用递归的方式来实现，使用栈结构，栈就是递归的一种实现结构，
广度优先遍历：一层一层的去遍历。
层次遍历（迭代法）
广度优先遍历，一般使用队列来实现

二叉树的递归遍历

递归算法三要素

确定递归函数的参数和返回值
确定递归函数的终止条件
确定单层递归条件

//Definition for a binary tree node.
 struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

标签：知识点,map,队列,元素,二叉树,key,整理,指针
From： https://www.cnblogs.com/bamboo2233/p/18279650