剑指offer面试题 java解答36-40

面试题36:数组中的逆序对

public class Test36 { private static <T extends Comparable<? super T>> int merge(T[] a,T[] tmp,int leftPos,int rightPos,int rightEnd) { int leftEnd=rightPos-1; int tmpPos=rightEnd; int numEles=rightEnd-leftPos+1; int count=0; while (leftPos<=leftEnd&&rightPos<=rightEnd) { if (a[leftEnd].compareTo(a[rightEnd])<=0) { tmp[tmpPos--]=a[rightEnd--]; }else { tmp[tmpPos--]=a[leftEnd--]; count+=rightEnd-rightPos+1; } } while (leftPos<=leftEnd) { tmp[tmpPos--]=a[leftEnd--]; } while (rightPos<=rightEnd) { tmp[tmpPos--]=a[rightEnd--]; } for (int i = 0; i < numEles; i++,leftPos++) { a[leftPos]=tmp[leftPos]; } return count; } private static <T extends Comparable<? super T>> int InversePairesCore(T[] a,T[] tmp,int left,int right) { int left_count=0; int right_count=0; int count=0; if (left<right) { int center=(left+right)/2; left_count=InversePairesCore(a, tmp, left, center); right_count=InversePairesCore(a, tmp,center+1, right); count=merge(a, tmp, left, center+1, right); } return left_count+right_count+count; } public <T extends Comparable<? super T>>int InversePaires(T[] data) throws Exception{ if (data==null||data.length<=0) { throw new Exception("invalid input"); } T[] tmp=(T[]) new Comparable[data.length]; int count=InversePairesCore(data, tmp, 0, data.length-1); return count; } public static void main(String[] args) throws Exception { Integer[] data={7,5,6,4}; Test36 t=new Test36(); int count=t.InversePaires(data); System.out.println(count); } }

面试题37:两个链表的第一个公共结点

