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

1、精选文库面试题3:二维数组中的查找P38public class Solution public boolean Find(int arrayjnt target) int m = 0;/行int i = arrayJength-1; 列 while(m =0) if(arraymi target)/左上的元素相比较 i-Selse if(arraymi target)m+;elsereturn true;return false;面试题4:替换空格P44public class Solution public String repiaceSpace(StnngBuffQr str) char

2、 a=new charstrJength();forfint i=O;istrJength();i+)ai=strxharAti);StringBuffer ss = new StnngBuffer()j forfint i=O;iaJength;i+)if(ai=3ss.append(%20)：elsess.a pp end(ai);String s = ss.toStringO； / System.out. pnntln(s);return s;面试题5:输入一个链表，从尾到头打印链表每个节点的值。P51 /* public class ListNode * int val;* ListN

3、ode next = null;ListNode(int val) this.val = val;/imp Ort java.utiLArrayList; import java.utikStack;public class Solution public ArrayList printListFromTailToHeadListNode listNode) Stack stack = new Stack();ArrayList list=new ArrayLisKintQgQr();/新生成的从后到前的链 ListNode current=listNode;while(current!=nu

4、ll)stack, push(current);current=current.next;while(!stackjsEm pty()list.addfnew Integer(stack. pop ()val);return list;面试题6:重建二叉树* Definition for binary tree* public class TreeNode * int val;* TreeNode left;* TreeNode right：* TreeNodefint x) val = x; public class Solution public TreeNode reConstructB

5、inaryTree(int prejnt in) /pre前序 in中序TreeNode root=reConstruct( pr巳O，prQlQngth-ljrbOnength-1); return root;前序遍历124,73568和中序遍历序列4/2丄538,6Private TreeNode reConstructfint prejnt startPrejnt endPrejnt in,int startinjnt endIn)ifstartPreendPre| |startlnendln) return null;TreeNode root=new TreeNode(prestar

6、tPre);forfint i=startln;i=endln;i+)if(iniJ=prestartPre)rootJeft=reConstruct(pre,startPre+l,start Pr+istartlnjmstartlrbi：L);root.right=reConstruct( pr ej-startin+start Pr e+l,end PrQmi+l，endln);return root;面试题7:用两个栈实现队列P59 import java.utikStack;public class Solution Stack stackl = new Stack);Stack st

7、ack? = new Stack();public void push(int node) stackl. push(new integer(node);public int pop() while(!stack2jsErn pty()return stack?.pop();while(!stackljsEm pty()stack2.push(stackl. pop();retur n stack?. pop();面试题8:旋转数组的最小数字import java.util.ArrayList;public class Solution public int minNumberlnRotate

8、Array(int array) if (array.length = 0)return 0;int left=O;int right=arrayJength-l;int mid = left;ifarrayleftj=arrayright)if( right-left =1)mid=left： break;mid=(left+nght)/2;if(arraymid=array(le1tj) left=mid;else if array(midj=arrayleft)right=mid;return arraymid;面试题9:斐波那契数列public class Solution p ubl

9、ic I nt Fibon accifint n)非递归解法 int array=0,l; if (n=0) return 0; if (n2) return arrayfn; int left =0;int right = 1;intfib = O;forfint i=l;in;i+)fib = bft 十 right; left=right; right = fib;return fib;面试题10:二进制中1的个数面试题数值的整数次方Public class Solution public double Powerdouble base, int exp)int absex p=0;if

10、base=0.0&exp0)return 0.0;/J数为零指数小于零的情况if (exp0) absexp=(-l)*exp; else absex p=exp;double result = Powfbaseabsexp); ifexp0) result = 1.0/result; return result;double Pow(double basejnt absexp)double re = 1.0; forfint i=l;i=absexp;i+)re *= base;return re;面试题22:打印1到最大的n位数面试题24:调整数组顺序使奇数位于偶数前面/运行时间超时Pub

11、lic void reOrderArrayfint array)int i = 0;int temp = 0;while(iarrayJength)if(arrayi%2=0)tem p = arrayi; arrayi=arrayi+l; array(arrayJength-l=tem p; i；卄；面试题15:链表中倒数第k个结点 /*Public class ListNode int val;ListNode next = null;ListNodeint val) this.val = val;/public class Solution public ListNode FindKth

12、ToTail(ListNode head,!nt k)ifhead=null| |1=0)鲁棒性return null;ListNode pre=head;ListNode last=head;forfint i=l;ik;i+)if(p re.next!=null)/ra* 棒性prop re.next; etsereturn null;while( prenext!=null)pre = p re. next; last = lastmext;return last;面试题16:反转链表 /*public class ListNode int val;ListNode next = nul

13、l;ListNodeint val) this.val = val;/public class Solutionpublic ListNode ReverseList(ListNode head)if (head = null) return null;if (head.next = null) return head;ListNode pP = null;ListNode p = head;ListNode pNext = head.next;ListNode newHead = null;while (p != null) pNext = p.next;/立要记录下来后面的节点 if (p

14、Next = null)newHead = p;p.next = pPv;/这里的方向已经转变pPre = pj 向后走了一位 p = pN ext;return newHead;面试题17:合并两个排序列表 /*public class ListNode int val;ListNode next = null;ListNodeint val) this.val = val;/public class Solution public ListNode IVlerge(ListNode listl,ListNode Iist2) if (listl = null&list2=null)retu

15、rn null;else if (listl=null) return Iist2;else if (Iist2=null) return listl;前四行考虑鲁棒性ListNode newHead = null;ListNode p = listl;ListNode q = Iist2;ListNode tem p = newHead;while(p!=null&q!二null) if(p .val=q.val)ifnewHead=null) newHead=tem p=p; elsetemp.next=p; tern p=tem p.next;P=p.next;elseifnewHead

16、=null) newHead=temp=q; elsetemp.next=q; tern p=tem p.next;q=qnext;ifp=null)temp.next=q;ifq=null)tempnext=p;return newHead;面试题18:树的子结构 /*public class TreeNode int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) this.val = val;/public class SolutionPublic boolean HasSubtree

17、(TreeNode rootlJreeNode root?)ifroot2=null) return false; ifrootl=null & root2!=null) return false;boolean flag = false;ifrootl.val=root2.val)flag = DoesTreelHaveTree2(rootl,root2)jflag = HasSubtreefrootlJeft, root2); if(!flag)flag = HasSubtreefrootl.right, root2);return flag;boolean DoesTreelHaveTr

18、ee2TreeNode plJreeNode p2)if(p2=null) return true; if(pl=null) return false; ifpl.val!=p2.val) return false;returnDoesTreelHaveTree2( plhftpZ.bft)&D OQsTrQQlHavQTrg2(plright，p2right);面试题19:二叉树的镜像 /*public class TreeNode int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val)

19、this.val = val;/ public class Solution public void IVlirror(TreeNode root)ifroot=null) return ;ifrootJeft=null&root.right=null) return;TreeNode ternp = null; tem p = root.left： root.left = root.right; root, right= temp;if(rootJeft!=null) Mirror(rootJeft); if(root.right!=null) Mirrorroot,right);面试题21

20、:包含min函数的栈 import java.util.Stack;public class SolutionStack stack = new Stack(); Stack minStack = new Stack(); int min;public void pushfint node)stack, push(node); ifminStackjsE mpty()min Stack, push(node); elsemin = minStack,peek();min = node min ? minStack.push(node): minStack.push(min);public vo

21、id pop() if!stackJsEmpty) & !minStackjsEmpty() stack.p op();minStack. pop();public int top() return stack.peek();/peek査看栈顶对象而不移除Public int min() return minStack.peek();面试题22:栈的压入弹出序列厂思路：先循环将pushA中的元素入栈，遍历的过程中检索popA可以pop的元素 “如果循环结束后栈还不空，则说明该序列不是pop序列。/imp ort java-utiLAgyList;impo rt java.utikStack;p

22、ublic class Solutionpublic boolean lsPopOrder(int pushA,int(popA)Stack stack = new Stackf);if pushAJength= 0 & popAJength= 0) return false; for int i=OJ=O; i pushA.Iength： i+ )stack.pushf pushAi);whilef ( !stack.empty) )& ( stack.peek) = popA|j) stack. pop();j+；return stack.empty() = true;面试题23:从上往下

23、打印二叉树 import Java.utik*;/*树的层序遍历java中队列queue的使用：增加一个元索add异常remove移除并返回队列头部的元素NoSuchElementException 异常如果队列已满，则抛出一个lllegalSlabEepeptian如果队列为空，则抛出一个element 返回队列头部的元素 NoSuchElementException 异常 offer poll p eek put take*/public class Solution如果队列为空，则抛出一个添加一个元素并返回trg移除并返问队列头部的元素返回队列头部的元素添加一个元素移除并返回队列头部的元

24、素如果队列已满，则返回false如果队列为空，则返回null 如果队列为空，则返回null 如果队列满，则阻塞如果队列为空，则阻塞Public ArrayList PrintFromTopTbBottomfTreeNode root)ArrayList list = new ArrayList(); /list存放输出序列 ifroot=null)return list;Queue queue = new LinkedList(); queue.offer(root);while (iqueueJsEmpty()TreeNode treeNode = queue.poll(); if tree

25、Node.left != null) queue.offer(treeNodeJeft);if treeNode.right != null) queue.offer(treeNode. right);li5Ladd(treeNode.val);return list;面试题24:二叉搜索树后序遍历序列 import Java.utik*;public class Solutionpublic boolean VerifySquenceOfBST(int sequence)iffsequenee =null| | sequenceJength=O) return false; int root

