思路 基础班双指针，还有归并的思想 题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。    示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2： 输入：l1 = [], l2 = [] 输出：[] 示例 3： 输入：l1 = [],…

思路 最终需要的结果是前序遍历，最简单的方式就是递归前序遍历，结果存到队列里，最后再组装。难一点的就是一边遍历一边组装结果，如果是递归，遍历左节点时，将父节点的右节点更改为左节点（题目要求的结果），那么会影响右节点的遍历（已经被替换成左节点了）。所以这里用迭代遍历，将遍历顺序存到了栈里，不用担心修改父节点影响遍历了。 题目 给你二叉树的根结点 ro…

思路 116题还能通过画图看出规律，但这是升级版，非完美二叉树。这题很容易想到用层次遍历，但是是中等难度，肯定不是最优解。 分析下，层次遍历时间复杂度O(N)，已经做到极致了。那么只能从空间复杂度下手，层次遍历空间复杂度为O(N)，如果不存副本，倒是可以优化。 遍历某一层时，就将下一层串起来，这样下一层就可以直接遍历，不用存到队列里。第一层没有上一…

思路 首先想到的是暴力求解，双重循环得出所有连续子串，但是多半要超时。没想到其他办法。看了题解，学到了前缀和的概念，这里的子串和等于end的前缀和减去start的前缀和。在前缀和的基础上，结合了hash来优化，也就是两数之和那道题。 两个地方需要注意。一、需要的前缀和可能出现多次，那么每次都得算上。二、前缀和为0也是一种情况，并且是必要的，需要手动…

冒泡排序 @Test public void test() { int[] arr = new int[]{3, 4, 1, 76, 3, 889, 8, 4}; for (int i = 0; i < arr.length - 1; i++) { for (int j = arr.length - 2; j >= i; j--) { …

思路 刚开始我以为这题的考点是如何快速读取文件（因为这是公司多线程学习分享后布置的作业），我就用多线程来解题。后来出题人跟我说：200m测试数据时我的程序OOM了，我才醒悟这题的考点不是快速读取文件，而是大文件排序。 这题挺有意思的，解题运用了多路归并，有个巧妙的地方估计只有实操才知道——复用流。 题目 查找第K小/大数据 每个法官都有不同的办案能…

一、思路 多个线程顺序执行，方法有很多，例如CountDownLatch，wait，volatile，join，semaphore，Automatic。。。 二、问题 我们提供了一个类： public class Foo {   public void first() { print("first"); }   public void second…

一、思路 第一时间想到的是动态规划，后来看题解发现，这玩意没那么复杂。 A和B比赛，没有平局，有两种结局。一、A赢B输，二、A输B赢。但是题中说亚历克斯先开始，言外之意就是主动权在他那里，只需提前计算出A赢还是B赢，然后照着赢的那个做即可。 言而总之，只要亚历克斯想赢，就一定能赢。而题中说了假设亚历克斯和李都发挥出最佳水平，亚历克斯一定会发挥好的，…

一、思路 我还想着二叉树遍历（非递归）忘了呢，转念一想，这儿又没有要求不能用递归，递归它不香吗？ 二、问题 翻转一棵二叉树。 示例： 输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1 备注: 这个问题是受到 Max Howell 的 原问题 启发的 ： 谷歌：我们90％的工程师使…

一、思路 经过画图发现，儿子之间连接没问题。但是不同父亲的孙子连接有问题，解决一个倒还好，巧妙的是经过递归，可以解决所有这类问题。 总是想着把问题分治，但分治完了却没想到可以还原回去。。。 二、问题 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node …