题目(字符串的排列—牛客网)

输入一个字符串,按字典序打印出该字符串中字符的所有排列(不重复)。例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,ca b和 cba。

算法思路

本题为经典的全排列问题，但是要处理一些细节问题。
全排列的思路分为两步：第一步是求所有可能出现在第一个位置上的字符，即把第一个字符和后面所有的字符(包括第一个字符)交换。第二步就是，在固定第一个位置上的字符时，求后面所有字符的全排列，即得到了原问题的子问题，我们利用递归求解即可。
本题中还需要使得输出的字符排列符合字典序，那么我们只要保证在全排列开始前，字符串符合字典序即可，即对字符进行升序即可。另外，这里还可能涉及到排列重复的问题，比如输入字符串 “aa”，那么将会出现重复的排列，解决办法就是在第一个字符和后面的所有字符交换前判断，交换的那对字符是否相同(需排除与自身交换)，若相同可跳过对该元素的交换。

算法实现

拓展：字符串的组合

输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

算法思路一(递归法)

对于长度为 n 的字符串，我们需要从中选择 m 个字符进行组合，其中 1<=m<=n。我们需要遍历这 m 的可能值，对应于输出含 m 个元素的字符串组合。那么对于每一个组合，如果我们选中了字符串的第一个位置，那么只要递归求解子问题：从长度为 n-1 的字符串中选择 m-1 个字符进行组合，而如果字符串的第一个位置不选，那么只要递归求解子问题：从长度为 n-1 的字符串中选择 m 个字符进行组合。

算法思路二(位操作)

假设字符串长度为 n，那么恰好它的所有组合均可由 1 到 (1<<n)二进制数表示得到，例如 001 对应于组合 a，111对应于组合 abc 等。因此，我们只要把二进制中的 1 对应到所求组合即可。这里我们利用掩码即与操作转换。

算法实现(递归法)

算法实现(位操作)

字符全排列拓展之八皇后问题

在 8×8 的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请求出总共有多少种摆法。

算法思路

由于八个皇后的任意两个不能处在同一行，那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组 ColumnIndex[8]，数组中第 i 个数字表示位于第 i 行的皇后的列号。先把 ColumnIndex 的八个数字分别用 0-7 初始化，接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字，因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上(正对角线和副对角线)，也就是数组的两个下标 i 和 j，是不是 i-j==ColumnIndex[i]-Column[j] 或者 j-i==ColumnIndex[i]-ColumnIndex[j]，即行差==列差。

算法实现

参考

[1] <<剑指offer2>>
[2] 字符串的全排列和组合算法

题目(序列化二叉树—牛客网)

请实现两个函数，分别用来序列化和反序列化二叉树。

算法思路

总体思路是利用前序遍历进行序列化和反序列化，但是我们知道仅有前序遍历是无法确定一颗二叉树的，所以我们还需要要给叶节点的空指针赋予特殊的标记 ‘#’，这样一来，当递归遇到’#’时，我们就知道了该跳出递归了，回溯完之后就进入右子树处理了。另外，二叉树的节点值可能有两位数，这样就不能单靠指针的移动就能确定二叉树的节点值，还需要加入分割标记，因此我们序列化的时候，需额外追加逗号，分割开不同的二叉树节点值，方便反序列化取出节点值。

处理思路一

1. 借助整形类型的vector数组存储二叉树节点值，所以我们进行序列化的时候，对二叉树进行前序遍历(或称DFS)将节点加入数组，当节点为空的时候，加入特殊值 0x23333，并退出递归。但由于函数需要返回字符数组类型，因此还需要将vector数组中的元素一一复制到动态整形数组中，最后对整形数组强制类型转为字符类型。
2. 反序列化时，先将字符数组类型强制类型转为整形数组，然后二叉树节点的值就可以直接从整形数组中得到。首先，处理递归出口，如果遇到 ox23333，则指针移动一个单位并退出递归。否则构造二叉树根节点，并继续移动指针，连接递归得到的左子树，以及右子树。

处理思路二

