十道算法题
十道算法题 回到目录返回顶部返回顶部一次倒在LRU上的经历阅读目录
- 一、0X01翻转链表
- 二、0X02设计LRU
- 三、0X03环形链表
- 四、0X04两个栈实现队列
- 五、0X05二叉树层序(锯齿)遍历
- 六、0X06 二叉树中后序遍历(非递归)
- 七、0X07 跳台阶(斐波那契、爬楼梯)
- 八、0X08 TOPK问题
- 九、0X09 无重复的最长子串(数组)
- 十、0X10 排序
- undefined、结语
LRU的核心就是借助哈希+双链表，哈希用于查询，双链表实现删除只知道当前节点也能O(1)的复杂度删除，不过双链表需要考虑的头尾指针特殊情况。
具体实现的代码为：
这个问题利用快慢双指针比较高效，快指针fast每次走2步，slow每次走1步，慢指针走n步到尾时候快指针走了2n步，而环的大小一定小于等于n所以一定会相遇，如果相遇那么说明有环，如果不相遇fast先为null说明无环。
具体代码为：
力扣142是在力扣141拓展，如有有环，返回入环的那个节点，就想下图环形链表返回节点2。
这个问题是需要数学转换的，具体的分析可以看上面的详细分析，这里面提一下大题的步骤。
如果找到第一个交汇点，其中一个停止，另一个继续走，下一次交汇时候刚好走一圈，可以算出循环部分长度为y。
所以我们知道的东西有：交汇时候fast走2x步，slow走x步，环长为y。并且快指针和慢指针交汇时候，多走的步数刚好是换长y的整数倍（它两此刻在同一个位置，快指针刚好多绕整数倍圈数才能在同一个位置相聚），可以得到2x=x+ny(x=ny)。其中所以说慢指针走的x和快指针多走的x是圈长y的整数倍。
也就是说，从开头走到这个点共计x步，从这个点走x步也就是绕了几圈也回到这个点。如果说slow从起点出发，fast从这个点出发(每次走一步，相当于之前两步抵消slow走的路程)，那么走x步还会到达这个点，但是这两个指针这次都是每次走一步，所以一旦slow到达循环圈内，两个指针就开始汇合了。
实现代码为：
如果普通二叉树层序遍历，也不是什么困难的问题，但是它会有个分层返回结果的操作，就需要你详细考虑了。
很多人会用两个容器(队列)进行分层的操作，这里其实可以直接使用一个队列，我们首先记录枚举前队列大小len，然后根据这个大小len去枚举遍历就可以得到完整的该层数据了。
还有一个难点就是二叉树的锯齿层序(也叫之字形打印)，第一趟是从左往右，第二趟是从右往左，只需要记录一个奇偶层数进行对应的操作就可以了。
这里就拿力扣103二叉树的锯齿形层序遍历作为题板给大家分享一下代码：
对于二叉树的中序遍历，其实就是正常情况第二次访问该节点的时候才抛出输出(第一次数前序)，这样我们枚举每个节点第一次不能删除，需要先将它存到栈中，当左子节点处理完成的时候在抛出访问该节点。
核心也就两步，叶子节点左右都为null，也可满足下列条件：
- 枚举当前节点(不存储输出)并用栈存储，节点指向左节点，直到左孩子为null。
- 抛出栈顶访问。如果有右节点，访问其右节点重复步骤1，如有没右节点，继续重复步骤2抛出。
实现代码为：
而后序遍历按照递归的思路其实一般是第三次访问该节点是从右子节点回来才抛出输出，这个实现起来确实有难度。但是具体的实现，我们使用一个pre节点记录上一次被抛出访问的点，如果当前被抛出的右孩子是pre或者当前节点右为null，那么就将这个点抛出，否则说明它的右侧还未被访问需要将它"回炉重造"，后面再用！如果不理解可以看前面的详细介绍。
具体实现的代码为：
当然，后序遍历也有用前序(根右左)的前序遍历结果最后翻转一下的，但面试官更想考察的还是上面提到的方法。
返回顶部返回顶部一文拿捏TOPKTOPK的问题解决思路有很多，如果优化的冒泡或者简单选择排序，时间复杂度为O(nk),使用优化的堆排序为O(n+klogn)，不过掌握快排的变形就可以应付大体上的所有问题了(面试官要是让你手写堆排序那真是有点难为你了)。
快排每次确定一个数pivot位置，将数分成两部分：左面的都比这个数pivot小，右面的都比这个数pivot大，这样就可以根据这个k去判断刚好在pivot位置，还是左侧还是右侧？可以压缩空间迭代去调用递归最终求出结果。
很多人为了更快过测试样例将这个pivot不选第一个随机选择(为了和刁钻的测试样例作斗争)，不过这里我就选第一个作为pivot了，代码可以参考：
快排：
具体实现：
归并排序:
实现代码为：