核心的思路是：既然要达到O(n)的复杂度，那么就要保持窗口内的最大值在窗口边界上。达到这个效果的方法就是滤掉窗口中没用的元素。维护一个双向队列，队列保存数组的下标，每当有新元素进入队列时，从队尾开始，删掉连续的比新元素小的元素，然后将其插入到队列末尾。之所以可以这样删掉元素是基于：这些元素永远都不会...

用Java暴力是可以过的，思路也很简单：补充完成之后的回文串中心必定在原字符串中，所以原字符串以第一个字符为起点必然存在至少一个回文串（长度可以为1），那么任务就变为找到原字符串中以第一个字符为起点最长的回文串，找到之后剩下的工作就是把剩余部分的翻转补充到原字符串头部即可。

典型的动态规划题。维护一个二维数组dungeon，dungeon[i][j]表示从第i行第j出发到终点所需要的最低血量（包含当前位置的消耗），最低血量不大于1。

要求连续元素的最大差值，那必然要排序，但是又要求在O(n)的复杂度内完成，自然就想到了桶排序。维护left和right两个数组，left[i]表示第i个桶的最左端元素，right[i]表示第i个桶的最右端点元素。除最后一个桶之外，每个桶都是前闭后开，最后一个桶是前闭后闭。当元素落到相应的桶内就更新相应桶的最左最右元素值，当所...

其实直接遍历也是可以也可以AC，但是更加优化的解法应该是采用二分查找的思想。如果中间值比起点大就收缩起点，如果中间值比终点大就收缩终点，直到收缩到起点和终点相邻，也就是找到了翻转的部分。这里需要注意的是，数组可能是没有翻转过的，所以mid的初值赋0。

题目本身不难，一次AC可能有点困难，因为要考虑的东西还是挺多的。两层循环，外层遍历所以点，内层遍历外层点之后的所有点，同时在内层循环用一个HashMap来保存每个斜率对应的，这样在内存循环中，斜率相同就代表是在同一条直线上了。这里要注意的有两点：

LRU Cache 数据结构用列表。get()和set()方法就不多讲，重要的是遇到下两种情况： 元素被访问过，要将其放到列表头部，实现函数：moveToHead(Node node) 元素个数达到最大值，删除尾部元素，实现函数：removeTail() 同时为了快速选中元素，就采用HashMap<Integer, Node>来保存键值。 {代码...}

树的前序和后序遍历是树相关算法的基本。就不多加解释了，直接上代码。 Binary Tree Preorder Traversal {代码...} Binary Tree Postorder Traversal {代码...}

递归，基本属于暴力求解。但是纯暴力应该是过不了的，参考网上的办法，增加了一个unmatch集合，类型是HashSet，用来存放那些已经被验证过无法匹配的字符串，这样可以剪掉很多分支。

节点中需要拷贝的两个引用是next和random。next引用比较好拷贝，相当直接复制普通列表。而对于random则需要目标节点已存在才比较容易些拷贝代码，采用的办法就是构造一个HashMap，其中key是原节点，value是拷贝节点，在拷贝random引用的过程中，直接用map.get(node.random)来获取相应的目标节点即可。

Candy 双向爬坡。从左到右爬一边，再从右到左爬一边。再累加所有值即可。 {代码...}

动态规划。维护一个boolean[][] isPalindrome二维数组，isPalindrome[i][j]表示s.substring(i, j)是否为回文串。递推公式：检查s.charAt(begin)和s.charAt(end)是否相等，如果相等就检查isPalindrome[begin + 1][end - 1]的值，也就是对一个isPalindrome[begin][end]的赋值复杂度是O(1)。另外维护一个numOfCuts数组，num...

那么这种『显然要遍历所有元素，但是却只给了O(n)的复杂度』，这样就想到了HashMap。把数组中的每个元素都放入一个HashMap中为key，value为boolean类型，表示该元素有没有访问过。然后，对于数组中的每个元素，要是没有被访问过，就对其进行计数——往前遍历及往后遍历，直到下一个元素不存在于表中为止。那么这样就保证了...

动态规划+深度优先搜索。把大问题（求整棵树的路径最大值）拆分成小问题（每颗子树的路径最大值），递推公式为：当前树的路径最大值=max(左子树的路径最大值, 右子树的路径最大值)+当前根节点的值。以此来推出最后全树的最大路径值。