26、 = sequencesequenceJength-l;int i =0;fori=0;iroot) break;for(int J=i;jsequenceJength-l;j+)ifsequenceJroot) return false;boolean left=true;boolean nght=true;left=VerifySquenceOfBST(ArraysxopyC)fRangesequence, 0, i);ifisequenceJength-l)right=VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.

27、length-1);return (left&right);/System.arraycopy(src, 2, dest, 5,1);从src中的第2个位置到dest的第5个位置;总数为1个 dest=Arrays.copyOfRangesrc, 2, 4);从src中的第2个位置到第4个位置;总数为2个/面试题25:二叉树中和为某一值的路径import Java.utik*;严*算法思路：（1）采用深度优先算法，利用栈结构存储访问过的路径结点的值。（2）当访问到空节点时，宜接return。（3）当访问到叶子结点时，判断走过的路径的值之和是否为target.如果是，则保存此路 径，否则不处理。

28、（4）先访问左子树，后访问右子树。（5）在访问完某个结点的左右子树时，需要将此结点的值出栈。/public class Solution public ArrayListArrayListlnteger FindPathfTreeNode rootjnt target)ArrayListArrayListlnteger lis = new ArrayListArrayListlnteger); Stack stack = new Stack();dfs(lis,root,stack,target);return lis;深度优先public void dfs (ArrayListArrayLi

29、stlnteger list, TreeNode root, Stack stack, int target)iffroot = null)return;iffroot.left = null & root.right = null)如果是叶子节点if (target = root.val)lterator iter = stackJterator();栈的迭代器ArrayList tmp = new ArrayList0； while(iterhasNext()tmp add(iternext();如果满足条件就将这条路径保存下来tmp.add(root.val); list.addftm

30、p);return;不是叶子节点就入栈stack. push(rootval);/递归左右子树dfs(list,rootJeft,stack,target-root.val)j dfs(list,root, right,stack,target-root.val);返回到该节点的父节点处stack. pop();面试题26:复杂链表的复制(分步法) imp Ort java.util,*;/分步解决法:public class RandomListNode int label;RandomListNode next = null; RandomListNode random = null; R

31、andomListNode(int label) thisJabel = label;1根据原始链表的毎个节点N创建对应的N,我们将N链在N的后而。2设置复制岀来的random,N是N的next 向的节点，那么S也是S的next 向的结点3.拆分这个链表：奇数位置是原有的链表，偶数位置是复制出来的链表。/Public class SolutionPublic RandomListNode ClonefRandomListNode pHead)CloneNodes( pHead);Con nectRandom (p Head); return (Reconnect(pHead);void Clo

32、neNodesRandomListNode pHead)RandomListNode pNode = pHead; whilefpNode != null)RandomListNode pCloned = new RandomUstNode(O); p Cloned.next = pNode.next;pCIoned.label = pNodeJabel;p Cloned.random = null;pN ode.next = pCioned; pN ode = pCioned.next;void ConnectRandom(RandomListNode pHead)RandomListNod

