顺利保研，国庆期间觉得还是需要练练每日一题保持手感。
10/4 密钥格式化
难度 EASY
由于是第一个小于等于规定数目，故倒着处理即可。
10/5 窥探迭代器
难度 MEDI
我的评价是不知道这题想干啥，参考了题解。。要善用题目提供的接口。
10/6 第三大的数
难度 EASY
用大小为3的数组记录就行。
10/7 字符串中的单词数
难度 EASY
难道是因为国庆，题目都简单了？注意可能有连续空格就行。
10/8 重复的DNA序列
难度 MEDI
既然确定长度是10，就用一个sliding window+哈希表处理即可。
10/9 将数据流变为多个不相交区间
难度 HARD
题目相对比较复杂，但难度不算太大。
本题的数据结构核心是一个map，key为某个区间起点，value为终点。每次执行void addNum(int val)时，使用upper_bound找到比val大的第一个区间对应迭代器 xj ，令 xi 为 xj 的前一个迭代器，如果 xj 为 begin ，则 xi置为 end。情况分析如下：
- 如果 xj 为 end，代表所有的区间起点都比 val 小，看 xi 对应的 start 和 end，starti 肯定更小.
- 此时看 endi 和 val 的关系，更小则形成新区间 (val,val) ，相邻则加入 xi 区间，包含则不动
- 如果 xj 为 begin，代表所有的区间起点都比 val 大，当且仅当此时 xi 为end
- 若startj - 1 = val，右区间左侧扩大，否则形成新区间val,val
- 其他情况下，考虑 xi 和 xj，此时有：starti <= (endi ? val 这两个不确定 ) < startj <= endj
- 如果endi + 1 = val = startj - 1，xi 和 xj 区间合并形成大区间
- 如果endi + 1 = val，左区间右侧扩大
- 如果startj - 1 = val，右区间左侧扩大
- 如果val <= endi，不变
- 如果都不是，形成新区间 (val,val)
10/10 排列硬币
难度 EASY
用了数学的方法，假设最后一行满，则有 $(1 + x) *x/2=n$ ，解得$x = \sqrt{2n+0.25}-0.5$，由于最终答案是整数，即使最后一行不满，即n减小（但至少有一个），结果在取整后也不会变。
10/11 整数转换英文表示
难度 HARD
这是个勾八的hard，题目毫无质量可言，写了一堆switch，每三个数一处理就行。
10/12 两数相除
难度 MEDI
不能用乘除，但是可以用移位，把被除数拆成除数的若干个2的次幂之和加上余数，这个2的次幂之和就是商。由于整数限制了范围，这个算法不算很慢
10/13 Fizz Buzz
难度 EASY
不是很懂，if-else就行。
10/14 山峰数组的顶部
难度 EASY
这个月好多简单题。山峰数组用二分查找就行，之前貌似做过（也可能是黄宇老师的课上）。
10/15 外观数列
难度 MEDI
模拟一下，数组迭代处理即可，没想到更好的办法，一看官方题解居然有打表，乐。
10/16 给表达式添加运算符
难度 HARD
好难好难好难。看了题解勉勉强强复现一下，这题用到了回溯法，这个方法老师没说过且用的不太多，每次遇到都得想半天。通过这题学到了c++的函数包装器function。由于具体做法完全参考题解，直接看题解就行。
私以为回溯法用来回溯的函数，类似记忆化的dfs，在搜索完某种情况后记得恢复状态，比如这题for循环结束后的str.resize(loc);。
10/17 二叉搜索树中第K小的元素
难度 MEDI
bfs是一种很特殊的树，可以先预处理树得到每个节点的所有后代（包括自己）的数量，然后再进行循环：
- 左子树所有节点数量为 left，右子树为 right，那么
- 如果 left＜k - 1，更小的节点在右子树中，k 减少left + 1，移动到右子
- 如果left == k - 1，那么本节点就是第k小的节点
- 否则，更小的节点在左子树中，移动到左子
10/18 数字的补数
难度 EASY
数学题，通过不断右移1，2，4，8，16并与自己“或”，得到数tmp，其最高的1与原数num位置相同，该位往后全为1。将num符号位置1后取反，得到有前导1的补数（但符号位为0而不是负数），再和tmp做与操作将前导1置0即可。
10/19 添加与搜索单词 - 数据结构设计
难度 MEDI
用字典树存储所有单词。普通单词的查询较为容易，含’.’的单词，遇到’.’时需要从当前位置的所有可能分叉（当前节点的26个子节点中所有有效的，即该位置可以为任意字母）递归查询’. ‘之后的单词，但凡有一种查到就返回true。
10/20 最小操作次数使数组元素相等
难度 EASY
这题并没有求最终数组的结果而只需要考虑次数。
在最优的操作情况下，每次是让最大的数不动，其他数均+1，其实等价于最大的数 - 1，这个trick挺巧妙的。
10/21 加一
难度 EASY
铸币简单题，找到最右侧的非9数字就行，只有找不到的情况下需要建新数组（例如99999这样的数+1）。
10/22 求众数 II
难度 MEDI
我只知道求超过n/2的众数可以选举法，这题没想到空间复杂度O(1)的算法（不限制复杂度直接哈希表就行），看了题解原来这种也可以用选举法，看来只要是限制了超过多少多少的众数都可以，最终结果可能有多个而已。
10/23 构造矩形
难度 EASY
又是简单题，开方后一个一个找就行。
10/24 大礼包
难度 MEDI
记忆化的dfs，过程比较繁琐但不算难
10/25 搜索二维矩阵 II
难度 MEDI
一开始没考虑清楚，想的是先横向二分查找确定一列，纵向二分查找确定一行，误以为只会出现在这些位置，而这明显不对。正确的想法是，设当前坐标元素(x, y)值为z，那么
- 如果z == target，找到目标
- 如果z < target，那么意味着这一行在 z 左侧的都没有可能
- 如果z > target，那么意味着这一列在 z 下侧的都没有可能
那么，如果我们从右上角出发，即右侧、上侧无有效元素，每次在2、3两种情况下就可以筛除整行或整列，并且依然保持z在右上角。因此从右上角向左下角搜索，搜到超出边界则失败。
10/26 下一个更大元素 I
难度 EASY
这道题最好的思想是单调栈：
一但要求下一个更大的元素，就是用单调栈解
我当时没想到，用的想法类似单调栈，即用一个哈希表记录某个元素的下一个最大元素是多少，初始化最右侧为-1，从右向左遍历：
for(int i = n - 2; i >= 0; i--){
int cmp = nums2[i + 1];
while(cmp < nums2[i] && cmp != -1){
cmp = bigger[cmp];
}
bigger[nums2[i]] = cmp;
}
cmp 初值为 i+1 元素的值，如果 cmp 比 i 元素小，找cmp元素记录的下一个最大元素，不断循环直到找到比 i 大的或是递归到 -1（即没有更大的），把这个值赋给 i 位置。用均摊分析法分析，虽然是双重循环，但时间复杂度依然在 O(n) 。
其实这个思路和单调栈基本一致，不过平均来说单调栈用的空间更小。
10/27 删除无效的括号
难度 HARD
本题题解中提供了其他较好的方法（比如回溯），有时间值得一看。
我用的方法基于BFS，基本类似官方题解的第二个解法。既然要删除最少的括号使之有效，那么每次从当前队列中拿出一个元素，删除任意一个括号加入队列，将其弹出，那么在一次循环开始时（或结束时）检查发现有效字符串，队列里的都是删除等量括号的，即包含所有可能的结果，找出所有有效的即可。
在这个基础上需要进行优化。首先，删除的顺序不同可能导致产生相同的中间结果，所以要用哈希表代替队列来避免。其次，删除任意一个括号的做法会在一些情况下带来大量冗余。由于我们可以在一开始通过简单的遍历得出需要删除多少个左、右括号才能使之有效，我们可以把这两个数字记录下来，作为unordered_map的 key，删除左括号时先检查是否能删除，右括号同理。避免了对于类似 “((((((((((())))”这样明显只需要删除左括号的进行了删除右括号，算是空间换时间。
10/28 重新排序得到 2 的幂
难度 MEDI
用大小为10的字符串记录数字中0到9的出现次数，把所有范围内的2的幂对应的字符串存入哈希表，再查询即可。题解中介绍了一种回溯算法，在这题中用不上，但是思路挺通用的。
10/
难度 EASY
10/
难度 MEDI
10/
难度 HARD