package com.dengzm.jianzhioffer;
/**
* @Description 035 复杂链表的复制
* 在复杂链表中，每个节点除了指向下一个节点，还有一个变量指向链表中的任意节点或为null
*
* Created by deng on 2019/5/25.
*/
public class Jianzhi035 {
public static void main(String[] args) {
ComplexListNode node1 = new ComplexListNode(1);
ComplexListNode node2 = new ComplexListNode(2);
ComplexListNode node3 = new ComplexListNode(3);
ComplexListNode node4 = new ComplexListNode(4);
ComplexListNode node5 = new ComplexListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node1.sibling = node3;
node2.sibling = node4;
node3.sibling = node5;
node5.sibling = node1;
ComplexListNode clonedHead = clone(node1);
while (clonedHead != null) {
System.out.println("Node:value=" + clonedHead.value + ", next=" + clonedHead.next + ", sibling=" + clonedHead.sibling);
clonedHead = clonedHead.next;
}
}
private static ComplexListNode clone(ComplexListNode head) {
cloneNodes(head);
connectSibling(head);
return getClonedHead(head);
}
/**
* 将每个节点复制一份，接在各自的后面
*
* @param head head
*/
private static void cloneNodes(ComplexListNode head) {
ComplexListNode temp = head;
while (temp != null) {
ComplexListNode clone = new ComplexListNode(temp.value);
clone.next = temp.next;
temp.next = clone;
temp = clone.next;
}
}
/**
* 为clone节点的sibling赋值
*
* @param head head
*/
private static void connectSibling(ComplexListNode head) {
ComplexListNode temp = head;
while (temp != null) {
ComplexListNode clone = temp.next;
if (temp.sibling != null) {
clone.sibling = temp.sibling.next;
}
temp = clone.next;
}
}
/**
* 将复制的列表提取出来；并恢复原链表
*
* @param head originalHead
* @return new head
*/
private static ComplexListNode getClonedHead(ComplexListNode head) {
ComplexListNode temp = head;
ComplexListNode clonedHead = null;
ComplexListNode cloneNode = null;
if (temp != null) {
clonedHead = cloneNode = temp.next;
temp.next = cloneNode.next;
temp = temp.next;
}
while (temp != null) {
cloneNode.next = temp.next;
cloneNode = cloneNode.next;
temp.next = cloneNode.next;
temp = temp.next;
}
return clonedHead;
}
private static class ComplexListNode {
int value;
ComplexListNode next;
ComplexListNode sibling;
public ComplexListNode(int value) {
this.value = value;
}
@Override
public String toString() {
return super.toString() + ":" + value;
}
}
}
package com.dengzm.jianzhioffer;
/**
* @Description 036 二叉搜索树与双向链表
* 输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
*
* Created by deng on 2019/5/25.
*/
public class Jianzhi036 {
public static void main(String[] args) {
BinaryTreeNode node1 = new BinaryTreeNode(10);
BinaryTreeNode node2 = new BinaryTreeNode(6);
BinaryTreeNode node3 = new BinaryTreeNode(14);
BinaryTreeNode node4 = new BinaryTreeNode(4);
BinaryTreeNode node5 = new BinaryTreeNode(8);
BinaryTreeNode node6 = new BinaryTreeNode(12);
BinaryTreeNode node7 = new BinaryTreeNode(16);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
ListNode head1 = convert(node1, true);
while (head1 != null) {
System.out.print(head1.value + " ");
head1 = head1.next;
}
System.out.println();
ListNode head2 = convert(node1, false);
while (head2 != null) {
System.out.print(head2.value + " ");
head2 = head2.pre;
}
}
private static ListNode convert(BinaryTreeNode root, boolean returnStart) {
if (root == null) {
return null;
}
ListNode rootNode = new ListNode(root.value);
if (root.left != null) {
ListNode left = convert(root.left, false);
left.next = rootNode;
rootNode.pre = left;
}
if (root.right != null) {
ListNode right = convert(root.right, true);
right.pre = rootNode;
rootNode.next = right;
}
if (returnStart) {
while (rootNode.pre != null) {
rootNode = rootNode.pre;
}
} else {
while (rootNode.next != null) {
rootNode = rootNode.next;
}
}
return rootNode;
}
private static class ListNode {
int value;
ListNode pre;
ListNode next;
public ListNode(int value) {
this.value = value;
}
}
}
package com.dengzm.jianzhioffer;
/**
* @Description 038 字符串的排列
* 输入一个字符串，打印出该字符串中字符的所有排列。
*
* Created by deng on 2019/5/25.
*/
public class Jianzhi038 {
public static void main(String[] args) {
String target = "abcdefg";
printAll(target);
}
private static void printAll(String target) {
if (target == null || target.length() == 0) {
return;
}
if (target.length() == 1) {
System.out.println(target);
return;
}
char[] targetChar = target.toCharArray();
printAllCore(targetChar);
}
private static void printAllCore(char[] target) {
for (int i = 0; i < target.length - 1; i ++) {
for (int j = i + 1; j < target.length; j ++) {
switchData(target, i, j);
System.out.println(String.valueOf(target));
switchData(target, i, j);
}
}
}
private static void switchData(char[] target, int i, int j) {
char temp = target[i];
target[i] = target[j];
target[j] = temp;
}
}