33、e pNode = pHead; while( pN ode!=null)RandomListNode pCioned = pNode.next; if(pN odQ.randomknull)p Cloned.random = pN odQ.random.next;/是原始random节点的下一个节点pNode = p Cloned.next;RandomListNode Reconnect(RandomListNode pHead)RandomListNode pN ode = pHead;RandomListNode pCIonedHead = null;RandomListNode pC

34、IonedNode = null;iffpNode != null)/处理头节点p ClonedHead = p ClonedNode = p Node.next; pN ode. next = p ClonedNode.next;pN ode = pN ode.next;/pNode向后走一位while(pNode != null)p ClonedNode.next = pN ode. next; p ClonedNode = p ClonedNode.next： pN ode. next = p ClonedNode.next; pN ode = pN ode.next;return pC

35、ionedHead;面试题27:二叉搜索树与双向链表非递归：严*P ublic class TreeNode int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) this.val = val;方法一：非递归版解题思路：1核心是中序遍历的非递归算法。2.修改当前遍历节点与前一遍历节点的指针指向。/import java.utikStack;public class Solution public TreeNode Convert(TreeNode root)ifroot=null)retu

36、rn null;Stack stack = new Stack();TreeNode p = root;TreeNode pre = null;/用于保存中序遍历序列的上一节点 boolean isFirst = true;while(p!=null| |!stack.isEmpty() while(p!=null) stack, pu sh(p); p = p.left;p = stack. pop();if(isFirst)root = p;/将中序遍历序列中的第一个节点记为root pre = root;isFirst = false;elsepre.right = p;p.left =

37、 p re;py = P；P = P-right;return root;递归:面试题28:字符串的排列（全排列，按照字典序输出）该问题可以看成两步：1. 求所有可能出现在第一位的字符2. 固是第一个字符，求后面所有可能的排列递归思想/import Java.utik*;public class SolutionP ublic ArrayList P ermutation(Stnng str)ArrayList result = new ArrayList()j if (str = null 11 strJength)9 11 strJength()=O)return result;str =

