2024.01.23_学习日记
天气：雪
学习地点：家
学习时长：5h
学习内容
暴力递归、贪心
- 贪心策略经常依据比较器实现堆或者排序。
- 返回最大钱数
一个小根堆用比较器进行排序，spend最小的在上面，一个大根堆用比较器排序，利润最大的再最上面。然后遍历小根堆，如果小根堆堆顶的花费小于我得钱，那么弹到大根堆里，如果大根堆空了，就返回money。然后更新money。 - 取得中位数
用两个堆，一个大根堆一个小根堆，先把第一个数字放入大根堆，接下来的数，如果小于大根堆的堆顶，如果是，放进大根堆，如果不是，放进小根堆，然后看size的差如果=2，大size堆顶进小根堆。最终就是大根堆放小于中位数的数字，小根堆放大于中位数的数。最后看size，大的那个堆顶就是中位数，如果size相等，就是俩中位数。 - N皇后（lc51）
版本1（打印出来）：思路就是用回溯算法，首先先生成全是.的n*n列表。主函数是当row走到n越界时，给res返回一种答案，这时候要用空格把每一行的列表变成字符串，然后return，找下一种方法。当到达i行的时候，要遍历每一列，看放到某个位置能不能行，如果能行，先把当前位置变成‘Q’那就继续往下dfs递归，当往下递归失败往上return以后，要把’Q’回复成.，最后bfs（0），然后返回res。判断是否有效就是看上方，左上方，右上方有没有Q，用到zip函数，可以把range的内容合在一起。
版本2（返回个数）：用一个record记录每一行放在第几列，然后当i来到n行，返回1，用res更新答案，来到第i行的时候对列遍历，如果有效，那么record记录上该位置j，然后res+dfs递归到下一行的结果，最后返回res，然后判断是否有效就是遍历之前的皇后，如果列数相等或者列数相减的绝对值等于行数相减，那就无效。 - 取出二进制中最右的1：pos&（~pos+1）。可以用于遍历。
- 二叉树最大距离值
这个题用到递归套路。第一种情况不要头节点，返回左右两边的最大值，第二种情况要头节点，返回头节点+左边（不为空情况）和头节点+右边（不为空）和头节点+左边+右边（都不为空）的最大值。 - 返回一个数组，java是返回node，python怎么搞明天搜一下。
- 数组的除以当前数字的乘积（facebook面试题）
要考虑0的个数，非零数乘起来，然后遍历的时候要看当前是不是0，以及0一共有多少个。1个和多个情况不一样。 - k进制异或（找到一堆数里的不一样的一个数）
把数组所有数先生成k进制数，累加到一个数组里，然后对k取余，最后转化成10进制。 - 返回后序遍历数组是否生成最小搜索树
最小搜索树就是头节点左边小，右边大，所以后续遍历最后一个值是头节点，然后左边的值必然有个分界线，分界线左边的是头节点左边的值，右边是头节点右边的值，所以用二分法找这个分界线即可。