剑指offer（java版）.doc-资料库

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第1页.png

第1页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第2页.png

第2页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第3页.png

第3页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第4页.png

第4页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第5页.png

第5页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第6页.png

第6页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第7页.png

第7页 / 共22页

d01e5402-f4ae-4a82-9609-0d9b0034472a.doc.pdf-第8页.png

第8页 / 共22页

1、二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 public class Solution { public boolean Find(int [][] array,int target) { int len =array.length-1; int i = 0; while((len>=0)&&(itarget) { len--; }else if(array[len][i]

} } 3、从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值。 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; } 注： 1、创建一个新的栈创建一个新的 list 2、将原来栈的内容压入新栈 stack 3、判断新栈 stack 非空的情况下，将栈内容移除栈，并添加到 list 4、添加 java.util.Stack 的引用 4、重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。注：先序遍历：先访问根节点，再左子树，再右子树中序遍历：先访问左子树，再根节点，再右子树后序遍历：先访问左子树，再右子树，再根节点 public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } private TreeNode reConstructBinaryTree(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 = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i- 1); reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); root.right = } } return root; } } 5、用两个栈实现队列用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型。 <分析> <用两个栈实现一个队列的功能> 入队：将元素进栈 A 出队：判断栈 B 是否为空，如果为空，则将栈 A 中所有元素 pop，并 push 进栈 B，栈 B 出栈；如果不为空，栈 B 直接出栈。 <用两个队列实现一个栈的功能> 入栈：将元素进队列 A 出栈：判断队列 A 红元素的个数是否为 1，如果等于 1，则出队列，否则将队列 A 中的元素，以此出队列并放入队列 B，知道队列 A 中的元素留下一个，然后队列 A 出队列，再把，队列 B 中的元素出队列以此放入队列 A 中。 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() { if(stack2.empty()) { while(!stack1.empty()) { stack2.push(stack1.pop()); } if(stack2.empty()) { System.out.println("stack1 is empty"); return stack2.pop().intValue(); } } } } 6、旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。 NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。 import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int low = 0; int high = array.length - 1; if(array.length == 0) { return 0; } while(lowarray[high]){ low = mid +1; }else{ high = mid; } } return array[low];

} } 7、斐波那契数列大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项。n<=39 public class Solution { public int Fibonacci(int n) { if(n<2)return n; int a=0,b=1,tmp=0; for(int i=2;i<=n;i++) { tmp =b; b=a+b; a=tmp; } return b; } } 8、跳台阶一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 public class Solution { public int JumpFloor(int target) { if(target == 1||target == 2){ return target; } int sum = 0; int step1 = 1; int step2 = 2; for(int i = 3;i<=target;i++){ sum = step1 + step2; step1 = step2; step2 = sum; } return sum; } } 9、变态跳台阶一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 public class Solution {

public int JumpFloorII(int target) { if(target <=0){ return -1; }else if (target == 1){ return 1; }else{ return 2*JumpFloorII(target - 1); } } } 10、矩形覆盖题目描述我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？ public class Solution { public int RectCover(int target) { if(target <= 2){ return target; } int sum = 0; int a= 1; int b= 2; for(int i = 3;i<=target;i++){ sum = a+b; a = b; b = sum; } return sum; } } 或者 public class Solution { public int RectCover(int target) { if(target <= 2){ return target; }else{ return RectCover(target-1)+RectCover(target-2); } }

} 11、二进制中 1 的个数题目描述输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。 public class Solution { public int NumberOf1(int n) { int count = 0; while(n!=0){ count++; n=n&(n-1); } return count; } } 如果一个整数不为 0，那么这个整数至少有一位是 1。如果我们把这个整数减 1，那么原来处在整数最右边的 1 就会变为 0，原来在 1 后面的所有的 0 都会变成 1 （如果最右边的 1 后面还有 0 的话）。其余所有位将不会受到影响。举个例子：一个二进制数 1100，从右边数起第三位是处于最右边的一个 1。减去 1 后，第三位变成 0，它后面的两位 0 变成了 1，而前面的 1 保持不变，因此得到的结果是 1011.我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减 1 后的结果做与运算，从原来整数最右边一个 1 那一位开始所有位都会变成 0.如 1100&1011=1000.也就是说，把一个整数减去 1，再和原整数做与运算，会把该整数最右边一个 1 变成 0，那么一个整数的二进制有多少个 1，就可以进行多少次这样的操作。 12、数值的整数次方题目描述给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。 public class Solution { public double Power(double base, int exponent) { if(exponent == 0){ return 1; }else if(exponent > 0){ double num = base; for(int i=1;i

}else{ double nums = base; int flag = -exponent; for(int i=1;i0 3、exponent<0 13、调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 public class Solution { public void reOrderArray(int [] array) { int[] a = new int[array.length]; int[] b = new int[array.length]; int evenCount = 0; int oddCount = 0; for(int i =0;i

资料库

剑指offer（java版）.doc

相关推荐

课程资源

热门标签

最新资料