public class Test37 { private class Node<T>{ private T obj; private Node<T> next = null; Node(T obj) { this.obj = obj; } } private Node firstOne = null; private Node firstTwo = null; public Node getHeadOne(){ return firstOne; } public Node getHeadTwo(){ return firstTwo; } public <T> Node insertFirstOne(T obj){ Node node = new Node(obj); node.next = firstOne; firstOne = node; return node; } public <T> void insertFirstTwo(T obj){ Node node = new Node(obj); node.next = firstTwo; firstTwo = node; } private int GetListLength(Node head){ int length=0; Node node=head; while (node!=null) { length++; node=node.next; } return length; } public Node FindFirstCommonNode(Node headOne,Node headTwo){ int nlength1=GetListLength(headOne); int nlength2=GetListLength(headTwo); int nlengthDif=nlength1-nlength2; Node listHeadLong=headOne; Node listHeadShort=headTwo; if (nlength2>nlength1) { nlengthDif=nlength2-nlength1; listHeadLong=headTwo; listHeadShort=headOne; } for (int i = 0; i < nlengthDif; i++) { listHeadLong=listHeadLong.next; } while (listHeadLong!=null&&listHeadShort!=null&&listHeadLong!=listHeadShort) { listHeadLong=listHeadLong.next; listHeadShort=listHeadShort.next; } Node firstCommonNode=listHeadLong; return firstCommonNode; } public static void main(String[] args) throws Exception { int[] a={9,7,5,3,1}; int[] b={6,4,2}; Test37 t=new Test37(); Node crossNode=null; for (int i = 0; i < a.length; i++) { if (i==1) { crossNode=t.insertFirstOne(a[i]);//头插法 }else { t.insertFirstOne(a[i]); } } //链表为1->3->5->7->9 for (int i = 0; i < b.length; i++) { t.insertFirstTwo(b[i]);//头插法 } //链表为2->4->6 Node tailNode=t.getHeadTwo(); while (tailNode.next!=null) { tailNode=tailNode.next; } tailNode.next=crossNode; //链表为 1->3->5-> // ->7->9 // 2->4->6-> Node firstCommonNode=t.FindFirstCommonNode(t.getHeadOne(), t.getHeadTwo()); System.out.println(firstCommonNode.obj); } }

面试题38:数字在排序数组中出现的次数

public class Test38 { private int GetFirstK(int[] data,int k,int start,int end){ if (start>end) { return -1; } int middleIndex=(start+end)/2; int middleData=data[middleIndex]; if (middleData==k) { if ((middleIndex>0&&data[middleIndex-1]!=k)||middleIndex==0) { return middleIndex; }else { end=middleIndex-1; } }else if(middleData>k) { end=middleIndex-1; }else { start=middleIndex+1; } return GetFirstK(data, k, start, end); } private int GetLastK(int[] data,int k,int start,int end){ if (start>end) { return -1; } int length=data.length; int middleIndex=(start+end)/2; int middleData=data[middleIndex]; if (middleData==k) { if ((middleIndex<length-1&&data[middleIndex+1]!=k)||middleIndex==length-1) { return middleIndex; }else { start=middleIndex+1; } }else if(middleData>k) { end=middleIndex-1; }else { start=middleIndex+1; } return GetLastK(data, k, start, end); } public int getNumberOfK(int[] data,int k) { int number=0; if (data!=null&&data.length>0) { int first=GetFirstK(data, k, 0, data.length-1); int last=GetLastK(data, k, 0, data.length-1); if (first>-1&&last>-1) { number=last-first+1; } } return number; } public static void main(String[] args) { int[] data={1,2,3,3,3,3,4,5}; Test38 t =new Test38(); int number=t.getNumberOfK(data, 3); System.out.println(number); } }

面试题39：二叉树的深度

public class Test39<T>{ private class Node<T> { public T value; public Node<T> lChild; public Node<T> rChild; public Node(T value) { this.value = value; } } private class Depth { public int height; } public Node<T> root=null; private int pos = 0; public void creatBiTree(T[] value){ pos=0; root=creatBiTree(root, value); } // 以node为根节点，创建一棵树，返回此根节点 private Node<T> creatBiTree(Node node, T[] value) { T t = value[pos]; pos++; if (t == null) { return null; } else { node = new Node<T>(t); node.lChild = creatBiTree(node.lChild, value); node.rChild = creatBiTree(node.rChild, value); } return node; } public int TreeDepth(Node<T> root){ if (root==null) { return 0; } int nleft=TreeDepth(root.lChild); int nright=TreeDepth(root.rChild); return (nleft>nright)?(nleft+1):(nright+1); } //参数中携带信息 需要用对象类 不能用基本类型 c中可以用指针修改 private boolean IsBalanced(Node<T> root,Depth pDepth) { if (root==null) { pDepth.height=0; return true; } Depth left=new Depth(); Depth right=new Depth(); if (IsBalanced(root.lChild, left)&&IsBalanced(root.rChild, right)) { int diff=left.height-right.height; if (diff<=1&&diff>=-1) { pDepth.height=1+(left.height>right.height?left.height:right.height); return true; } } return false; } public boolean IsBalanced(Node<T> root){ Depth depth=new Depth(); return IsBalanced(root, depth); } public static void main(String[] args) { Object[] a = { 1, 2, 4, null, null,5,7,null,null,null, 3, null,6,null, null}; Test39 t = new Test39(); t.creatBiTree(a); int depth=t.TreeDepth(t.root); boolean isBalanced=t.IsBalanced(t.root); System.out.println(depth); System.out.println(isBalanced); } }

面试题40:数组中只出现一次的数字

public class Test40 { private class Number{ int intValue; } private Number number; public void FindNumsAppearOnce(int[] data,Number num1,Number num2){ if (data==null||data.length<2) { return; } int resultExclusiveOR=0; for (int i = 0; i < data.length; i++) { resultExclusiveOR^=data[i]; } int indexOf1=FindFirstBitIs1(resultExclusiveOR); num1.intValue=0; num2.intValue=0; for (int i = 0; i < data.length; i++) { if (IsBit1(data[i], indexOf1)>0) { num1.intValue^=data[i]; }else { num2.intValue^=data[i]; } } } private int FindFirstBitIs1(int num) { int indexBit=0; while (((num&1)==0)&&(indexBit<Integer.SIZE)) { num=num>>1; indexBit++; } return indexBit; } private int IsBit1(int num,int indexBit){ num=num>>indexBit; return (num&1); } public static void main(String[] args) { int[] data={2,4,3,6,3,2,5,5}; Test40 t=new Test40(); //假设外部类叫Out，内部类叫In，那么我们可以使用Out.In in = new Out().new In()来实例化内部类的对象 Test40.Number num1=t.new Number(); Test40.Number num2=t.new Number(); t.FindNumsAppearOnce(data, num1, num2); System.err.println(num1.intValue+","+num2.intValue); } }