树的广度优先搜索题。记录下每一层的节点总个数，然后根据广度优先搜索的原则进行遍历，将非null节点都加入到队列中，对于同一层中的节点，将其next指向队列中的下一个节点即可。

动态规划题。先用二维动态规划的思路解释下：设match是动态规划表，其中match[i][j]表示S.substring(0, i)对T.substring(0, j)有几种组成方式，递推公式为：

一旦有两个位置的节点被交换了，那么中序遍历就会出现有两个：Node[i] > Node[i + 1]其中i是错误位置，Node[j] < Node[j - 1]其中j是错误位置，遵循这个规律，找到相应的Node[i]和Node[j]对其进行交换（只交换val值）即可。

动态规划题。用一个二维（也可以简化成一维的）boolean数组match[i][j]来表示str3.substring(0, i + j)能不能由str1.substring(0, i)和str2.substring(0, j)组成，递推公式：

提前检验的内容就是检验两个字符串的内容是否相同，这个内容是否相同指的是：两个字符串所包含的字符种类和每种字符出现的个数是否相同，如果这个不同就可以直接返回，不需要执行接下来的代码。

这一题的核心算法其实和Largest Rectangle in Histogram一样，对每一行都求出每个元素对应的高度，这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积，那么这个问题就变成了Largest Rectangle in Histogram，用相同的方法求解就行了。总结来说就是对矩阵中的每一行，执行一遍Largest Rectangle in His...

这道题目有一个规则要掌握：当图形处在上升期时（height[i] < height[i + 1]），其实是不用计算面积的，因为在这种情况下再往前移动一格（i -> i + 1）所能得到的面积必然更大；当图形处在下降期时（height[i] > height[i + 1]），就要开始计算当前矩形的面积了，但是这个时候只知道右端点，如何知道左端点在哪...

扩充窗口：将窗口的右端点尽力向右扩展，直至到包含所有标准表中的字符（窗口中的每个有效字符的数量大于等于标准表中对应字符的数量），一旦窗口中的有效字符的总数达到字典字符串的长度，就停止扩充。

典型的动态规划题目。维护一个二维数组dis[][]，dis[i][j]表示：word1的前i个元素与word2的前j个元素的edit distance值。递推关系为：

首先，筛选出一行中应该包括的单词，这里要考虑空格还要占用掉的长度，也就是除了当前的总长度之外，还需要记录下纯单词的长度，这样方便之后生成相应的空格。

首先，对字符串左右去空格，然后根据字符e来进行划分，e之前的归为底数，e之后的归为指数。这个时候在使用Java的split()函数时要注意的时当分隔符是原字符串的首字母时，拆分之后的数组的第一个元素会是空字符串。所以，其实我们在去空格之后就可以对原字串做一些判断，直接筛选掉一些明显错误的情况。

我当时的想法非常朴素，就是用带插入的区间去原区间列表中一个个比较，问题就出在这个比较的结果会很多，可以看到我代码里面用了5个值来代表5中不同的比较结果（这里的前后是以数轴为坐标）：

这也是一题我有点不太能理解为什么可以标为hard的题目。解法其实很直观，就是先对interval进行排序，然后遍历一遍。这里需要注意的点有两个：

N-Queens N皇后问题，非常经典。同时也是非常传统的递归方法解决。 递归的主体很简单：对于当前位置，分别尝试下放皇后和不放皇后两种情况。这里有两个需要注意的地方： 在递归函数中，在一次递归中，对整行进行遍历，这样相当于在检查的时候就不需要对当前行进行检查了，因为赋值的时候已经保证了当前行只有一个皇后。 ...

比较典型的贪心。维护一个区间，区间表示第i步所能到达的索引范围。递推的方法为：每次都遍历一遍当前区间内的所有元素，从一个元素出发的最远可达距离是index+array[index]，那么下一个区间的左端点就是当前区间的右端点+1，下一个区间的右端点就是当前区间的max(index+array[index])，以此类推，直到区间包含了终点，...

一开始是非常想用递归的方法做的，因为前面已经有做正则表达式的经验了，所以认为这一题应该是同样的思路做。但是小数据集还好，大数据集根本过不去，分析了一下，主要是要回朔的地方太多了，或者是需要处理的分支实在太多。