数组
连续内存顺序存储，查找O(1), 数组指定大小
动态数组，不指定大小，分配一定空间，空间不够新申请double内存，复制原来数组内容，释放原内存
考点
数组中重复的数字
二维数组的查找
顺时针打印矩阵
连续子数组的最大和
排序数组中查找数字
Pony按照字典序输出１－ｎ的数
Pony数组所有的０移到前面，其他顺序不变
Pony旋转二维矩阵
Pony有序数列Ｎ个数，随机替换ｋ个，求算法排序让序列仍然有序
Pony快速查询大数组中任意区间的最大值
哈希表
数组下标为哈希表key映射，值为value 通过哈希函数映射key到数组下标，查找O(1).
哈希表key通过哈希函数映射数组下标，但当key足够多，哈希函数无法一一映射数组下标顺序，出现多个key对应一个下标，此时为哈希冲突
解决哈希冲突3方法，
1是对冲突的key-下标作为数组，通过冲突项目顺序查找key
2是对冲突key-下标后移一位，
3 是将所有冲突项目单独放在新哈希表中。需要新建一个哈希表
字符串
连续字符存储， 以'\0'结尾
考点
替换空格
字符串的排列
最长不含重复字符的子字符串
翻转字符串
Pony字符串用另外字符串分割
链表
不连续内存存储，用指针把节点连成链式结构
struct ListNode{
int value;
ListNode* next;
}
空间效率高，新入元素加一个内存。遍历查找O(n)
考点：
删除倒数k节点
链表排序
链表反转
链表中环的入口
两个链表的第一个公共节点
Pony单链表的乘法
考点
反转链表
链表排序
删除倒数第k个节点
两个链表的第一个公共节点
树
根节点用指针链接多个子节点，每个子节点继续链接多个节点，形成树形结构
二叉树
每个节点链接2个子节点的树
struct ListNode{
int value;
ListNode* left;
ListNode* right;
}
考点
前中后序遍历
重建二叉树
二叉树的下一个节点
树的子结构
二叉树的镜像
从上到下打印二叉树
二叉树中和为某一值的路径
二叉树的深度
Pony如何求树的直径
二叉搜索树
每个节点链接2个子节点其中左子节点小于节点，右子节点大于节点。平均搜索时间O(logn). 但是不是平衡的二叉树，根节点选取不好则导致最大搜索时间O(n)
考点
二叉搜索树的后序遍历序列
二叉搜索树与双向链表
Pony如何确定树为二叉搜索树
堆
最大堆： 每个节点链接2个子节点其中根节点大于子节点
最小堆： 每个节点链接2个子节点其中根节点小于子节点
红黑树
每个节点链接2个子节点，节点分红与黑，红不链接红，叶子节点为黑NULL 完全二叉树，搜索性能好且稳定
栈
先进后出的数据结构，最后push的元素第一个pop弹出
stack<template T> m_stack;
考点
两个栈实现队列
包含min函数的栈
栈的压入，弹出序列
队列
先进先出的数据结构，最先push的元素第一个pop弹出
考点
两个队列实现栈
队列的最大值
Pony n个点求面积最大四边形
Pony 黑白两类点能否找线分开
网友评论