剑指offer-java实现

package offer; /输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后 的链表满足单调不减规则。 public class AddList public static void main(String args) ListNode list1 = new ListNode(1, null); ListNode list2 = new ListNode(2, null); for (int i = 3; i = 0) /如果相等 if(arrayij = target) return true; /如果比target大，则在本行内 else if(arrayij target) j-; continue; /如果比target大，则在下一行 else i+; continue; return false; package offer; /把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 /输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 /例如数组3,4,5,1,2为1,2,3,4,5 的一个旋转，该数组的最小值为 1。 /NOTE：给出的所有元素都大于0，若数组大小为 0，请返回0。 public class ChangeArrays public static void main(String args) ChangeArrays a = new ChangeArrays(); System.out.print(a.minNumberInRotateArray(new int3,4,5,1,2); public int minNumberInRotateArray(int array) int left=0,right=array.length -1; int temp=0; while(arrayrightarraytemp) right = temp; else right = temp; return arraytemp; package offer; /输入两棵二叉树A，B，判断 B是不是A的子结构。（ps：我们约定空树不是任意 一个树的子结构） public class ChildTree public boolean HasSubtree(TreeNode root1,TreeNode root2) /如果有树等于空，则不存在 if(root1=null|root2=null) return false; boolean flag = false; /如果有节点相等，验证该节点 if(root1.val=root2.val) flag = isSubtree(root1,root2); /验证左子树是否相等 if(flag=false) flag = HasSubtree(root1.left,root2); /验证右子树是否相等 if(flag=false) flag = HasSubtree(root1.right,root2); return flag; public boolean isSubtree(TreeNode root1,TreeNode root2) if (root1=null if (root2 = null) return true; if(root1.val!=root2.val) return false; return isSubtree(root1.left,root2.left) package offer; import java.util.HashMap; /输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节 点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。 /（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回 空） public class CopyList /复制、链接、拆分 public ListNode Clone(ListNode pHead) if(pHead=null) return null; ListNode pCur = pHead; /复制next 如原来是A-B-C 变成A-A-B-B-C-C while(pCur!=null) /复制节点 ListNode node = new ListNode(pCur.value); node.next = pCur.next; pCur.next = node; /当前节点后移一位 pCur = node.next; pCur = pHead; /复制random pCur是原来链表的结点 pCur.next是复制pCur 的结点 while(pCur!=null) if(pCur.random!=null) pCur.next.random = pCur.random.next; pCur = pCur.next.next; /复制的链表 ListNode head = pHead.next; ListNode cur = head; pCur = pHead; /拆分链表 while(pCur!=null) /还原链表 pCur.next = pCur.next.next; if(cur.next!=null) /拆分链表 cur.next = cur.next.next; cur = cur.next; pCur = pCur.next; return head; /复制、链接、拆分 public ListNode Clone1(ListNode pHead) if (pHead = null) return null; /当前节点 ListNode pCur = pHead; HashMap nodeMap = new HashMap(); / 复制next并入map while (pCur != null) / 复制节点 ListNode node = new ListNode(pCur.value); nodeMap.put(pCur, node); / 当前节点后移一位 pCur = pCur.next; pCur = pHead; /复制节点 ListNode head = nodeMap.get(pCur); / 建立连接 while (pCur != null) if (pCur.random != null) head.random =nodeMap.get(pCur.random); head.next = nodeMap.get(pCur.next); return nodeMap.get(pHead); package offer; import java.util.Arrays; /输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的 前序遍历和中序遍历的结果中都不含重复的数字。 /例如输入前序遍历序列1,2,4,7,3,5,6,8 和中序遍历序列 4,7,2,1,5,3,8,6，则重建二叉树并返回。 public class CreatTree /前序和中序 public TreeNode reConstructTree(int pre,int in) TreeNode root=constructTree(pre,in); return root; /前序遍历1,2,4,7,3,5,6,8 和中序遍历序列 4,7,2,1,5,3,8,6 private TreeNode constructTree(int pre,int in) if(pre.length = 0| in.length = 0) return null; /前序的第一个是根节点 TreeNode root=new TreeNode(pre0); /找到中序遍历中根节点所在位置 for(int i=0;i=end) return true; int root = sequenceend; /左右子树的分届 int i=start; while(sequenceiroot Stack data = new Stack(); public void push(int node) data.push(node); if(min.empty() min.push(node); else if(nodemin.peek() min.push(min.peek(); else min.push(node); public void pop() if(!data.empty() min.pop(); data.pop(); public int top() return data.peek(); public int min() if(!min.empty() return min.peek(); return 0; package offer; /操作给定的二叉树，将其变换为源二叉树的镜像 public class MirrorTree public void Mirror(TreeNode root) if(root!=null) swap(root); Mirror(root.left); Mirror(root.right); public void swap(TreeNode root) TreeNode temp = null; temp = root.left; root.left = root.right; root.right = temp; package offer; /输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇 数位于数组的前半部分，所有的偶数位于位于数组的后半部分， /并保证奇数和奇数，偶数和偶数之间的相对位置不变。 public class OddAndEven public static void main(String args) OddAndEven instance = new OddAndEven(); instance.reOrderArray(new int1,2,3,4,5,6,7); /借鉴与插入排序 public void reOrderArray(int array) for(int i=1;i= 1 j-; arrayj = target; package offer; import java.util.Stack; /输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为 该栈的弹出顺序。 /假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序 列4，5,3,2,1是该压栈序列对应的一个弹出序列， /但4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度 是相等的） public class PopOrder public boolean IsPopOrder(int pushA,int popA) Stack data = new Stack(); int i=0,j=0; for(i=0;i arrayList=new ArrayList(); public ArrayList printListFromTailToHead(ListNode listNode) /递归放到arrayList中保存 if(listNode!=null) this.printListFromTailToHead(listNode.next); arrayList.add(listNode.value); return arrayList; /链表类 class ListNode static int i=0; int value; ListNode next = null; /随机指向一个节点 ListNode random = null; ListNode(int value) this.value = value; i+; ListNode(int value,ListNode listnode) this.value = value; i+; package offer; import java.util.ArrayList; /输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字， /例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 /则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10. public class PrintMatrix public ArrayList printMatrix(int array) ArrayList result = new ArrayList (); if(array.length=0) return result; /n是行，m是列 int n = array.length,m = array0.length; if(m=0) return result; /这个是层数 int layers = (int) Math.ceil(Math.min(n,m)/2.0); for(int i=0;i=i)k-) result.add(arrayn-i-1k); /左下至左上 for(int j=n-i-2;(ji)j-) result.add(arrayji); return result; package offer; import java.util.*; /从上往下打印出二叉树的每个节点，同层节点从左至右打印 public class PrintTree public static void main(String args) PrintTree a = new PrintTree(); TreeNode root = new TreeNode(1); TreeNode right = new TreeNode(3); TreeNode left = new TreeNode(2); root.left=left; root.right= right; a.PrintFromTopToBottom(null); public ArrayList PrintFromTopToBottom(TreeNode root) /临时存储节点 Queue tree = new LinkedList(); /从上到下节点 ArrayList result = new ArrayList(); tree.offer(root); TreeNode temp = null; while(!tree.isEmpty() if(temp.left!=null) tree.offer(temp.left); if(temp.right!=null) tree.offer(temp.right); result.add(temp.val); return result; package offer; /请实现一个函数，将一个字符串中的空格替换成“%20”。 /例如，当字符串为We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。 public class ReplaceSpace public String replaceSpace(StringBuffer str) String sti = str.toString(); char strChar = sti.toCharArray(); StringBuffer stb = new StringBuffer(); for(int i=0;i2-3-pre head-next=null; while(nextNode!=null) head.next = preNode; preNode =head; head = nextNode; nextNode = nextNode.next; head.next = preNode; return head; package offer; /用两个栈来实现一个队列，完成队列的Push 和Pop操作。 队列中的元素为int 类型。 public class Singleton /设置构造函数私有 private Singleton() /设置该类的实例 private static Singleton instance; /设置获取实例的方法 public static Singleton getInstance() /双验证模式 if(instance=null) synchronized(Singleton.class) if(instance=null) instance = new Singleton(); return instance; package offer; import java.util.Stack; /用两个栈来实现一个队列，完成队列的Push 和Pop操作。 队列中的元素为int 类型。 public class StackToQueue Stack stack1 = new Stack(); Stack stack2 = new Stack(); /放入第一个栈 public void push(int node) stack1.push(node); /从第二个栈出 publi