劍指offer例題(Java編程通過)參考模板

1、面試題3：二維數(shù)組中的查找P38public class Solution public boolean Find(int array,int target) int m = 0;/行 int i = array.length-1;/列 while(m < array0.length && i>=0) if(arraymi > target)/與左上的元素相比較 i-; else if(arraymi < target) m+; else return true; return false; 面試題4：替換空格P44public class Soluti

2、on public String replaceSpace(StringBuffer str) char a=new charstr.length(); for(int i=0;i<str.length();i+) ai=str.charAt(i); StringBuffer ss = new StringBuffer(); for(int i=0;i<a.length;i+) if(ai=' ') ss.append("%20"); else ss.append(ai); String s = ss.toString(); /System.ou

3、t.println(s); return s; 1 / 34面試題5：輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。P51/* * public class ListNode * int val;* ListNode next = null;* ListNode(int val) * this.val = val;* * */import java.util.ArrayList;import java.util.Stack;public class Solution public ArrayList<Integer> printListFromTailToHead(ListNode

4、listNode) Stack<ListNode> stack = new Stack<ListNode>(); ArrayList<Integer> list=new ArrayList<Integer>();/新生成的從后到前的鏈 ListNode current=listNode; while(current!=null) stack.push(current); current=current.next; while(!stack.isEmpty() list.add(new Integer(stack.pop().val); retur

5、n list; 面試題6：重建二叉樹/* * Definition for binary tree * public class TreeNode * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) val = x; * */public class Solution public TreeNode reConstructBinaryTree(int pre,int in) /pre前序 in中序 TreeNode root=reConstruct(pre,0,pre.length-1,in,0,in.length-1

6、); return root; /前序遍歷1,2,4,7,3,5,6,8和中序遍歷序列4,7,2,1,5,3,8,6 private TreeNode reConstruct(int pre,int startPre,int endPre,int in,int startIn,int endIn) if(startPre>endPre|startIn>endIn) return null; TreeNode root=new TreeNode(prestartPre); for(int i=startIn;i<=endIn;i+) if(ini=prestartPre) ro

7、ot.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); return root; 面試題7：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列P59import java.util.Stack;public class Solution Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2

8、 = new Stack<Integer>(); public void push(int node) stack1.push(new Integer(node); public int pop() while(!stack2.isEmpty() return stack2.pop(); while(!stack1.isEmpty() stack2.push(stack1.pop(); return stack2.pop(); 面試題8：旋轉(zhuǎn)數(shù)組的最小數(shù)字import java.util.ArrayList;public class Solution public int minN

9、umberInRotateArray(int array) if (array.length = 0) return 0; int left=0; int right=array.length-1; int mid = left; if(arrayleft<arrayright) return arrayleft; while(arrayleft>=arrayright) if(right-left =1) mid=left; break; mid=(left+right)/2; if(arraymid>=arrayleft) left=mid; else if (array

10、mid<=arrayleft) right=mid; return arraymid; 面試題9：斐波那契數(shù)列public class Solution public int Fibonacci(int n) /非遞歸解法 int array=0,1; if (n<=0) return 0; if (n<2) return arrayn; int left = 0; int right = 1; int fib = 0; for(int i=1;i<n;i+) fib = left+right; left=right; right = fib; return fib;

11、面試題10：二進(jìn)制中1的個(gè)數(shù)面試題11：數(shù)值的整數(shù)次方public class Solution public double Power(double base , int exp) int absexp=0; if(base=0.0&&exp<0) return 0.0;/底數(shù)為零指數(shù)小于零的情況 if (exp<0) absexp=(-1)*exp; else absexp=exp; double result = Pow(base,absexp); if(exp<0) result = 1.0/result; return result; double

12、Pow(double base,int absexp) double re = 1.0; for(int i=1;i<=absexp;i+) re *= base; return re; 面試題12：打印1到最大的n位數(shù)面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面/運(yùn)行時(shí)間超時(shí)public void reOrderArray(int array) int i = 0; int temp = 0; while(i<array.length) if(arrayi%2=0) temp = arrayi; arrayi=arrayi+1; arrayarray.length-1=temp;

13、i-; i+; 面試題15：鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)/*public class ListNode int val; ListNode next = null; ListNode(int val) this.val = val; */public class Solution public ListNode FindKthToTail(ListNode head,int k) if(head=null|k<=0)/魯棒性 return null; ListNode pre=head; ListNode last=head; for(int i=1;i<k;i+) if(pre.next

14、!=null)/魯棒性 pre=pre.next; else return null; while(pre.next!=null) pre = pre.next; last = last.next; return last; 面試題16：反轉(zhuǎn)鏈表/*public class ListNode int val; ListNode next = null; ListNode(int val) this.val = val; */public class Solution public ListNode ReverseList(ListNode head) if (head = null) retu

15、rn null; if (head.next = null) return head; ListNode pPre = null; ListNode p = head; ListNode pNext = head.next; ListNode newHead = null; while (p != null) pNext = p.next;/一定要記錄下來后面的節(jié)點(diǎn) if (pNext = null) newHead = p; p.next = pPre;/這里的方向已經(jīng)轉(zhuǎn)變 pPre = p;/向后走了一位 p = pNext; return newHead; 面試題17：合并兩個(gè)排序列表/

16、*public class ListNode int val; ListNode next = null; ListNode(int val) this.val = val; */public class Solution public ListNode Merge(ListNode list1,ListNode list2) if (list1 = null&&list2=null) return null; else if (list1=null) return list2; else if (list2=null) return list1; /前四行考慮魯棒性 List

17、Node newHead = null; ListNode p = list1; ListNode q = list2; ListNode temp = newHead; while(p!=null&&q!=null) if(p.val<=q.val) if(newHead=null) newHead=temp=p; else temp.next=p; temp=temp.next; p=p.next; else if(newHead=null) newHead=temp=q; else temp.next=q; temp=temp.next; q=q.next; if(

18、p=null) temp.next=q; if(q=null) temp.next=p; return newHead; 面試題18：樹的子結(jié)構(gòu)/*public class TreeNode int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) this.val = val; */public class Solution public boolean HasSubtree(TreeNode root1,TreeNode root2) if(root2=null) return fa

19、lse; if(root1=null && root2!=null) return false; boolean flag = false; if(root1.val=root2.val) flag = DoesTree1HaveTree2(root1,root2); if(!flag) flag = HasSubtree(root1.left, root2); if(!flag) flag = HasSubtree(root1.right, root2); return flag; boolean DoesTree1HaveTree2(TreeNode p1,TreeNode

20、 p2) if(p2=null) return true; if(p1=null) return false; if(p1.val!=p2.val) return false; return DoesTree1HaveTree2(p1.left,p2.left)&&DoesTree1HaveTree2(p1.right,p2.right); 面試題19：二叉樹的鏡像/*public class TreeNode int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) t

21、his.val = val; */public class Solution public void Mirror(TreeNode root) if(root=null) return ; if(root.left=null&&root.right=null) return; TreeNode temp = null; temp = root.left; root.left = root.right; root.right = temp; if(root.left!=null) Mirror(root.left); if(root.right!=null) Mirror(ro

22、ot.right); 面試題21：包含min函數(shù)的棧import java.util.Stack;public class Solution Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> minStack = new Stack<Integer>(); int min ; public void push(int node) stack.push(node); if(minStack.isEmpty() minStack.push(node); else min = min

23、Stack.peek(); min = node < min ? minStack.push(node) : minStack.push(min); public void pop() if(!stack.isEmpty() && !minStack.isEmpty() stack.pop(); minStack.pop(); public int top() return stack.peek();/peek 查看棧頂對象而不移除 public int min() return minStack.peek(); 面試題22：棧的壓入彈出序列/*思路：先循環(huán)將pushA中

24、的元素入棧，遍歷的過程中檢索popA可以pop的元素*如果循環(huán)結(jié)束后棧還不空，則說明該序列不是pop序列。*/import java.util.ArrayList;import java.util.Stack;public class Solution public boolean IsPopOrder(int pushA,intpopA) Stack stack = new Stack(); if( pushA.length= 0 && popA.length= 0 ) return false; for( int i=0,j=0; i < pushA.length;

25、i+ ) stack.push( pushAi ); while( ( !stack.empty() )&& ( stack.peek() = popAj ) ) stack.pop(); j +; return stack.empty() = true; 面試題23：從上往下打印二叉樹import java.util.*;/*<樹的層序遍歷>java中隊(duì)列queue的使用：add 增加一個(gè)元索 如果隊(duì)列已滿，則拋出一個(gè)IIIegaISlabEepeplian異常remove 移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementExcepti

26、on異常element 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常offer 添加一個(gè)元素并返回true 如果隊(duì)列已滿，則返回falsepoll 移除并返問隊(duì)列頭部的元素 如果隊(duì)列為空，則返回nullpeek 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則返回nullput 添加一個(gè)元素 如果隊(duì)列滿，則阻塞take 移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則阻塞*/public class Solution public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) ArrayL

27、ist<Integer> list = new ArrayList<Integer>(); /list 存放輸出序列 if(root=null) return list; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty() TreeNode treeNode = queue.poll(); if (treeNode.left != null) queue.offer(treeNode.left); if (tr

28、eeNode.right != null) queue.offer(treeNode.right); list.add(treeNode.val); return list; 面試題24：二叉搜索樹后序遍歷序列import java.util.*;public class Solution public boolean VerifySquenceOfBST(int sequence) if(sequence =null|sequence.length=0) return false; int root = sequencesequence.length-1; int i =0; for(i=0

29、;i<sequence.length-1;i+) if(sequencei>root) break; for(int j=i;j<sequence.length-1;j+) if(sequencej<root) return false; boolean left=true; boolean right=true; if(i>0) left=VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i); if(i<sequence.length-1) right=VerifySquenceOfBST(Arrays

30、.copyOfRange(sequence, i, sequence.length-1); return (left&&right); /* System.arraycopy(src, 2, dest, 5, 1);/從src中的第2個(gè)位置到dest的第5個(gè)位置;總數(shù)為1個(gè)dest=Arrays.copyOfRange(src, 2, 4);/從src中的第2個(gè)位置到第4個(gè)位置;總數(shù)為2個(gè) */ 面試題25：二叉樹中和為某一值的路徑import java.util.*;/* 算法思路:（1）采用深度優(yōu)先算法，利用棧結(jié)構(gòu)存儲(chǔ)訪問過的路徑結(jié)點(diǎn)的值。 （2）當(dāng)訪問到空節(jié)點(diǎn)時(shí)，直接re

31、turn 。 （3）當(dāng)訪問到葉子結(jié)點(diǎn)時(shí)，判斷走過的路徑的值之和是否為target，如果是，則保存此路徑，否則不處理。 （4）先訪問左子樹，后訪問右子樹。 （5）在訪問完某個(gè)結(jié)點(diǎn)的左右子樹時(shí)，需要將此結(jié)點(diǎn)的值出棧。*/public class Solution public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) ArrayList<ArrayList<Integer>> lis = new ArrayList<ArrayList<Integer&

32、gt;>(); Stack<Integer> stack = new Stack<Integer>(); dfs(lis,root,stack,target); return lis; /深度優(yōu)先 public void dfs (ArrayList<ArrayList<Integer>> list, TreeNode root, Stack<Integer> stack, int target) if(root = null) return ; if(root.left = null && root.right

33、 = null) /如果是葉子節(jié)點(diǎn) if(target = root.val) Iterator<Integer> iter = stack.iterator(); /棧的迭代器 ArrayList<Integer> tmp = new ArrayList<Integer>(); while(iter.hasNext() tmp.add(iter.next(); /如果滿足條件就將這條路徑保存下來 tmp.add(root.val); list.add(tmp); return ; /不是葉子節(jié)點(diǎn)就入棧 stack.push(root.val); /遞歸左右

34、子樹 dfs(list,root.left,stack,target-root.val); dfs(list,root.right,stack,target-root.val); /返回到該節(jié)點(diǎn)的父節(jié)點(diǎn)處 stack.pop(); 面試題26：復(fù)雜鏈表的復(fù)制（分步法）import java.util.*;/*public class RandomListNode 分步解決法：int label;RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) this.label = labe

35、l; 1.根據(jù)原始鏈表的每個(gè)節(jié)點(diǎn)N創(chuàng)建對應(yīng)的N，我們將N鏈在N的后面。2.設(shè)置復(fù)制出來的random,N是N的next指向的節(jié)點(diǎn)，那么S'也是S的next指向的結(jié)點(diǎn)3.拆分這個(gè)鏈表：奇數(shù)位置是原有的鏈表，偶數(shù)位置是復(fù)制出來的鏈表。*/public class Solution public RandomListNode Clone(RandomListNode pHead) CloneNodes(pHead); ConnectRandom(pHead); return (Reconnect(pHead); void CloneNodes(RandomListNode pHead) Ra

36、ndomListNode pNode = pHead; while(pNode != null) RandomListNode pCloned = new RandomListNode(0); pCloned.next = pNode.next; pCloned.label = pNode.label; pCloned.random = null; pNode.next = pCloned; pNode = pCloned.next; void ConnectRandom(RandomListNode pHead) RandomListNode pNode = pHead; while(pNo

37、de!=null) RandomListNode pCloned = pNode.next; if(pNode.random!=null) pCloned.random = pNode.random.next; /是原始random節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) pNode = pCloned.next; RandomListNode Reconnect(RandomListNode pHead) RandomListNode pNode = pHead; RandomListNode pClonedHead = null; RandomListNode pClonedNode = null; if(pNo

38、de != null)/處理頭節(jié)點(diǎn) pClonedHead = pClonedNode = pNode.next; pNode.next = pClonedNode.next; pNode = pNode.next; /pNode向后走一位 while(pNode != null) pClonedNode.next = pNode.next; pClonedNode = pClonedNode.next; pNode.next = pClonedNode.next; pNode = pNode.next; return pClonedHead; 面試題27：二叉搜索樹與雙向鏈表非遞歸：/*public class TreeNode int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) this.val = val; 方法一：非遞歸版解題思路：1.核心是中序遍歷的非遞歸算法。2.