面试题3：二维数组中的查找
题目描述：一个二维数组，每一行从左到右递增，每一列从上到下递增．输入一个二维数组和一个整数，判断数组中是否含有整数。

public class Find{
	public static boolean find(int[][] array,int number){
		if(array==null){
		return false;
		}
		int column=array[0].length-1;
		int row=0;
		while (row<array.length && column>=0){
		if(array[row][column]==number){
		return true;
		}
		if(array[row][column]>number){
		column--;
		}else{
		row++;
		}
		}
		return false;
	}
	public static void main(String args[]){
		int[][] testarray=new int[4][4];
		testarray[0][0]=1;
		testarray[0][1]=2;
		testarray[0][2]=8;
		testarray[0][3]=9;
		testarray[1][0]=2;
		testarray[1][1]=4;
		testarray[1][2]=9;
		testarray[1][3]=12;
		testarray[2][0]=4;
		testarray[2][1]=7;
		testarray[2][2]=10;
		testarray[2][3]=13;
		testarray[3][0]=6;
		testarray[3][1]=8;
		testarray[3][2]=11;
		testarray[3][3]=15;
		System.out.println(find(testarray, 1));
	}
}

面试题4：替换空格
题目：请实现一个函数，把字符串中的每个空格替换成“%20”。

public class ReplaceBlank {
	public static void main(String args[]){
		String s="We are happy.";
		System.out.println(replaceBlank(s));
	}
	public String replaceBlank(String input){
		if(input==null)
		return null;
		StringBuffer outputBuffer=new StringBuffer();
		for(int i=0;i<input.length();i++){
		if(input.charAt(i)==' '){
		outputBuffer.append("%");
		outputBuffer.append("2");
		outputBuffer.append("0");
		}else {
		outputBuffer.append(String.valueOf(input.charAt(i)));
		}
		}
		return new String(outputBuffer);
	}
}

面试题5：从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
方法一：非递归的方式

public class PrintListReverse{
	public static void main (String args[])
	{
		ListNode node1=new ListNode();
		ListNode node2=new ListNode();
		ListNode node3=new ListNode();
		node1.data=1;
		node2.data=2;
		node3.data=3;
		node1.next=node2;
		node2.next=node3;
		printListReversversingly test=new printListReversversingly();
		test.printListReverse(node1);
	}
	public static void printListReverse(ListNode headNode){
		Stack<ListNode> stack=new Stack<ListNode>();
		while(headNode!=null){
		stack.push(headNode);
		headNode=headNode.next;
		}
		while(!stack.isEmpty()){
		System.out.println(stack.pop().data);
		}
	}
}

方法二:递归方式实现

public class PrintListReverse{
	public static void main (String args[]){
		ListNode node1=new ListNode();
		ListNode node2=new ListNode();
		ListNode node3=new ListNode();
		node1.data=1;
		node2.data=2;
		node3.data=3;
		node1.next=node2;
		node2.next=node3;
		printListReversversingly test=new printListReversversingly();
		test.printListReverse(node1);
	}
	public static void printListReverse(ListNode headNode){
		if(headNode!=null){
		if(headNode.next!=null){
		printListReverse(headNode.next);
		}
		}
		System.out.println(headNode.data);
	}
}

面试题6：重建二叉树
题目描述：输入二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设前序遍历和中序遍历结果中都不包含重复的数字，例如输入的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建出如图所示的二叉树。

