本文共 12591 字，大约阅读时间需要 41 分钟。
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。方法一：暴力双层循环，代码简洁，时间复杂度为O(m*n)，内存消耗大
运行时间：185ms 184ms 占用内存：17560k 17440kpublic class Solution { public boolean Find(int target, int [][] array) { boolean flag=false; for(int i=0;i 方法二：从左下角（或右上角）比照，大则上移，小则右移，时间复杂度为O(m+n)
运行时间：145ms 148ms 占用内存：17456k 17492kpublic class Solution { public boolean Find(int target, int [][] array) { //定义多维数组的行数 int len = array.length - 1; //定义多维数组的列数 int row = 0; while(len >= 0 && row < array[0].length){ if(array[len][row] > target) len--; else if(array[len][row] < target) row++; else return true; } return false; }} 运行时间：24ms
占用内存：9548kpublic class Solution { public String replaceSpace(StringBuffer str) { return str.toString().replaceAll("\\s","%20"); }} 运行时间：27ms
占用内存：9516kimport java.util.ArrayList;import java.util.Collections;public class Solution { public ArrayList printListFromTailToHead(ListNode listNode) { ArrayList list =new ArrayList (); while(listNode!=null){ //在列表的指定位置插入指定元素。将当前处于该位置的元素（如果有的话）和所有后续元素向右移动（在其索引中加 1）。 list.add(0,listNode.val); listNode=listNode.next; } return list; }} 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
第一次：
测试输出不通过 用例: [1,2,3,4,5,6,7],[3,2,4,1,6,5,7] 对应输出应该为: {1,2,5,3,4,6,7} 你的输出为: {1,5,#,7}/** * 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) { //前序的第一个数字定为根 TreeNode root=new TreeNode(pre[0]); int length=pre.length; if(length==1){ root.left=null; root.right=null; } //找出中序中根的位置 int rootval=root.val; int i; for(i=0;i 0){ //pre[i]中1到i的全是左子树上的结点 //in[i]中0到i-1的全是左子树上的结点 int[] segPre=new int[i]; int[] segIn=new int[i]; for(int j=0;j 0){ int[] segPre=new int[length-i-1]; int[] segIn=new int[length-i-1]; //[i]后的全是右子树上的节点 for(int j=i+1;j 检查发现：
只有单节点时忘记返回根 右子树创建时 root.right 输错为 root.left 修改： 运行时间：250ms 占用内存：23660k/** * 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) { //前序的第一个数字定为根 TreeNode root=new TreeNode(pre[0]); int length=pre.length; //当只有一个结点时 if(length==1){ root.left=null; root.right=null; return root; } //找出中序中根的位置 int rootval=root.val; int i; for(i=0;i 0){ //pre[i]中1到i的全是左子树上的结点 //in[i]中0到i-1的全是左子树上的结点 int[] segPre=new int[i]; int[] segIn=new int[i]; for(int j=0;j 0){ int[] segPre=new int[length-i-1]; int[] segIn=new int[length-i-1]; //[i]后的全是右子树上的节点 for(int j=i+1;j 题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 运行时间：15ms 占用内存：9372kimport java.util.Stack;public class Solution { Stack input = new Stack (); Stack output = new Stack (); /* 1，整体思路是元素先依次进入栈1，再从栈1依次弹出到栈2，然后弹出栈2顶部的元素， 整个过程就是一个队列的先进先出 2，但是在交换元素的时候需要判断两个栈的元素情况： “进队列时”，队列中是还还有元素，若有，说明栈2中的元素不为空， 此时就先将栈2的元素倒回到栈1中，保持在“进队列状态”。 “出队列时”，将栈1的元素全部弹到栈2中，保持在“出队列状态”。 */ public void push(int node) { while(!output.empty()){ input.push(output.pop()); } input.push(node); } public int pop() { while(!input.empty()){ output.push(input.pop()); } return output.pop(); }} 题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。思路：
旋转后的数组实际上可以划分为两个有序的子数组，前面的子数组中的所有数都大于后面的子数组中的数。 （1）用left，right两个指针分别指向数组的第一个元素和最后一个元素，无重复时，按旋转规则，第一个元素大于最后一个元素 （2）找到中间元素， 若中间元素大于left，则中间元素位于前面的子数组中，最小值在中间元素后面的数组中 若中间元素小于left，则中间元素位于后面的子数组中，最小值在中间元素前面的数组中 （3）这样，第一个指针left总是指向前面子数组中的元素，第二个指针right总是指向后面子数组中的元素，最终他们将指向相邻的两个元素，最小值将是right指向的元素。 但是当存在重复元素时，比如｛1，0，1，1，1｝ 和 ｛1，1， 1，0，1｝，第一种情况下，中间数字位于后面的子数组，第二种情况，中间数字位于前面的子数组。因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面的子数组还是属于后面的子数组。import java.util.ArrayList;public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0){ return 0; } int leftIndex=0; int rightIndex=array.length-1; int mid=0; while(array[leftIndex]>=array[rightIndex]){ //如果left和right相邻，最小值就是right指向的值，取值后跳出循环 if(rightIndex-leftIndex<=1){ mid=rightIndex; break; } //取中值mid mid=(leftIndex+rightIndex)/2; //left和right指向重复的元素时， if(array[leftIndex]==array[rightIndex]&&array[leftIndex]==array[mid]){ //left和right相邻元素不等 if(array[leftIndex+1]!=array[rightIndex-1]){ mid=array[leftIndex+1] =array[leftIndex]){ leftIndex=mid; }else{ //中间值比right小，最小值在前面子数组，mid位置赋给right if(array[mid]<=array[rightIndex]){ rightIndex=mid; } } } } return array[mid]; }} 题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 递归 运行时间：21ms 占用内存：9248kpublic class Solution { public int Fibonacci(int n) { int result=0; int preOne=0; int 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; }} 迭代
运行时间：15ms 占用内存：9408kpublic class Solution { public int JumpFloor(int target) { if (target <= 0||target>39) { return -1; } if (target == 1) { return 1; } if (target == 2) { return 2; } int result=0; int firstJump=1,secondJump=2; for(int i=3;i<=target;i++){ result=firstJump+secondJump; firstJump=secondJump; secondJump=result; } return result; }} 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 （1）假设有n个台阶，第一次跳1个台阶，剩下解一个跳f(n-1)级台阶的问题 （2）如果第一次跳2个台阶，剩下解一个跳f(n-2)级台阶的问题，这样总解决次数 f(n)=f(n-1)+f(n-2) （3）当最后剩下一级或两级台阶时，f(1)=1，f(2)=2，整个问题转化为斐波那契数列问题递归
运行时间：637ms 占用内存：9348kpublic class Solution { public int JumpFloor(int target) { if (target <= 0||target>39) { return -1; } else if (target == 1) { return 1; } else if (target == 2) { return 2; } else { return JumpFloor(target-1)+JumpFloor(target-2); } }} 迭代
运行时间：16ms 占用内存：9380kpublic class Solution { public int JumpFloor(int target) { if (target <= 0||target>39) { return -1; } else if (target == 1) { return 1; } else if(target == 2) { return 2; } int result=0; int firstJump=1,secondJump=2; for(int i=3;i<=target;i++){ result=firstJump+secondJump; firstJump=secondJump; secondJump=result; } return result; }} 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 f(1)=1 f(2)=f(2-1)+f(2-2)=f(1)+1 … f(n)=f(n-1)+f(n-2)+…+f(1)+1=2*f(n-1)运行时间：19ms
占用内存：9088kpublic class Solution { public int JumpFloorII(int target) { if(target<=0){ return -1; }else if(target==1){ return 1; }else { return 2*JumpFloorII(target-1); } }} 题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？依然是斐波那契数列，对非法、1、2 解释后，对于n，纵向覆盖一个新的小矩形，排列方法为f(n-1)，横向排列一个新的小矩形，排列方法为f(n-2)。
运行时间：507ms
占用内存：9332kpublic class Solution { //target 代表要覆盖2*target大的大矩形 public int RectCover(int target) { if(target<=0){ return 0; }else if(target==1){ return 1; }else if(target==2){ return 2; }else{ return (RectCover(target-1)+RectCover(target-2)); } }} 题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
逐次辨别二进制补码最后一位是否为1
运行时间：12ms 占用内存：9784kpublic class Solution { public int NumberOf1(int n) { int count=0; while(n!=0){ count+=(n&1); n>>>=1; } return count; }} jdk自带计算位数的API
运行时间：18ms 占用内存：9436kpublic class Solution { public int NumberOf1(int n) { return Integer.bitCount(n); }} 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
原始做法：
运行时间：75ms 占用内存：10828kpublic class Solution { public double Power(double base, int exponent) { double result=1; for(int i=0;i 运行时间：39ms
占用内存：10564kpublic class Solution { public double Power(double base, int exponent) { if(exponent==0&&base!=0){ return 1; } if(exponent==1){ return base; } if(base==0&&exponent<=0){ //非法输入 throw new RuntimeException(); } if(base==0&&exponent>0){ return 0; } int n=Math.abs(exponent); double result=Power(base,n>>1); result*=result; if((n&1)==1){ result*=base; } if(exponent<0){ result=1/result; } return result; }} 非递归方法：
第一次： 空指针异常抛出public class Solution { public ListNode ReverseList(ListNode head) { if(head==null) return null; ListNode p=head.next; ListNode next=p.next; head.next=null; while(p!=null){ p.next=head.next; head.next=p; p=next; next=p.next; } return head; }} 第二次：
这个方法，链表如果有头结点，最后一个结点是空val的头结点。所以这个适合没有头结点的链表。 运行时间：20ms 26ms 占用内存：9716k 9532kpublic class Solution { public ListNode ReverseList(ListNode head) { if(head==null) return null; ListNode next,pre; pre=null; while(head!=null){ next=head.next;//next保存当前结点head的下一个节点防止断链 head.next=pre;//当前节点head的链指向上一个节点pre pre=head;//把当前节点赋给pre head=next;//当前节点head后移一位 } return pre; }} 第三次：
适用于带头结点的链表public class Solution { public ListNode ReverseList(ListNode head) { if(head==null) return null; ListNode next,p,pre; pre=head; p=head.next; next=p.next; pre.next=null; //提前处理头结点head while(p!=null){ next=p.next; p.next=pre.next; pre.next=p; p=next; } return pre; }} 非递归：
运行时间：21ms 占用内存：9700k/*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) return list2; if(list2==null) return list1; ListNode head=new ListNode(0); //预设头结点 ListNode temp=head; //当前结点指示器 while(list1!=null&&list2!=null){ //两链表当前都未空 if(list1.val<=list2.val){ temp.next=list1; list1=list1.next; }else{ temp.next=list2; list2=list2.next; } temp=temp.next; //移动当前结点指示器 } if(list1!=null){ //有没空的表继续连上 temp.next=list1; } if(list2!=null){ temp.next=list2; } return head.next; //剔除预设头结点返回 }} 递归：
运行时间：23ms 占用内存：9632kpublic class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; ListNode head=null; //头结点指示器 if(list1.val<=list2.val){ head=list1; head.next=Merge(list1.next,list2); //递归压栈，head这个引用 }else{ //最后会指向合并后第一个结点 head=list2; head.next=Merge(list1,list2.next); } return head; }} 转载地址：http://kavli.baihongyu.com/