发表于   |   分类于
题目输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串 abc、acb、bac、bca、cab和cba。（可能有字符重复，字符只包括大小写字母） 分析把一个字符串看成由两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符。 ...
阅读全文 »

发表于   |   分类于
题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 分析使用二叉树的中序遍历，并更改原节点的left和right引用指向。 注意：更改链表尾节点的引用，需要声明一个相应的全局变量。 实现123456789101112131415 ...
阅读全文 »

发表于   |   分类于
题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点或者为null），返回结果为复制后复杂链表的head。 分析方法一 时间复杂度是 $O(n_2)$。 思路： 复制原始链表上的每个节点，并用next连接起来； 设置节点的random指针，在 ...
阅读全文 »

发表于   |   分类于
题目输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 分析由于路径是从根结点出发到叶结点， 也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结 ...
阅读全文 »

发表于   |   分类于
题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。 分析后序遍历的序列中最后一个总是树（子树）的根节点，同时二叉搜索树的性质是左子树都小于根节点，且右子树都大于根节点。确定根节点后，依次遍历其子树序列 ...
阅读全文 »

发表于   |   分类于
题目输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列1、2、3、4、5是某栈的压入序列，序列4、5、3、2、1是该栈的对应的一个弹出序列，但是4、3、5、1、2就不可能是该栈的弹出序列。 分析思路：借助辅助栈，把压入序列的数 ...
阅读全文 »

发表于   |   分类于
题目定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push以及pop的时间复杂度都是O(1)。 分析如果在定义的数据结构中，仅仅通过添加一个全局变量来保存最小元素，当最小元素出栈时，则得不到下一个最小元素。 思路：通过一个辅助栈来保存每次应该存放的最小 ...
阅读全文 »

发表于   |   分类于
题目输入一个矩阵，按照从外往里以顺时针的顺序依次打印出每一个数字。 分析把打印一圈分为四步：第一步从左到右打印一行，第二步从上到下打印一列，第三步从右到左打印一行，第四步从下到上打印一列。每一步我们根据起始坐标和终止坐标用一个循环就能打印出一行或者一列。 最后一圈有可能退化成只有一行、只有一列，甚至 ...
阅读全文 »