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

. .

面试题3：二维数组中的查找P38

public class Solution {

public boolean Find(int [][] array,int target) { int m = 0;//行

int i = array.length-1;//列

while(m < array[0].length && i>=0){

if(array[m][i] > target)//与左上的元素相比较 i--;

else if(array[m][i] < target) m++; else

return true; }

return false; } }

面试题4：替换空格P44

public class Solution {

public String replaceSpace(StringBuffer str) { char a[]=new char[str.length()]; for(int i=0;i

a[i]=str.charAt(i); }

StringBuffer ss = new StringBuffer(); for(int i=0;i

if(a[i]==' ') {

ss.append(\ } else {

ss.append(a[i]); } }

String s = ss.toString(); // System.out.println(s); return s; } }

页脚

. .

面试题5：输入一个链表，从尾到头打印链表每个节点的值。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 printListFromTailToHead(ListNode listNode) {

Stack stack = new Stack();

ArrayList list=new ArrayList();//新生成的从后到前的链 ListNode current=listNode; while(current!=null){ stack.push(current); current=current.next; }

while(!stack.isEmpty()){

list.add(new Integer(stack.pop().val)); }

return 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); 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(pre[startPre]);

for(int i=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); } return root; } }

面试题7：用两个栈实现队列P59

import java.util.Stack;

public class Solution {

Stack stack1 = new Stack(); Stack stack2 = new Stack();

public void push(int node) {

stack1.push(new Integer(node)); }

public int pop() {

while(!stack2.isEmpty()) {

return stack2.pop(); }

页脚