38、 strthmO；/去掉空格就是字符串前后的空白Permutstr.toCharArray(), 0, result);HashSet hs = new HashSetresult); 用hashset去重，但并未按照字典序排列 ArrayList resultdic = new ArrayLisths);Collections.sortfresultdic);去重后的序列按照字典序排列return resultdic;void PermutcharI data, int beginldx,ArrayList result)if (beginldx = dataJength)/ 只剩一个字符的

39、时候result.add(new String(data);elsefor int i = beginldx; i dataJength;i+)ifi!=beginldx & ddtai=databeginldx) continue;char tem p = databeginldx; ddtabeginldx = datafi;datai = tem p;Permutfdata, beginldx + 1, result);为了防止重复的情况，还需要将begin处的元素重新换回来恢复打扫战场，恢复为原来子串，data共享tem P = databeginldx; databeginldx =

40、 datai; datai = temp;面试题29:数组中出现次数超过一半的数字Public class Solution public int IVloreThanHalfNum_Solutionint array)if (arrayJength =0) return 0; if (arrayJength =1) return arrayfO;quickSort(array, 0, arrayJength-1);int middle = arrayarray.lengthy2-l;boolean MoreThanHalf = ChecklVloreThanHalf(array,middle

41、); if MoreThanHalf=true) return arraymiddle;else return 0;private static void quickSort(int data, int low, int hight)int i=low,J=hight：int mid=data(low+hight);/中间的数 while(i = j) while(dataimid) j; if(ivj) int tem p = datai; ddtai = data。; data|j = temp; i+； if(ilow) quickSortdata, low, j);boolean Ch

