在给出了明确的时间复杂度和空间复杂度后，我第一个想到的就是利用divide and conquer 方法进行排序。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。了解利用分治法对数组进行排序的童鞋应该知道，我们会根据数组的下标将数组取一半分别进行排序后，再将排序好的二者进行合并。那么将链表分为大小相...

通过队列实现一个栈的功能。栈的api为push（压入栈顶），pop（出栈），peek（栈顶元素），empty（栈是否为空）。这道题和之前的使用栈实现队列功能是类似的，可以参考我的这篇博客。

假设存在这样一个链表，在链表的每一个节点中，除了记录了自身值和指向下一个节点的指针，还有一个随机指针指向链表中任意一个节点。现在要求深度复制这份链表，在不改变原链表内容的情况下，创建一组新的对象，该组对象中的值和原链表中的值相同。

这篇题目与leetcode200. Number of Islands思路非常相近，建议毫无思路的同学先参考一下这篇博客。其实这种将区域相连的题目往往都可以使用深度优先遍历或者是Union-Find方法来实现。在这里我就给出深度优先遍历的实现方法，有兴趣的同学可以参考上文的博客来自己实现Union-Find方法。

题目要求 {代码...} 也就是说，比较版本号。 思路一：利用java API 通过split方法将版本通过.分隔开，然后将每一段版本从string转化为int进行比较 {代码...} 思路二：自己实现string转化为integer 自己实现将string转化为integer，可以通过循环的方式。这是一个基本的算法。 {代码...} 想要了解更多开发技术，面试教程以...

这道题目从经典的数据结构的角度来说可以使用并查集来进行判断，将每一个海洋看做一个集合合并起来，将相邻的陆地通过并查集连接起来。最后查看并查集中剩余下的集合数。这里使用一个新的二维数组来表示对应地图上的元素属于哪个并查集。在合并的时候先进行判断，如果二者为已经相连的陆地，则无需合并，否则将新的二维...

题目要求 {代码...} 计算一个完全二叉树的节点个数。其中完全二叉树是指除了最后一行，其余的每一行都必须是满节点的树。 思路一 ：不讲道理的递归 直接返回左子树和右子树的叶结点的个数。当然超时啦 {代码...} 思路二：讲道理的递归 思路一很明显没有充分利用这是一颗完全二叉树的条件。从另一个角度看，一颗完全二叉...

这时一道典型的DP题。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。在这道题目中，如果我们想要计算S中含有几个T（假设S长度为n，T长度为m），那么我们只需要知道S[0...n]含有几个T[0...m-1]以及S[0...n-1]含有几个T[0...m-1]。从中归纳出最普遍的场景...

题目要求 {代码...} 假设有一个升序排序的数组，在某个节点处断开并调换了顺序。寻找这个断开数组中的最小元素。 当数组中不存在重复的元素 通过二分法来实现在logN的时间中找到最小的值。通过二分法往往会有以下几种情况 位于一个升序的数组中，也就是左侧值小于右侧值，这时候左侧值就是最小值。 左侧值小于中间值，那...

还有一种方法是指将链表的结果给拆掉，一旦遍历过当前节点，就将当前节点的下一个指针指向dummy节点。如果有环，就会重复遇到这个指向dummy的节点。则该链表有环，且该节点就是环的起始节点。但是这个方法会毁坏原来链表的数据结构。

计算后缀表达式。我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。

关于正则表达式的详细信息，请参考我的这篇博客在这里，我们只需要将句子中的单词通过split的正则表达式读取出来即可。这里用到的正则表达式为\s+,也就是遇到一个或多个空白时断句。

在看下面的文章前，请先参考我的这篇文章关于Single Number I。按照思路一和思路二很容易将这题解决。下面要讲一个通过位计算来实现的方法。在这里，我们希望将出现三次的数字通过%3操作划掉。比如将一个数字化为二进制数之后，在某一位上的数字为1，则1*3%3=0，如果在某一位上为0，则0*3%3=0。也就是说，出现三次的数值...

