demo

不要把优先队列当成排序数组来用，例如数组1，2，3，依次加入大顶堆，得到的是3，1，2。
优先队列里的比较器返回值不要写死，比如1，2，3依次加入大顶堆，老老实实写(a,b)->b-a而不是(a,b)->-1或者(a,b)->1；
Arrays.sort(nums,(a,b)->b-a)不支持基本数据类型，所以想要获取倒序int[]不能这样写，只能老老实实for循环交换前后指针位置。
list只能转成object数组，即使list是有泛型，所以刷题list转数组老老实实new int[]然后依次填充。
map判断key是否存在的方法是containsKey而不是contain。
Arrays.fill(nums,key)方法只能填充一维数组。
string不能取代其中的一个字符，stringBuilder.setCharAt(index,c)可以。

刷题笔记

leetcode2943.设计数字容器系统：核心难点在于寻找一个数据结构，能获取最小的元素，新增元素和删除元素。对于获取最值的数据结构，可以选择priorityQueue和treeSet。

priorityQueue是由二叉堆实现的，无序，获取最值的时间复杂度是O(1), 插入元素O(logN), 删除任一元素O(N);
TreeSet的底层实现是红黑树，有序，获取最值的时间复杂度是O(1)，插入和删除任一元素的时间复杂度都是O(logN);
priorityQueue可以插入重复元素，treeset只保留一个重复元素

所以综上选择treeSet。针对这题如果选择了priorityQueue，就不能随意的删除元素（因为时间复杂度是O（N），超出时间限制），可以采用惰性删除的方法，在取堆顶元素，根据题意判断堆顶元素不符合要求时再删除。

leetcode863二叉树中所有距离为k的节点
leetcode2385感染二叉树需要的时间（亚马逊周赛）
两题都是求解其他节点距离某个固定节点的距离。对于这种求距离的问题，可以采用dfs的层次遍历，每一层即距离+1。因为初始节点不一定是根节点，所以节点可以向根节点，子节点遍历。子节点在二叉树中已知，所以我们还需要直到某个节点的根节点，可以用dfs将节点和根节点的映射关系存储在map中。综上：一次dfs+一次bfs即可解决问题。

3.剑指offer36：二叉搜索树与双向链表：
方法1 ：将中序的遍历顺序加入list中，遍历完后将list转换成双向链表。
方法2：设置全局节点记录当前节点的上一个节点，边中序遍历边转换成链表。
4. 剑指offer60：n个骰子的总数 :经典动态规划，难。
5. 预算内的最多机器人数目： leetcode2398 ：
解法1：单调队列：单调队列适合滑动窗口类的题目（使用滑动窗口一定要满足窗口的单调性），求窗口中的最值的元素，这时候我们可以维护一个双向队列deque，在窗口扩大时保证窗口的单调性（从尾部加，往前遍历，不满足则移除之前的队列元素），在窗口收缩时判断队顶是不是被收缩的元素，是则移除队顶元素。窗口的大小不一定是固定的，只要能找到什么时候该左移即可。
解法2：二分，求最大的k满足m，如果对于(k-1)一定也满足，即k和m之间存在单调关系，则可以使用二分。然后关键就到了怎么根据k求m上，写出这个函数即可。
6. 剑指offerII ：乘积小于k的子数组，可以使用滑动窗口，重点是怎么知道一个窗口的子数组的数量是多少？求子数组的数量可以有两种求法，一种是固定数组的长度，找出子数组数量，一种是固定子数组的结尾位置；这里我们选择第二种，例如i开头，j结尾的窗口中以j结尾的子数组的数量是j-i+1；
7. 剑指offerII：和为k的子数组：由于数组不全是非负数，无法保证单调性，所以没法使用滑动窗口。求子数组的和的话可以使用前缀和，即求a-b = k，我们可以用map把前缀和数组保存起来，当遍历到a时，求a-k在map里的个数即可。
注意：一定要先取 a-k在map里的个数加入结果，再将a加入到map，否则当k=0时会出错。
8.leetcode327：区间和的个数：处于m-n区间内的子数组个数：子数组的区间和使用前缀数组，即满足 m<= a-b <= n; 这题可以借助归并排序，因为归并排序可以给我们提供两个有序的数组，此时问题就变成了，在两个有序数组里分别找a和b：这时就可以固定一个数组的a，在另一个数组里找满足条件的b。扩展：如何高效的在两个升序数组里找差值在某个范围的数？一种普遍的做法是对于第一个数组里的每个数，都在第二个数组里从头到尾遍历求。但因为两个数组都是有序的，所以对于a0对应的 b0start-b0end，a1对应的b1start-b1end，必有b1start>b0start && b1end>b0end。所以可以记录每次的start和end，在之后往数组后面找新的start和end就可以。两种做法前者数组二遍历了m次，时间复杂度为O(mn), 而后者做法数组二只遍历了一次，时间复杂度为O(m)+O(n).

