剑指offer例题(Java编程通过)

面试题3：二维数组中的查找P38publicclassSolution{publicbooleanFind(int[][]array,inttarget){intm=0;//行inti=array.length-1;//列while(marray[0].length&&i=0){if(array[m][i]target)//与左上的元素相比较i--;elseif(array[m][i]target)m++;elsereturntrue;}returnfalse;}}面试题4：替换空格P44publicclassSolution{publicStringreplaceSpace(StringBufferstr){chara[]=newchar[str.length()];for(inti=0;istr.length();i++){a[i]=str.charAt(i);}StringBufferss=newStringBuffer();for(inti=0;ia.length;i++){if(a[i]==''){ss.append(%20);}else{ss.append(a[i]);}}Strings=ss.toString();//System.out.println(s);returns;}}面试题5：输入一个链表，从尾到头打印链表每个节点的值。P51/***publicclassListNode{*intval;*ListNodenext=null;**ListNode(intval){*this.val=val;*}*}**/importjava.util.ArrayList;importjava.util.Stack;publicclassSolution{publicArrayListIntegerprintListFromTailToHead(ListNodelistNode){StackListNodestack=newStackListNode();ArrayListIntegerlist=newArrayListInteger();//新生成的从后到前的链ListNodecurrent=listNode;while(current!=null){stack.push(current);current=current.next;}while(!stack.isEmpty()){list.add(newInteger(stack.pop().val));}returnlist;}}面试题6：重建二叉树/***Definitionforbinarytree*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(intx){val=x;}*}*/publicclassSolution{publicTreeNodereConstructBinaryTree(int[]pre,int[]in){//pre前序in中序TreeNoderoot=reConstruct(pre,0,pre.length-1,in,0,in.length-1);returnroot;}//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}privateTreeNodereConstruct(int[]pre,intstartPre,intendPre,int[]in,intstartIn,intendIn){if(startPreendPre||startInendIn)returnnull;TreeNoderoot=newTreeNode(pre[startPre]);//最好把迭代写在循环外for(inti=startIn;i=endIn;i++)if(in[i]==pre[startPre]){root.left=reConstruct(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);root.right=reConstruct(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);}returnroot;}}面试题7：用两个栈实现队列P59importjava.util.Stack;publicclassSolution{StackIntegerstack1=newStackInteger();StackIntegerstack2=newStackInteger();publicvoidpush(intnode){stack1.push(newInteger(node));}publicintpop(){while(!stack2.isEmpty()){returnstack2.pop();}while(!stack1.isEmpty()){stack2.push(stack1.pop());}returnstack2.pop();}}面试题8：旋转数组的最小数字importjava.util.ArrayList;publicclassSolution{publicintminNumberInRotateArray(int[]array){if(array.length==0)return0;intleft=0;intright=array.length-1;intmid=left;if(array[left]array[right]){returnarray[left];}while(array[left]=array[right]){if(right-left==1){mid=left;break;}mid=(left+right)/2;if(array[mid]=array[left])left=mid;elseif(array[mid]=array[left])right=mid;}returnarray[mid];}}面试题9：斐波那契数列publicclassSolution{publicintFibonacci(intn){//非递归解法int[]array={0,1};if(n=0)return0;if(n2)returnarray[n];intleft=0;intright=1;intfib=0;for(inti=1;in;i++){fib=left+right;left=right;right=fib;}returnfib;}}Log(n)的解法：importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;importjava.util.Stack;publicclassMain{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannersc=newScanner(System.in);longn=sc.nextLong();if(n==0){System.out.println(0);}elseif(n==1){System.out.println(1);}else{long[][]a={{1,1},{1,0}};System.out.println(fibonacci(n,a)[0][0]);}}publicstaticlong[][]fibonacci(longn,long[][]a){if(n==2)returna;if(n==3)returnmatrixMultiply(a,a);if(n%2==0){long[][]b=matrixMultiply(fibonacci((n-2)/2+1,a),fibonacci((n-2)/2+1,a));returnmatrixMultiply(b,a);}else{returnmatrixMultiply(fibonacci((n-1)/2+1,a),fibonacci((n-1)/2+1,a));}}publicstaticlong[][]matrixMultiply(long[][]a,long[][]b){longc[][]=newlong[a.length][b[0].length];intx,i,j;for(i=0;ia.length;i++){for(j=0;jb[0].length;j++){longtemp=0;for(x=0;xb.length;x++){temp+=a[i][x]*b[x][j];}c[i][j]=temp;}}returnc;}}面试题10：二进制中1的个数publicclassMain{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubSystem.out.println(numberOf1(7));}publicstaticintnumberOf1(intn){intcount=0;while(n!=0){if((n&1)!=0)count++;n=n1;}returncount;}}更好的方法publicclassMain{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubSystem.out.println(numberOf1(7));}publicstaticintnumberOf1(intn){intcount=0;while(n!=0){++count;n=(n-1)&n;}returncount;}}面试题11：数值的整数次方此题应该加个全局变量标志是否出现底数为零指数小于零的错误情况publicclassSolution{publicdoublePower(doublebase,intexp){intabsexp=0;if(base==0.0&&exp0)return0.0;//底数为零指数小于零的情况if(exp0)absexp=(-1)*exp;elseabsexp=exp;doubleresult=Pow(base,absexp);if(exp0)result=1.0/result;returnresult;}doublePow(doublebase,intabsexp){doublere=1.0;for(inti=1;i=absexp;i++){re*=base;}returnre;}}面试题12：打印1到最大的n位数方案1：模拟整数的加法importjava.util.Arrays;publicclassTest{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubprintToMaxOfNDigits(2);}publicstaticvoidprintToMaxOfNDigits(intn){if(n=0)return;char[]number=newchar[n];Arrays.fill(number,'0');while(!Increment(number)){printNumber(number);System.out.println();}}publicstaticbooleanIncrement(char[]number){booleanisOverFlow=false;intnTakeOver=0;intnSum;intnLength=number.length;for(inti=nLength-1;i=0;i--){nSum=number[i]-'0'+nTakeOver;if(i==nLength-1){nSum++;}if(nSum=10){if(i==0){isO