可以通过set来记录数字出现的情况。如果set中不曾出现该数字，则加入set。如果已经出现，则将其从set中删除。最后无法从set中删除的数字，则是single number

u may assume beginWord and endWord are non-empty and are not the same.

将一个字符串逐渐分解为一个叶节点为单个字母的树。允许对非叶结点的两个子节点进行旋转，且允许对多个非叶节点进行子节点的旋转操作。将该操作生成的新字符串成为scrambled string。现在输入两个字符串，判断该两个字符串是否是scrambled string。

在这里和其它题目不一样的是，并非从根节点到叶节点的一条路径，而是从任意一个节点到任意一个节点的路径。其实在这里我们通过递归的方法可以发现以下几种场景：

假设输入两个单词beginWord，endWord以及一个字典。每一次操作只能对当前单词修改一个字符成为字典中的一个单词。问至少需要多少次操作可以将beginWord转化为endWord。如果不可转换则返回0。

在这里需要注意的是，因为提供的数据结构为链表，所以我们必须顺序遍历才能知道该链表的长度以及该链表的中间位置。在这里，我们可以采用递归的形式，而且在递归中我们通过双指针的方式找到其中的中间节点。并依次递归左子节点和右子节点。

如果只是单纯的计算二叉树的数量，其实这就完全转化成了一道规律题。我们可以从1开始寻找规律。1： 11，2： 12， 211，2，3：123，132，213，312，321

给一个完全二叉树，将当前节点的next值指向其右边的节点。而在II中则是提供了一个不完全的二叉树，其它需求没有发生改变。额外的需求包括O(1）的空间复杂度

题目要求 {代码...} 将一棵二叉树展开形成一棵链表形状的树。本质上是将该树转变成先序遍历后的样子。 思路一：非递归 如果我们从图形的角度来说，每一次都将当前节点的右子树拼接到左子节点的右子树下，再将左节点替换原来的右节点。所以这个例题一步步的操作如下： {代码...} 代码如下： {代码...} 思路二：递归 其实...

dp的一个思路就是通过存储换效率。也就是说，我将前序遍历过程中的一些有效值存储下来，以供后序遍历参考。从而省去了许多重复遍历，提高效率。这里我使用两个二维int数组来分别记录到matrix[i][j]为止的最大长度和最大高度。如果matrixi不是最左侧和最上侧的点，还需要判断其所能构成的最大矩形。

乍一看这题可以通过递归的方式来求解。我们可以同时判断当前下标s1和s2的元素是不是和s3当前下标的元素相同。如果相同，就进入下一轮递归。代码如下：

这是一道典型的backtracking的题目，通过递归的方式记录尝试的节点，如果成功则加入结果集，如果失败则返回上一个尝试的节点进行下一种尝试。

通过栈的形式同样可以实现比较。将需要进行比较的节点依次压入栈中。每次从栈中取出两个进行比较的节点比较。有点像level traversal的思路。

其实在数据结构的教材中为了说明栈和队列的使用，分别举的就是中序遍历和水平遍历的例子。在这里我们同样可以使用队列的先进先出的机制将同一行的元素读入后，再逐个读出，并在同时插入下一行中的元素。

我们可以发现，如果已知当前节点的值val以及取值的上下限upper，lower，那么左子节点的取值范围就是(lower, val),右子节点的取值范围就是(val, upper)。由此出发递归判断，时间复杂度为O(n)因为每个节点只需要遍历一次。

如果了解中序遍历的同学可以知道，一颗二叉查找树的中序遍历结果应当是一个数值有小到大递增的数组。正因为中序遍历是指先遍历左子树，接着遍历中间节点，再遍历右子树，恰好和查找树的值递增顺序相同。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。代码如下：

如果了解中序遍历的同学可以知道，一颗二叉查找树的中序遍历结果应当是一个数值有小到大递增的数组。正因为中序遍历是指先遍历左子树，接着遍历中间节点，再遍历右子树，恰好和查找树的值递增顺序相同。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。代码如下：