1.复杂链表的复制
问题描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路：
按照正常的思路，首先从头到尾遍历链表，拷贝每个节点的 value 和 next 指针。然后从头再次遍历，第二次遍历的目的在于拷贝每个节点的 sibling 指针。
然而即使找到原节点的 sibling 指针，还是得为了找到复制节点对应的 sibling 指针而再遍历一遍。那么对于 n 个要寻找 sibling 指针的节点，复杂度就是 O(N*N)。
显然，为了降低复杂度，必须从第二次遍历着手。这里采用的方法是，在第一次遍历的时候，把 (原节点, 复制节点) 作为映射保存在表中。那么第二次遍历的时候，就能在 O(1) 的复杂度下立即找到原链上 sibling 指针在复制链上对应的映射。
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(pHead) {
// write code here
if (!pHead || !pHead.next) {
return pHead;
}
const map = new Map();
let node = pHead;
const newHead = new RandomListNode(node.label);
let newNode = newHead;
map.set(node, newNode);
while (node.next) {
newNode.next = new RandomListNode(node.next.label);
node = node.next;
newNode = newNode.next;
map.set(node, newNode);
}
newNode = newHead;
node = pHead;
while (newNode) {
newNode.random = map.get(node.random);
newNode = newNode.next;
node = node.next;
}
return newHead;
}
2.二叉搜索树与双向链表
问题描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路：
- 中序遍历一遍二叉搜索树，将节点保存在一个数组中。
- 遍历数组，更改每个节点的 left 和 right
- 返回数组第一个元素
时间复杂度是 O(N)，空间复杂度是 O(N)。相较于方法二，多开辟了 O(N)的数组空间。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree) {
// write code here
if (!pRootOfTree) {
return null;
}
const nodes = [];
midTravel(pRootOfTree, nodes);
const len = nodes.length;
for (let i = 0; i < len; i++) {
nodes[i].right = nodes[i + 1] || null;
nodes[i].left = nodes[i - 1] || null;
}
return nodes[0];
}
//中序遍历,将所有节点存在nodes中
function midTravel(node, nodes) {
if (node.left) {
midTravel(node.left, nodes);
}
nodes.push(node);
if (node.right) {
midTravel(node.right, nodes);
}
}
3.字符串的排列
问题描述：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba。
输入描述：输入一个字符串,长度不超过 9(可能有字符重复),字符只包括大小写字母。
输出描述：输出是一个数组
解题思路：
abc 的所有组合可以这么理解：
每次取一个字符出来，比如'a'，然后剩下的字符组合成'bc'，'bc'的所有组合可以通过递归来获取，在 bc 的所有组合前面都拼接一个字符'a'；
再取出字符'b'，剩下的字符拼接成'ac'，同样的方法：'ac'的组合可以通过递归，在'ac'的所有组合前面都拼接一个字符'b'，
依次类推...
但是要注意：每次取出来的字符不能与前面的字符相同，所有用一个数组 map 来记录每次取出来的值
function Permutation(str) {
// write code here
var arr = [];
if (str.length === 0) return [];
if (str.length === 1) {
arr.push(str);
} else {
var map = []; //用来判断是不是每次取出来的字符与前面取出来的是否有重复
for (let i = 0; i < str.length; i++) {
var s = str[i]; // 索引为i的字符
if (!map.includes(s)) {
var st = str.slice(0, i) + str.slice(i + 1); // 剩下的字符拼接成一个新字符
var a = Permutation(st); // 递归，找出新字符的排列组合
a.forEach((ele) => arr.push(s + ele));
}
map.push(s); //把s加入到map中
}
}
return arr;
}