题目描述  输入一个链表，反转链表后，输出新链表的表头。  思路：两个指针，循环调节指针方向。 代码： public class Solution { public ListNode ReverseList(ListNode head) { ListNode pre = null; ListNode p = null; while(head != null){ p = head.next; head.next = pre; pre = head; head = p; } return pre; } }

题目描述  输入一个链表，输出该链表中倒数第k个结点。  思路：  快慢指针。一个指针先跑k步，然后另一个指针在开始跑，直到前面的指针到空，两指针之间差k，后面的指针即是倒数第k个节点  代码： import java.util.*; public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if (k == 0 || head == null ){ return null; } ListNode fast = head; ListNode slow = head; for(int i = 0 ; ...

题目描述  输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。  思路：相对位置不变--->保持稳定性；奇数位于前面，偶数位于后面 --->存在判断，挪动元素位置；这些都和内部排序算法相似，考虑到具有稳定性的排序算法不多，例如插入排序，归并排序等；这里采用插入排序的思想实现。 代码： public class Solution { public void reOrderArray(int [] array) { //相对位置不变，稳定性 //插入排序的思想 int ...

题目描述  给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0  思路： ** * 1.全面考察指数的正负、底数是否为零等情况。**** * 2.写出指数的二进制表达，例如13表达为二进制1101。**** * 3.举例:10^1101 = 10^000110^010010^1000。**** * 4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。** 代码：  public class Solution { public double Power...

题目描述  输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。  思路： 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开...

题目描述  我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？请在这里输入引用内容比如n=3时，23的矩形块有3种覆盖方法：   思路：依旧是斐波那契数列 假设：n块矩形有f(n)种覆盖方法。进行逆向分析，要完成最后的搭建有两种可能。对于最左部分，两种情况，一种用一块，剩下f(n-1)。一种用两块，剩下f(n)故f(n) = f(n-1) + f(n-2)，还是一个斐波那契数列。。。。 代码： 非递归： public class Solution { public int RectCover(int target) { i...

题目描述  一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。  思路： 因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级跳1级，剩下n-1级，则剩下跳法是f(n-1)跳2级，剩下n-2级，则剩下跳法是f(n-2)所以f(n)=f(n-1)+f(n-2)+...+f(1)因为f(n-1)=f(n-2)+f(n-3)+...+f(1)所以f(n)=2*f(n-1) 代码： public class Solution { public int JumpFloorII(int target) { if (target <= 0...

题目描述  一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。  思路：实际上就是斐波那契数列 代码 public class Solution { public int JumpFloor(int target) { if(target==0) return 1; if(target==1) return 1; int si_1=1; int si_2=1; int result=0; for(int i=2;i<=target;i++){ result=si_1+si_2; si_2=si_1; si_1=resul...

题目描述  大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39  思路：1.尾递归2.循环 代码： 尾递归 public class Solution { public int Fibonacci(int n) { return Fibonacci(n,0,1); } private static int Fibonacci(int n,int acc1,int acc2){ if(n==0) return 0; if(n==1) return acc2; else return Fibonacci(n - 1, acc2, ...

题目描述  把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。  思路：采用二分法解答这个问题，mid = low + (high - low)/2需要考虑三种情况：(1)array[mid] > array[high]:出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。low = mid + 1(2)array[mid] ==...

题目描述  用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。  思路 用两个栈实现一个队列的功能?要求给出算法和思路! 入队：将元素进栈A 出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。 用两个队列实现一个栈的功能?要求给出算法和思路! 入栈：将元素进队列A 出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素 以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把 队列B中的元素出队列以此放入队列A中。 代码  import java.uti...

题目描述  输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。  思路：根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。 代码： import java.util.Arrays; public class S...

题目描述  输入一个链表，按链表从尾到头的顺序返回一个ArrayList。  思路：1.递归2.栈 代码：  递归代码 public class Solution { ArrayList<Integer> arrayList=new ArrayList<Integer>(); public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode!=null){ this.printListFromTailToHead(listNode.next); arrayLi...

题目描述  请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。  思路：替换字符串，是在原来的字符串上做替换，从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。 代码: public class Solution { public String replaceSpace(StringBuffer str) { int spacenum = 0;//spacenum为计算空格数 for(...