每天解一题。一千零一夜太长，先从一百零一夜做起。
November 2018
1101
求给定排列的字典序编号(有重复元素)。
1027 题目的基础上，做去重处理，借鉴排列组合问题中的除法运算。
1102
同 1101
1103
Space Replacement (’ ’ -> ‘%20’)
1104
NULL
1105
NULL
1106
NULL
1107
Permutation Sequence (给定正整数 n 和 k, 求 1 ~ n 的整数组成的第 k 个排列。)
处理过程有点类似进制转换。
1108
The same as 1101.
1109
最长回文子串。
1110～1118
NULL * 9
1119
Remove Duplicates from Sorted List II (None of the duplicates is remained).
October 2018
1001
查找子串在父串中第一次出现的位置。
写了一个非 KMP 的解法。
1002
二叉搜索树插入节点。
递归解法。
1003
同上题。非递归写法。
1004
验证一棵树是否二叉搜索树。
递归求解。
1005
同上题。非递归求解。（联想二叉树中序遍历）
1006
将有序数组转化为二叉搜索树。
折半取中，递归实现。
1007
有序链表转换二叉搜索树。
O(nlgn) 实现。
1008
同上题。O(n) 实现。
1009
二叉搜索树迭代器。
1010
二叉搜索树的最小绝对差。
1011
求二叉搜索树中处于 [k1, k2] 区间范围的节点。
中序遍历即可。递归写法可以加“剪枝”处理——跳过不可能有解的节点。
1012
从中序与后序遍历序列构造二叉树。（与 0918 题目对偶）
1014
求两个字符串的最长公共子串。
写了暴力枚举的解法。
1015
实现 LRU 缓存机制。
链表题，关键是如何锁定到用链表这种数据结构实现。比如自己本来想到过 PriorityQueue.
1016
给定两个字符串 A 和 B, 判断 B 的字符是否全被 A 包含（次数也要考虑）。
1017
判断给定字符串中的 alphanumeric character 是否构成回文（忽略大小写）。
1018
报数。给出数列前几项：1, 11, 21, 1211, 111221, … 每一项的生成规则就是，对前一项进行报数。求第 n 项的报数结果。
1019
同上题。递归求解。
1020
字母异位词分组。
brute-force solution…
1021
同上题。
排序 + hashmap 降低时间复杂度。
1022
Valid Anagram.
method1: hashmap; method2: sort.
1023
NULL （累且困，睡了）
1024
Next Permutation.
字典序算法。
1025
给定数组，求其元素的全排列。
两种递归写法。一种思路是，枚举每个位置可能的元素；另一种是枚举每个元素可能的位置。
1026
Previous Permutation.
Next Permutation 的对偶问题，解法一样。
1027
求给定排列的字典序编号（无重复元素）。
用一个具体例子，如 [4, 3, 2, 1], 从高位到低位（或相反方向）分析计算，容易找到规律，再转化为代码即可。
1028
NULL （too occupied by the messy room）
1029
最后一个单词的长度。
1030
翻转字符串里的单词。
1031
旋转字符串。
September 2018
0905
后续遍历二叉树，非递归实现
0906
leet 842 Split Array into Fibonacci Sequence, 未 AC
0907
承前
思路
指定前两个数字，记为 s0 和 s1，就可以顺着 Fibonacci 数列的定义往后递推，得到一个期望中的序列。比较期望序列与待拆分串，可知该串有解无解。至于输出具体的拆分结果，只需要在递推过程中加以记录即可。有了对于具体 (s0, s1) 的求解思路，接下来只需要枚举所有可能的 (s0, s1) 组合。
这道题 corner case 比较多，如：有前导 0 的串视为非法、拆分出的每个数必须在 int 能表示的范围内（即 32 位有符号整数类型）等。循环递推过程的实现，也比较考验代码表达能力。
0908
中续遍历二叉树，非递归实现
0909
删除链表中等于给定值 val 的所有节点
0910
层序遍历二叉树
0911
层序遍历二叉树II（自底向上）
0912
设计循环双端队列
0913
求二叉树的最大深度
思路
跟遍历类似，也是可递归、可迭代
0914
NULL （团建、临时情况、赶火车等等，missed）
0915
判断是否平衡二叉树。
思路
最开始想到的是……，比较笨拙。
0916
锯齿形层次遍历二叉树
0917
镜像反转二叉树。
非常简单，仅仅在层序遍历的基础上，处理每个节点之前先交换其左右孩子。
0918
从前序与中序遍历序列构造二叉树。
递归，关键在于递归调用的传参（几个下标）以及终止条件控制。
0919
判断一个树（T2）是否另一个树（T1）的子树。
思路
简单直接的想法，枚举 T1 的每个子树，比较其与 T2 是否相等。枚举 T1 的子树其实就是遍历所有节点，可以用 BFS 比较快。比较两树是否相等则可通过递归。
或者，isSubtree 判断子树的函数本身也可以递归——要么 T1 与 T2 相等则肯定是子树；要么进一步对 (T1.left, T2) 以及 (T1.right, T2) 判断是否子树。
0920
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
0921
题目同昨天。解法：dfs 求出树的所有路径（从根节点到达任一叶节点），从中 pick 出节点 A, B 分别归属的路径（可能是两条，也可能是同一条），沿着这条路径寻找 LCA.
写了一个巨复杂的 dfs(), 然后学着改为 normal 的 dfs.
0922
求二叉树中能连接两个叶子结点的最长路径（两个叶节点未指定）。
思路：与 LCA 很接近。
0933
求二叉树最大路径和（不一定包含根节点）。
0924
二叉树的序列化和反序列化。
序列化：递归实现前序遍历（后序、层序遍历也可以），稍有不同的是，通常的遍历不用处理叶子结点的孩子，这里需要在叶子结点的孩子处设置“哨兵”（sentinel）；
反序列化：读取序列化字符串，如果遇到“哨兵”则忽略，如果遇到正常的节点 value, 就创建对应的节点，并对其左右孩子作相同处理。递归实现较为方便。
0925
从后序与中序遍历序列构造二叉树。
0926
三道位操作的题目——
- 找出 2n+1 数组中的单数（共有 2n+1 个数，有且仅有一个落单，其余均出现两次）
- 找出 2n+2 数组中的单数（共有 2n+2 个数，有且仅有两个落单，其余均出现两次）
- 找出 3n+1 数组中的单数（共有 3n+1 个数，有且仅有一个落单，其余均出现三次）
3 的求解，涉及到二进制转十进制，宜用位操作计算。然答题的时候偷懒，用了 Math.power() 函数，竟 WA. 琢磨了会，发现 (int) Math.power(2, 31) 结果不正确——期望得数为 2147483648, 实际为 2147483647。应该与浮点数强转为 int 时丢失精度有关，改为 (long) Math.power(2, 31) 则结果正确。顺带复习了二进制补码。
0927
判断一个整数是否2的幂。
key: 整数 x 是2的幂 <==> x & (x - 1) == 0
0928
用栈实现队列。
第一次提交时 empty() 方法有错误，应该是当两个栈都为空，才返回 true.
0929
用队列实现栈。
跟上一题类似的是，一个队列用来进出元素、另一个用作中转站；不同的是，上一题中转的时候将所有元素都放入了中转站，而这一题作中转的时候则保留了最后一个元素，并且负责进出元素的队列和作为中转站的队列，是交替变换的。
more: http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html
0930
Determine the number of bits required to flip if you want to convert integer n to integer m. （相当于求两个数不同的比特位数。）