leetcode97: 恢复二叉搜索树: 问题的本质是一个有序数组，交换其中任意两个值，怎么找出被交换的两个数。例如 1->2->3->4->5

第一种情况：交换的不是相邻的两个数，例如1->4->3->2->5，遍历的时候发现异常的数对是4->3, 3->2。第一个数对的第一个数和第二个数对的第二个数即是要交换的值。
第二种情况：交换的是相邻的两个数，例如1-2-4-3-5，则遍历的时候第一个异常的数对就是要被交换的值。

实现：

我们可以利用二叉搜索树中序遍历有序的的特点，由分析知我们需要知道当前节点的上一个遍历的节点，因为可以维护一个全局遍历pre并实时更新。注：获取遍历的上一个节点没法通过入参体现，只能维护全局变量。获取父节点可以通过入参体现。

10：镜像二叉树：获得一颗镜像二叉树的办法就是先获取左右节点的镜像，再交换左右节点，所以使用简单的后序遍历即可。
11：判断对称二叉树：判断对称二叉树等同于判断左右子树是否对称，判断左右子树是否对称即判断左子树的左子树与右子树的右子树&&左子树的右子树&&右子树的左子树是否对称，同样是dfs，不过入参是两个节点。
12：leetcode2415：反转二叉树的奇数层，这题和前两题有点类似，但无法在第一题的基础上修改（无法只交换奇数层的子树从而得到正确的答案），在第二题的基础上修改的原则是这是一颗满二叉树，否则出现其中一个入参为空的情况很难处理（node1==null,把node2赋值给node1是没有意义的，因为没有对node1的父节点产生联系）。如果不是满二叉树，就得使用bfs了。

13:leetcode89 格雷编码：本题主要学到的是计算2的n次方，有一般的累乘法，还有进阶的快速幂算法，最重要的是在普通题里直接用1<<n就好了。位运算例如&，|，^ 的优先级都比其他运算符低，记得加括号，例如计算中位数的正确写法是int mid = left+(right-left>>1), 错误写法是left+(right-left)>>1。
14：leetcode91 解码方法：本题是超进阶版的青蛙跳台阶，可以使用动态规划，注意如果前两个台阶都不让跳应该直接返回错误。
15：leetcode97：交错字符串： 本题是很经典的回溯+备忘录优化 = 动态规划，但是竟然在备忘录优化的时候没优化对，注意是备忘录，因为两个参数就有必要使用备忘录了，不能确定参数1和参数2的到达顺序，但在都到达的那一刻之后的操作是一样的，所以我们只要记录是否到达过而不用关注此刻对不对！
16: 三目运算符的优先级比加减都要低，%的运算优先级和加减一致，实际中注意加括号！！！leetcode875
17: 做滑动窗口题目，比较两个map里的Map<Character,Integer>中的value的时候用equals而不要用==，因为value大于127就会永远!==, leetcode438.