串（string）

1 基本概念 串：是由零个或多个字符组成的优先序列，又名叫字符串。 本质是一种线性表的扩展，但更多的是关注子串的应用问题 子串在主串中的位置就是子串的第一个字符在主串中的序号。 字符编码 ASCII：7位 拓展 ASCII：8位 Unicode：16位 串的比较 挨个比较字符，以第一个不同 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

树与二叉树

一、树的基本概念 树：是 n ( n>=0 ) 个结点的有限集。 n = 0 时称为空树。 在任意一棵非空树中: 有且仅有一个根结点 当 n > 1 时，其余结点可分为一个或多个互不相交的有限集。 其中每一个集合本身又是一棵树，并且称为根的子树。 1、结点分类 结点的度：结点 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

顺序表查找

顺序查找：又叫线性查找，从表中第一个(或最后一个)记录开始，逐个比较。 适合小型数据，静态查找。 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

划分树

1. 两数之和 - Easy 2. 两数相加 - Medium 3. 无重复字符的最长子串 - Medium 4. 寻找两个有序数组的中位数 - Hard 1. 两数之和 - Easy 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 02 高级数据结构

查找的基本概念

查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素 （或记录）。 查找表：是由同一类型的数据元素（或记录）构成的集合。 关键字：是数据元素中某个数据项的值 主关键字：可以唯一地标识一个记录的关键字 次关键字：可以识别多个数据元素(或记录)的关键字 查找表按照操作方式来分有 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

跳跃表（Skip List)

一、二分查找和AVL树查找 二分查找要求元素可以随机访问，所以决定了需要把元素存储在连续内存。这样查找确实很快，但是插入和删除元素的时候，为了保证元素的有序性，就需要大量的移动元素了。 如果需要的是一个能够进行二分查找，又能快速添加和删除元素的数据结构，首先就是二叉查找树，二叉查找树在最坏情况下可能 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 02 高级数据结构

有序表查找

1 折半查找(二分查找) 折半查找：又称为二分查找。在有序顺序存储的线性表中，取中间记录作为比较对象，若相等,则成功；若给小于，则在左半区继续查找；若给大于，则在右半区继续查找。 $mid = \frac{low+high}{2}= low+\frac{1}{2}(high-low)$ 适合有序，静 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

堆

堆（Heap）是一种特别的树状数据结构：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。分为最小堆和最大堆。 二叉堆 左倾堆 斜堆 二项堆 斐波那契堆 索引堆 Treap 树堆 1、二叉堆 二叉堆是完全二元树或者是近似完全二元树，按照数 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

图

一、图的基本概念 图：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G 表示一个图，V 是图 G 中顶点的集合。E 是图 G 中边的集合。 1、各种图定义 无向边：若顶点 $V_i$ 到 $V_j$，之间的边没有方向，则称这条边为无向边(Edge)。 用无序偶对 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

红黑树

1、红黑树定义 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。可以在 O(logn) 时间内做查找，插入和删除。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。 满足如下条件： 每 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构