常见的经典面试题

面试题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：替换空格 题目：请实现一个函数，把字符串中的每个空格替换成“ ”。 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; } }