1. 借助string类型的变量来拼接序列化的字符串。只需前序遍历二叉树，当遇到根节点为空时，追加 ‘#’，并退出递归，否则追加二叉树的根节点值，接着追加逗号。接下只需递归实现左子树和右子树的序列化。那么，序列化之后得到了string类型的字符串，最后构造动态字符数组，将字符串的每一个字符复制到字符数组中，结尾加入’\0’标记结束。
2. 进行反序列化时，如果遇到 ‘#’ ，那么指针移动一个单位，退出递归。否则，找到字符数组中的一个二叉树节点值，然后构造根节点，如果此时到达字符末尾，直接返回根节点，否则指针继续移动一个单位。接下来根节点的左右指针分别连接左子树的递归实现结果和右子树的递归实现结果。

算法实现

算法实现一

算法实现二

参考

[1]. <<剑指offer2>>
[2]. <<牛客网>>

题目(二叉搜索树与双向链表—牛客网)

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

算法思路

利用二叉树的中序遍历二叉搜索树，得到的序列恰为递增有序，因此采用中序遍历二叉搜索树。

非递归版本

1. 结合栈，对二叉搜索树进行遍历；
2. 只需要当前访问的节点(即当前出栈的节点,除了访问根节点)和其前一个访问的节点(即上一个出栈的节点)进行互相连接即可；
3. 所以在 1 进行的过程中，还需要记录访问节点的前一节点 pre。

递归版本

1. 考虑特殊值即根节点为空；
2. 考虑递归出口，即最简单的情况，一般都是直接返回叶节点；
3. 现将二叉搜索树分为三部分，左子树，根，右子树，那么按照顺序，需要将左子树形成的链表的最后一个节点和根节点互相连接，而右子树形成的链表的首节点和根节点互相连接；
4. 那么对于左子树和右子树只需递归执行方法即可；
5. 函数都返回链表的首节点，因此对于左链表来需要遍历到其尾节点。

算法实现

非递归版本

递归版本

算法复杂度

时间复杂度均为O(n)，空间复杂度方面，递归版本需要消耗递归栈，而非递归版本消耗栈的空间。

参考

<<剑指offer2>>

题目(复杂链表的复制—牛客网)

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

算法思路

算法分为三步。
第一步：对于链表中的每个节点 N ，它的复制节点 N’，链接到它的后面，这样复制完后，形成了新的链表。(N’链接到 N 的下一个节点)
第二步：链接随机节点。采用第一步的构造方式给第二步带来了遍历。因为原链表中节点 N 的随机节点的下一个节点就是 节点 N’ 的随机节点，这样一来就可以遍历新链表中原链表的那些节点就行了。
第三步：将新链表拆分成原链表和复制链表。定义复制链表头结点以及其工作指针用于链接所有复制节点。再定义原链表的工作指针，用于链接原链表中的节点，最后整个新的链表就被两个工作指针拆分成了两个链表。

算法实现

复杂度分析

算法对原链表在线性时间内遍历，因此时间复杂度为 O(n)，空间复杂度为 O(1)(生成节点不算)

参考

<<剑指offer2>>

题目(二叉树中和为某一值的路径—牛客网)

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

算法思路

首先，处理根节点为空的情况；

接下来，按照前序遍历的思想从根节点开始递归搜索，每次先将节点加入路径，然后更新期望的路径和，即减去当前已加入路径的节点值,利用数组 path 存放当前已加入路径的节点值，然后依次判断根节点的左右子树是否存在，存在则继续递归寻找，待递归返回后，必须从路径中移除当前节点，以便继续记录其余路径；

最后，就是递归出口。当遇到了叶节点，并且叶节点的值刚好等于剩余期望的路径和，那么就找到了一条路径；最后依然要从路径中移除当前节点，以便继续记录其余路径，最后再返回。

算法实现

复杂度分析

算法遍历了每个节点，时间复杂度为 O(n)，空间复杂度主要在递归栈，大致消耗 O(logn)的空间,还有一些辅助数组空间。

参考

<<剑指offer2>>