42、ecklVloreThanHalf(int(array,int number)int times = 0; forfint i = O;jarrayJength-l;i+)if(arrayi=number) times+;boolean isMoreTha nHalf = true; if(times*2=arrayJength)isMoreThanHalf = false;return isMoreThanHalf;面试题30:最小的K个数 import java.util.*;public class Solution public ArrayList GetLeastNumbers_So

43、lutionint input, int k)ArrayList arr = new ArrayList(); ifk=O) return arr;if(inputJengthk) return arr;/ if(inputJength=k) return arr;quickSortinput,OJ nput.len gthl); forfint I = 0;ivk;i卄)drr.add(inputi);return arr;private static void quickSort(int data, int low, int hight)int i=low,J=hight;int mid=

44、data(low+hight);/中间的数 while(i = j) while(dataimid) j;if(ivj) int tem p = datai; ddtai = data。; ddta|j = tem p; i+；if(ivhight) quickSort(data, i, hight); if(jlow) quickSortfdata, low, j);面试题31:连续子数组的最大和public class Solution public int FindGreatestSumOfSubArrayint array)if (array.length=O) return 0;in

45、t sum = arrayOj; int savedsum = array0;for(int i = l;iarrayJength;i+)sum+=array(i; if(sum=savedsum) savedsum = sum;return savedsum;面试题32:从1到n的数字中1出现的次数巧妙算法：拼接分割汁算imp Ort java.util,*;public class Solution public int NumberOflBetweenlAndN_Solution(int n) if(n=O) return 0; if(n=l) return 1;StringBuffer

46、 temp = new StringBuffer()j forfint i=l;i=n;i+)temp.dppend(i);String temp2 =temp.toString().replacaAIICT, AAAI);String ts =temp2.splitl);int num = tsJength-1;return num;面试题34:丑数 imp Ort java.util,*;public class Solutionp ublic I nt GetUglyNumber_Solution(int index)ifindexl) arrl = 2; if(index2) arr2

47、 = 3; if(index3) arr3 = 4; if(index4) arr4 = 5; if(index5)for(int i = 5 ;i index; i +)int rnin2 = 0, min3 = 0, minS = 0; int tmp = 0;for(inti = 0;j arri-l) min2 = tmp; break;for(inti = 0;j arri-lj) min3 = tmp; break;for(intj = 0;j arri-l) minS = tmp; break;int min =Math.min(min2,min3); min = Math.mi

48、n(min,min5);arri = min;return arrindex-l：面试题35:第一个只出现一次的字符 import java.util.*;public class Solution空间换时间哈希表public int FirstNotRepeatingChar(String str)ifstrJength()=O) return -1;/char占一个字节，8位，最多表示256种字符 int hash=new int 256;forint i = 0;i strJength();i+)hashstr.charAti)+;for(int j = 0;j =len2)plong = p Headl; p short = p Head2; len = Ienl-len2;elsep long = p Head2; p short = p Headl; len = Ien2-lenl;forfint i =O;i-l&end-l)