前缀树

通常为了使用方便，会构造一个结点，丰富结点信息。

class TrieNode{
public:
	int pass; // 该节点被通过的次数
	int end; // 以该节点为终点的节点的个数
	vector<TrieNode> nexts; //该节点下边的节点
	TrieNode() {
		pass = 0;
		end = 0;
		nexts = new vector<TrieNode>(26);
	}
}
1
2
3
4
5
6
7
8
9
10
11

通过pass和end两个值，可以很方便的查询前缀树以某个字段为前缀的字符串数。

构造前缀树的过程：

根据前缀树搜索一个Word加入了几次：
将word中每个字母遍历完，如果遍历过程中发现next为空，表面该Word没有插入过，否则可以完成遍历，遍历完成时的节点的end值就是所求。

同理根据前缀树搜索一个前缀pre的次数，如果不能完成遍历（遍历到空值）则表面没有插入过，否则返回遍历完成时的节点的pass值。

删除某个Word的过程：
首先执行搜索Word，确认Word有被插入后，遍历该Word，将所经过的节点pass–，遍历结束时的节点还需end–。特殊地，当pass–过程中发现pass已经减为0，则该节点后边的节点都需要删除掉，即在之后的遍历过程中直接手动删除每个节点，由于直接删节点会导致无法遍历这个节点后边的节点，因此需要记录下要删的节点，可以存放在栈中，遍历完成时。再遍历一次栈，一个个删除栈中的节点。

贪心算法

有限时间完成最多次的会议

有限时间内安排完成最多次的会议
思路，先根据会议结束的时间进行排序，然后按照会议结束的时间最早的先安排。
代码实现，先设置一个比较器，根据结束时间比较。

真正安排会议时：
先判断根据排好的顺序遍历会议，如果会议开始的时间在设置的时间timePoint前，则进行会议安排，result++，并将时间点timePoint设置为该会议的结束点。

最省钱的切割金条方法

比较经典的哈夫曼编码问题
将数组中的数据构成小根堆，每次取出小根堆头两个数的结合值sum，代码增加sum，将sum再插入小根堆，再取小根堆头两个数，直至小根堆中只有一个数。

赚钱最多的项目安排方案

每个项目（上边代表项目需要的投入资金，下边代表项目获取的净利润值）。启动资金是1，如何安排项目能够最快获取利润。
思路：
将项目按照投入资金存入小根堆，弹出投入资金≤当前资金的项目（解锁的项目），将解锁的项目按照利润存入大根堆，每次弹出利润最大的项目，将当前资金累加上弹出项目的利润值。

字典序比较方法

字典序就是字典中单词排列的顺序。
如果两个单词长度一致，将单词看做27进制数比较大小，如果两单词长度不一致，将短的单词尾用0补全为长单词一样的长度，然后比较大小。

一个数据流中随时可以取得中位数

• 准备一个大根堆和一个小根堆。
• 第一个数进大根堆。
• 后边的数，如果值≤大根堆头，入大根堆，如果小，入小根堆。
  比较两个堆的大小，如果两个堆的大小相差＞2，则将较大的堆中堆头弹出，插入长度较小的堆中去。
• 在这种规则下，大根堆的头是大根堆最大的数，小根堆的头是小根堆中最小的数，而根据规则，小根堆中的数都大于大根堆，且两个堆的大小不超过1，因此，大小根堆的堆头就是数据流中最中间的两个元素。
• 如果两个堆的大小之和为奇数，那么较大的那个堆的头结点就是中位数，如果两个堆的大小之和为偶数，那么两个堆的头结点的平均数就是中位数。
  

N皇后问题

record数组用于表示第i行的皇后放到了第几列，i就是数组下标，对应的值代表放到列号。
递归体process1，输入参数依次是

• 当前排列到第几行
• record记录数组
• 整体要排多少个
• 返回值是合理的排列方法总数。

假如能来到第n行，说明找到一种有效排列，返回1.
非第n行，则需判断当前行的皇后放到1-n中的那一列上是有效的。如果有效，则更新record，继续process1处理（第i+1行的皇后）。

关于判断是否有效 isValid（record, i, j）。
record记录，第i个放到第j列。
首先由于是按行遍历，行号必不相同，故只需判断是否共列和共斜线 。
共列：判断列号j是否与之前record中的元素值相同
共列：判断两皇后所为位置连线斜率是否为45°或者135°，即列号相减的绝对值是否等于行号相减的绝对值。

位运算优化的N皇后问题

只能处理不超过32位。
用一个二进制数来表示皇后放置的位置。
limit的含义是将一个数后n位赋值为1，其他为0，以此用于限制设置位运算的范围。

判断皇后位置是否合法可以通过位运算优化。
依旧是只考虑共列和共斜线的情况，共斜线分为左斜线与右斜线。三种情况求或就是所有可以排除的情况。
这三种情况可以直接通过某个皇后所在位置，左移、右移来确定。

递归体process2（）函数
输入参数：

• 位限制limit
• 列限制colLim
• 左对角限制leftDiaLim
• 右对角限制rightDiaLim

当列限制与位限制相同时，表示有效位上都填上了皇后，找到一种合理的方法。

将所有限制情况取或，得到所有限制的位置，取反后，1的位置代表可以放的位置，再与位限制limit求与运算得到pos，pos中1的位置代表的就是可以插入的位置。

当pos不为0，代表还有可以放置的位置，从最右侧的1开始放置，放置后，更新pos，pos = pos - mostRightOne。更新三种限制，继续递归。
列限制为原有限制与mostRightOne的或，左右对角线的限制为原有限制与mostRightOne或运算后在左右移位。
注意：左右对角限制对一行的限制是左右移位的地方，但对于再下一行需要接着左右移位。因此这里是左右对角限制DiaLim先与mostRightOne求或运算后，整体左右移位。如果定式思维，先mostRightOne左右移位再与DiaLim求或这就是刻舟求剑了。因为对于第一行所需的皇后，对角限制使得第二行相应列左右移位1次被限制，而对第三行的限制是第一行列对应位置左右移位2次被限制，即移位操作是累积进行的，必须得是先或再移位，才能体现出改行移位1次，而上一行会多移位一次。