9月16号leetcode每日一题
思考过程
虽然这道题属于那种有手就行的，但是将核心递归函数融合在返回主函数中还是比较巧妙的，要翻转这个树，就先翻转他的左右子树，之后在把两边指针进行交换。递归边界就是遇到root为空。虽然简单，但是题目还是比较典型的。
虽然这道题属于那种有手就行的，但是将核心递归函数融合在返回主函数中还是比较巧妙的，要翻转这个树，就先翻转他的左右子树，之后在把两边指针进行交换。递归边界就是遇到root为空。虽然简单，但是题目还是比较典型的。
说实话，这道题还是有一定的思考量的，刚开始想的是建立每行每列以及每个cell，之后就是把空的点push到一个队列里面，如果当前点可以进行填写（意思就是说其他8个数已经确定），就将节点pop出去，如果不能进行填写，pop出去之后就再push进入队尾。
这道题一开始肯定想的是使用dfs，外加bool型数组记录是否被选取，但是发现我自己原来写的并没有剪枝，但是时间效率还不错…看了题解，发现也是简单dfs加回溯。。。无语，那就这样写吧，这样的话感觉这道题就没有什么意义了，纯粹考察熟练度。
leetocde这几天感觉是要弄一个组合周…，总的来说还是换汤不换药，问题的关键在于去除重复的组合，重点是题目中说明不会出现重复的数字，这样就很简单了，递归函数包括两个参数，一个是剩余选取次数，一个是剩余选取大小，只有两者都为0时才能将结果push进最终答案，感觉实在没有什么好说的，确实太水了。。。
先说句题外话，这道题和昨天的那道组合数基本一样，只不过要自己额外做点处理，甚至在剪枝的要求上还不如昨天那道题。
拿到这道题的第一想法就是我先用大的数去减这个target，减不动了再用小一点的数字。这一点很好理解，相当于将所有可行解按照解的长度由小到大排列。但是这里没有保证数组有序，所以预先排序即可。但是第一次实现的时候，发现有重复组合，消除重复组合的方法昨天的博客里面已经提到，限定一种顺序即可，这里我们按照从大到小的顺序，因为可以重复选取元素，所记得选元素的时候可以是小于等于。
这道题刚拿到一看就比较典型，组合选k个数字，应该可以用dfs解决。
但是这道题要求的是组合，如果按照循环遍历选一个再用bool数组记录选取情况的话，会产生很多不必要的递归路径。
因此要确定每个组合只有一个排列会push到最终结果，方法就是规定一个顺序即可，这里就规定递增顺序即可。
但是做出来之后效率比较低下，应该是没有进行剪枝，仔细一想，每次要求遍历开始的部分直接从已有数字+1开始（数组为空时取1即可），修改之后最大时间缩短为十分之一。然而超过人数占比并不理想，所以在想了想，要是当前剩余可遍历元素少于所需元素个数，好像也可以直接返回，最后运行结果16ms,超过94%。
首先最直白的方法肯定是统计数字出现频率，然后排序选出频率最高的前K
个数字。但是既然会用到排序，那么复杂度就会来到 O(nlogn),不太符合题目的要求。
这时候很自然的就想到了快速的partition来进行划分，划分出来频率高的一边有k个即可。
另外一种想法就是(纯靠自己乱想的)，因为题目保证答案唯一，所以频率最高的前K个数字是确定的，使用map计数，然后每轮对元素数目每次减去1，这样某一轮过后，必定会在map中只剩K个元素，最后push到结果即可。