public class BinaryTreeNode {
	public static int value;
	public BinaryTreeNode leftNode;
	public BinaryTreeNode rightNode;
}
import java.util.Arrays;
	public class Problem6{
	public static void main(String[] args) throws Exception {
		int[] preSort={1,2,4,7,3,5,6,8};
		int[] inSort={4,7,2,1,5,3,8,6};
		BinaryTreeNode root=constructCore(preSort,inSort);
	}
	public static BinaryTreeNode constructCore(int[] preorder,int[] inorder) throws Exception{
		if(preorder==null||inorder==null){
		return null;
		}
		if(preorder.length!=inorder.length){
		throw new Exception("长度不一样，非法的输入");
		}
		BinaryTreeNode root=new BinaryTreeNode();
		for(int i=0;i<inorder.length;i++){
		if(inorder[i]==preorder[0]){
		root.value=inorder[i];
		System.out.println(root.value);
		root.leftNode=constructCore(Arrays.copyOfRange(preorder,1, i+1), Arrays.copyOfRange(inorder, 0, i));
		root.rightNode=constructCore(Arrays.copyOfRange(preorder,i+1, preorder.length),Arrays.copyOfRange(inorder, i+1, inorder.length));
		}
		}
		return root;
	}
}

面试题7：用两个栈实现队列
题目描述：用两个栈实现一个队列，实现对了的两个函数appendTail和deleteHead，分别完成在队列尾插入结点和在队列头部删除结点的功能。

public class Problem7<T> {
	private Stack<T> stack1=new Stack<T>();
	private Stack<T> stack2=new Stack<T>();
	public void appendTail(T t){
		stack1.push(t);
	}
	public T deleteHead() throws Exception{
		if(stack2.isEmpty()){
		while(!stack1.isEmpty()){
		stack2.push(stack1.pop());
		}
		}
		if(stack2.isEmpty()){
		throw new Exception("队列为空，不能删除");
		}
		return stack2.pop();
	}
	public static void main(String args[]) throws Exception{
		Problem7<String> p7=new Problem7<>();
		p7.appendTail("1");
		p7.appendTail("2");
		p7.appendTail("3");
		p7.deleteHead();
	}
}

面试题8：旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.

public class Problem8 {
public static void main(String[] args) {
Problem8 p8=new Problem8();
//int[] array={1,1,1,2,0};
// int[] array={3,4,5,1,2};
int[] array={1,0,1,1,1}; System.out.println(p8.findMinNum(array));
}
public Integer findMinNum(int[] array){
	if(array==null){
		return null;
	}
	int leftIndex=0;
	int rightIndex=array.length-1;
	int mid=0;
	while(array[leftIndex]>=array[rightIndex]){
		if(rightIndex-leftIndex<=1){
		mid=rightIndex;
		break;
		}
		mid=(leftIndex+rightIndex)/2;
		if(array[leftIndex]==array[rightIndex]&&array[leftIndex]==array[mid]){
		if(array[leftIndex+1]!=array[rightIndex-1]){
		mid=array[leftIndex+1]<array[rightIndex-1]?(leftIndex+1):(rightIndex-1);
		break;
		}else{
		leftIndex++;
		rightIndex--;
		}
		}else{
		if(array[mid]>=array[leftIndex])
		leftIndex=mid;
		else {
		if(array[mid]<=array[rightIndex])
		rightIndex=mid;
		}
		}
	}
	return array[mid];
	}
}

面试题9：斐波那契数列
题目一：写一个函数，输入n，求斐波那契数列的第n项。

public class Fibonacci {
	public long fibonacci(int n){
		long result=0;
		long preOne=0;
		long preTwo=1;
		if(n==0)
		{
		return preOne;
		}
		if(n==1)
		{
		return preTwo;
		}
		for(int i=2;i<=n;i++)
		{
		result=preOne+preTwo;
		preOne=preTwo;
		preTwo=result;
		}
		return result;
	}
}

面试题10：二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001；有2位是1，因此如果输入9，函数输出2.

public class Problem10 {
	public static void main(String args[]){
		Problem10 test=new Problem10();
		System.out.println(test.numberOf1(3));
	}
	public int numberOf1(int n){
		int count=0;
		while(n!=0){
			count++;
			n=(n-1) & n;
		}
		return count;
	}
}

限于篇幅，大家可以下载文后的附件查看更多的算法面试题。