面试题35：复杂链表的复制
题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling 指向链表中的任意结点或者nullptr。
public class Node {
public int val;
public Node next;
public Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
} public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 细节：遍历时要以移动指针为准，以克隆指针为准容易在最后一个结点出幺蛾子
copyNodes(head);
copyRandomPointer(head);
return splitCopiedList(head);
}
private void copyNodes(Node head) {
Node move = head;
while (move != null) {
Node cloneNode = new Node(move.val);
cloneNode.next = move.next;
move.next = cloneNode;
move = cloneNode.next;
}
}
private void copyRandomPointer(Node head) {
Node move = head;
while (move != null) {
Node cloneNode = move.next;
if (move.random != null) {
cloneNode.random = move.random.next;
}
move = cloneNode.next;
}
}
private Node splitCopiedList(Node head) {
Node cloneHead = head.next;
Node move = head;
Node cloneNode = head.next;
move.next = cloneNode.next; // 遍历时让move在cloneNode前面，保证原链表最后一个结点的next指向null
move = move.next;
while (move != null) {
cloneNode.next = move.next;
cloneNode = cloneNode.next;
move.next = cloneNode.next;
move = move.next;
}
return cloneHead;
} 面试题36：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向循环链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
4 / \ 2 5 -> ==> 1 <=> 2 <=> 3 <=> 4 <=> 5 <== / \ || || 1 3 ||=============================||
public class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
}; - 算法：
- 中序遍历
- 遍历左子树，获得并保存已经转换好部分的最后一个结点largestNode
- largestNode和当前遍历到的node进行连接并更新largestNode
- 继续使用largestNode遍历右子树
- 中序遍历
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
Node largestNode = null;
largestNode = convertNode(root, largestNode);
Node headNode = largestNode;
while (headNode != null && headNode.left != null) {
headNode = headNode.left;
}
largestNode.right = headNode;
headNode.left = largestNode;
return headNode;
}
private Node convertNode(Node node, Node largestNode) {
if (node == null) {
return largestNode;
}
if (node.left != null) {
largestNode = convertNode(node.left, largestNode);
}
node.left = largestNode;
if (largestNode != null) {
largestNode.right = node;
}
largestNode = node;
if (node.right != null) {
largestNode = convertNode(node.right, largestNode);
}
return largestNode;
} 面试题37：序列化二叉树
题目：请实现两个函数，分别用来序列化和反序列化二叉树。
- 算法：
- 前序遍历序列化（包括叶子节点的null子节点也要遍历）
- 前序遍历反序列化
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();
serialize(root, stringBuilder);
return "["+stringBuilder.substring(0, stringBuilder.length()-1)+"]";
}
private void serialize(TreeNode root, StringBuilder stringBuilder) {
if (root == null) {
stringBuilder.append("null,");
} else {
stringBuilder.append(root.val+",");
serialize(root.left, stringBuilder);
serialize(root.right, stringBuilder);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
data = data.substring(1, data.length()-1);
String[] nodes = data.split(",");
Queue<String> queue = new LinkedList<String>();
queue.addAll(Arrays.asList(nodes));
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
String s = queue.poll();
if (s.equals("null")) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(s));
root.left = deserialize(queue);
root.right = deserialize(queue);
return root;
} - 算法：
- 队列
- 层次遍历
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
String output = "";
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
while(!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (node == null) {
output += "null, ";
continue;
}
output += node.val + ", ";
nodeQueue.add(node.left);
nodeQueue.add(node.right);
}
return "[" + output.substring(0, output.length() - 2) + "]";
}
public TreeNode deserialize(String input) {
input = input.trim();
if (input.length() == 0) {
return null;
}
input = input.substring(1, input.length() - 1);
String[] parts = input.split(",");
String item = parts[0];
TreeNode root = new TreeNode(Integer.parseInt(item));
Queue<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
int index = 1;
while(!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int leftNumber = Integer.parseInt(item);
node.left = new TreeNode(leftNumber);
nodeQueue.add(node.left);
}
if (index == parts.length) {
break;
}
item = parts[index++];
item = item.trim();
if (!item.equals("null")) {
int rightNumber = Integer.parseInt(item);
node.right = new TreeNode(rightNumber);
nodeQueue.add(node.right);
}
}
return root;
} 面试题38：字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。字符串可能包含重复字符，结果不能有重复排列。
public String[] permutation(String s) {
if (s == null || s.length() == 0) {
return new String[0];
}
char[] chars = s.toCharArray();
HashSet<String> result = new HashSet<>();
permutation(chars, 0, result);
String[] stringArray = new String[result.size()];
return result.toArray(stringArray);
}
private void permutation(char[] chars, int begin, HashSet<String> result) {
if (begin == chars.length) {
result.add(new String(chars));
} else {
for (int i = begin; i < chars.length; i++) {
swap(chars, i, begin);
permutation(chars, begin+1, result);
swap(chars, i, begin);
}
}
}
private void swap(char[] array, int x, int y) {
char temp = array[x];
array[x] = array[y];
array[y] = temp;
} 
京公网安备 11010502036488号