题目描述
给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
平衡二叉树之平衡调整图解
先看一个平衡二叉树创建的例子。假设现在表中关键字序列为（13，24，37），具体的平衡二叉树创建过程如下图所示：
我们可以发现结点37的插入导致二叉树的根结点13的平衡因子变为-2，此时二叉树没有达到平衡状态。其中离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡树， 我们可将重新平衡的范围局限于这颗树或子树。
字典树的实现
字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。假设组成所有单词的字符仅是“a”~“z”，实现字典树结构，并包含以下四个主要功能。
- void insert(String word)：添加word，可重复添加；
- void delete(String word)：删除word，如果word添加过多次，仅删除一个；
- boolean search(String word)：查询word是否在字典树中；
- int prefixNumber(String pre)：返回以字符串pre为前缀的单词数量。
字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间，比如加入“abc”、“abcd”、“adb”、“b”、“bcd”、“efg”、“hik”之后，字典树如下图所示，其中橙色节点表示一个终止节点。
- 根节点没有字符路径。除根节点外，每一个节点都被一个字符路径找到；
- 从根节点出发到任何一个节点，如果将沿途经过的字符连接起来，一定为某个加入过的字符串的前缀；
- 每个节点向下的所有字符串路径上的字符都不同；
并查集的实现
一、结构
并查集由一群集合构成，最开始时所有元素各自单独构成一个集合。比如，有一批元素arr = [a, b, c, d, e]，我们需要将这一批元素初始化成单个元素的集合，即a单独构成一个集合，b单独构成一个集合。其中并查集中的单个集合结构如下所示：
当集合中只有一个元素时，这个元素的father为自己，也就是这个集合的代表节点。当一个集合有多个节点时，代表节点为集合中某节点的father指向其自己的节点，比如下图的节点a。
我们使用哈希表来保存所有并查集所有集合的所有元素的father信息，记为fatherMap。比如，哈希表fatherMap中的某一条记录会为(当前节点，father节点)。也就是key为当前节点，而value为当前节点的father节点。
另外，我们使用另外一个哈希表rankMap来保存一个集合中的元素个数，即集合的大小rank。且只有一个集合的代表节点的rank信息才有效。rankMap的某条记录为（代表节点，集合节点数）。上图中集合的rank为6，并记录在代表节点a对应的valuer中。
KMP 算法
我们先来看的题目，假如给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1，要求算法复杂度为O(N)。
举例如下：
str = “acbc”, match = “bc”, 返回 2。
str = “acbc”, match = “bcc”, 返回 -1。
矩阵的最小路径和
给定一个矩阵matrix，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中的最小路径和。
如果给定的矩阵matrix如下：
其中路径1，3，1，0，6，1，0是所有路径中路径和最小的，所以返回12。