The Decomposition of “Sword offer” Makes Complex Problems Simpler

  algorithm, Front end, Interview, javascript

1. Copy of Complex Linked List

Enter a complex linked list (each node has a node value and two pointers, one pointing to the next node and the other special pointer pointing to any node), and the returned result is the head of the copied complex linked list. (Note, please do not return the node reference in the parameter in the output result)

Train of thought

Split into three steps

1. Copy a linked list and place it after the previous node, that is, create N according to each node N of the original linked list, put nPut it directly at the next position of n, and let the copied linked list and the original linked list form a new linked list.

2. assign a value to the copied linked list random, i.e. n `. random = n.random.next.

3. Split the linked list, splitting N’ and N to ensure that the original linked list is not affected.

Code

function Clone(pHead) {
if (pHead === null) {
return null;
}
cloneNodes(pHead);
cloneRandom(pHead);
return reconnetNodes(pHead);
}

function cloneNodes(pHead) {
var current = pHead;
while (current) {
var cloneNode = {
label: current.label,
next: current.next
};
current.next = cloneNode;
current = cloneNode.next;
}
}

function cloneRandom(pHead) {
var current = pHead;
while (current) {
var cloneNode = current.next;
if (current.random) {
cloneNode.random = current.random.next;
} else {
cloneNode.random = null;
}
current = cloneNode.next;
}
}

function reconnetNodes(pHead) {
var cloneHead = pHead.next;
var cloneNode = pHead.next;
var current = pHead;
while (current) {
current.next = cloneNode.next;
current = cloneNode.next;
if (current) {
cloneNode.next = current.next;
cloneNode = current.next;
} else {
cloneNode.next = null;
}
}
return cloneHead;
}

2. The binary search tree is converted into a double linked list

Enter a binary search tree and convert the binary search tree into an ordered double linked list. It is required that no new node can be created, only the point of the node pointer in the tree can be adjusted.

Train of thought

1. Ordered Double Linked List-Middle Order Traversal Binary Tree

2. Record the last node of the linked list

3. Each traversal: set the left of the tree node and the right of the linked list to link. After successful linking, the current node becomes the end node of the linked list and returns.

Code

function Convert(pRootOfTree) {
 var lastNode = null;
 lastNode = convertToList(pRootOfTree, lastNode);
 while (lastNode && lastNode.left) {
 lastNode = lastNode.left;
 }
 return lastNode;
 }
 
 function convertToList(treeNode, lastNode) {
 if (!  treeNode) {
 return null;
 }
 if (treeNode.left) {
 lastNode = convertToList(treeNode.left, lastNode);
 }
 treeNode.left = lastNode;
 if (lastNode) {
 lastNode.right = treeNode;
 }
 lastNode = treeNode;
 if (treeNode.right) {
 lastNode = convertToList(treeNode.right, lastNode);
 }
 return lastNode;
 }

3. Arrangement of character strings

Enter a string and print out all the arrangements of characters in the string in dictionary order. For example, if the character string abc is input, all the character strings abc,acb,bac,bca,cab and cba that can be arranged by the characters A, B and C will be printed.

Enter a string with a length of not more than 9 (there may be repeated characters), and the characters include only upper and lower case letters.

Train of thought

1. Divide the string into two parts, the first character and the following characters
2. The full arrangement of the whole string is equal to: the full arrangement of the first character+the following characters, and the interchange of the first character and the following characters.

The full arrangement of the first character+the following characters 3. The full arrangement of other characters except the first character is equal to the full arrangement of the second character+the following characters.

3. Recursion, recording the position of a current node, and recording an arrangement when the position points to the last node.

Code

function Permutation(str) {
var result = [];
if (!  str) {
return result;
}
var array = str.split('');
permutate(array, 0, result);
result.sort();
return [... new Set(result)];
}

function permutate(array, index, result) {
if (array.length - 1 === index) {
result.push(array.join(''));
}
for (let i = index;   i < array.length;  i++) {
swap(array, index, i);
permutate(array, index + 1, result);
swap(array, i, index);
}
}

function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}