在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 示例：自定义一个二维数组如下
891291114233546利用题中所给的条件：二维数组由左到右递增，由上到下递增的规律，那么，数组的左上角元素是最小的，数组的右下角元素是最大的。还有右上角的元素它的左边都比它小，下边元素都比它大。而左下角元素，该元素上边的都比自身小，右边的都比自身大。利用此性质，我们可以选取右上角元素或者左下角元素作为参照物。这里我选取的是右上角元素，拿着右上角元素array[row][col]与target进行比较，若target小于array[row][col]时，就不需要再考虑array[row][col]所在列的所有元素了，即col–（删除该列）。若target大于array[row][col]时，一样的道理就不需要再考虑array[row][col]所在行的所有元素了，即row++（删除改行）。 以上是该题思路。
实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
首先，我们要知道字符串中有多少个空格，既从头到尾遍历字符串，统计空格数。由此计算替换之后的所需要的总长度。然后从后往前依次检查字符串，如果发现是空格则替换为 。如果从前往后开始检查，发现有空格时需要移动后面的字符腾出位置，之后要不断向后检查一旦发现有空格还要继续后移字符（要多次移动，所以效率低下）。如果事先计算需要多少空间，从后往前检查，则每个字符只移动一次，这样效率更高。
String 字符串常量 StringBuffer 字符串变量（线程安全） StringBuilder 字符串变量（非线程安全）
简要的说， String 类型和 StringBuffer 类型的主要性能区别其实在于 String 是不可变的对象（常量）, 因此在每次对 String 类型进行改变的时候其实都等同于生成了一个新的 String 对象，其指针指向了新的 String 对象，所以经常改变内容的字符串最好不要用 String ，因为每次生成对象都会对系统性能产生影响，特别当内存中无引用对象多了以后，JVM 的 GC 就会开始工作，那速度是一定会相当慢的。
而如果是使用 StringBuffer 类则结果就不一样了，每次结果都会对 StringBuffer对象本身进行操作。而不是生成新的对象，再改变对象引用。所以在一般情况下我们推荐使用 StringBuffer， 特别是字符串对象经常改变的情况下。
输入一个链表，从尾到头打印链表每个节点的值。
将链表中的值从头到尾依次压入进栈，利用栈后进先出的性质从栈顶依次出栈实现了反转，同时再将出栈的元素加入新的链表，最后输出新的链表即可。
@skl--java package training; import java.util.List; import java.util.ArrayList; //ArrayList类是一种特殊的数组类型（动态数组） import java.util.Stack; public class Solution03 { public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode == null) return null; Stack<Integer> stk = new Stack<Integer>(); //定义一个栈类型 对象 stk while(listNode != null) { stk.push(listNode.val); //当前节点不为空时，将其值压入进栈 listNode = listNode.next; //节点后移一个位置继续检查 } ArrayList<Integer> arr = new ArrayList<Integer>(); while(! stk.isEmpty()) { arr.add(stk.pop()); //ArrayList自带的添加元素方法：add(object value)， //判断栈顶的当前元素不为空时，出栈同时加入数组arr } return arr; } public class ListNode { int val; ListNode next =null; ListNode(int val) { this.val = val; } } public static void main(String[] args) { int[] arr = {1, 23, 12, 8, 222}; int i = 0; Solution03 s = new Solution03(); ListNode listNode = s.new ListNode(arr[i++]); listNode.next = null; ListNode p = listNode; while(i < arr.length) { // 创建单链表 ListNode tmp = s.new ListNode(arr[i++]); tmp.next = null; p.next = tmp; p = tmp; } List<Integer> l = printListFromTailToHead(listNode); for(Integer t : l) { System.out.println(t); } }输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
整体思路是元素先依次进入栈1，再从栈1依次弹出到栈2，然后弹出栈2顶部的元素，整个过程就是一个队列的先进先出。但是在这个过程中需要判断两个栈的元素情况：“进队列时”，队列中是否还有元素，若有，说明栈2中的元素不为空，此时就先将栈2的元素出栈，保持在“进队列状态”。“出队列时”，将栈1的元素全部弹到栈2中，保持在“出队列状态”。所以要做的判断是，进时，栈2是否为空，不为空，则栈2元素出栈。出时，将栈1元素全部弹到栈2中，直到栈1为空。
@skl--java package training; import java.util.Stack; public class Solution05 { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int val) { stack1.push(val); } public int pop() { while(!stack2.isEmpty()) { return stack2.pop(); } while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); } public static void main(String []args) { Solution05 t = new Solution05(); t.push(1); t.push(2); t.push(3); t.push(4); System.out.println(t.pop()); System.out.println(t.pop()); System.out.println(t.pop()); System.out.println(t.pop()); } }把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
@skl--java package training; public class Solution06 { public int minNumberInRotateArray(int[] array) //minNumberInRoteArray1方法更加优化 { if (array == null || array.length == 0) { return 0; } int low = 0; int up = array.length - 1; int mid = low; while (array[low] >= array[up]) { if (up - low == 1) { mid = up; break; } if (array[low] == array[up] && array[mid] == array[low]) { return MinInOrder(array); } mid = (low + up) / 2; if (array[mid] >= array[low]) low = mid; else if (array[mid] <= array[up]) up = mid; } return array[mid]; } private int MinInOrder(int[] array) { int min = array[0]; for (int i = 1;i < array.length;i++) { if(array[i] < min) min = array[i]; } return min; } public int minNumberInRotateArray1(int [] array) { if(array == null || array.length == 0) { return 0; } for(int i = 1; i < array.length; i++) { if(array[i] < array[i - 1]) { // 若出现第一个元素递减就为最小元素 return array[i]; } } return array[0]; } public static void main (String[] args) { int [] a = {3,4,5,1,2}; Solution06 t = new Solution06(); int minnum = t.minNumberInRotateArray(a); //int minnum = t.minNumberInRotateArray1(a); System.out.println(minnum); } }大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
@skl--java package training; // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 public class Solution07 { public int Fibonacci(int n) { if(n <= 0) return 0; if(n == 1) return 1; return Fibonacci(n - 1) + Fibonacci(n - 2); } public int Fibonacci1(int n) //此方法是当时学c的时候书中提到的 { int f1 = 1; int f2 = 1; int f3 = 0; if(n == 0) return 0; if(n == 1 ||n == 2) return 1; for(int i = 1;i < n-1;i++) { f3 = f1 + f2; f1 = f2; f2 = f3; } return f3; } public static void main(String[] args) { Solution07 t = new Solution07(); int Fn = t.Fibonacci(8); //int Fn = t.Fibonacci1(8); System.out.println(Fn); } }一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
类似斐波那契数序列，初始条件n=1:只能一种方法，n=2:两种 对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以 F(n) = F(n-1) + F(n-2)
@skl--java package training; public class Solution08 { public static int jumpFloor(int target) //此方法比下面的方法更加优化 { int one = 1; int two = 2; if(target == 1) { return one; } if(target == 2) { return two; } for(int i = 3;i <= target; i++) { two = one + two; one = two - one; } return two; } public static int jumpFloor1(int target) { if(target < 0) { return 0; } if(target == 0) { return 1; } else { return jumpFloor1(target - 1) + jumpFloor1(target - 2); } } public static void main(String[] args) { Solution08 t = new Solution08(); int a = t.jumpFloor(3); System.out.println(a + "种跳法"); int b = jumpFloor1(4); System.out.println(b + "种跳法"); } }一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析如下: f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。 f(3) = f(3-1) + f(3-2) + f(3-3) … f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
以下具体来看： (1)这里的f(n)代表的是n个台阶规定一次可以跳1,2,…n阶台阶，共有f(n)种跳法。 (2) n = 1时，只有1种跳法，f(1) = 1 (3) n = 2时，有两种跳台阶方式一次1阶或者2阶， f(2) = f(2-1) + f(2-2) (4) n = 3时，会有三种跳台阶方式，1阶，2阶，3阶，那么若第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)，因此是f(3) = f(3-1)+f(3-2)+f(3-3) (5) n = n时，会有n中跳的方式，1阶、2阶…n阶，得出结论： f(n) = f(n-1)+f(n-2)+…+f(n-(n-1)) + f(n-n) f(n-1) = f(n-2) + … +f(1) + f(0) (6)所以有： f(n) = f(n-1)+f(n-1) 可以得出： f(n) = 2*f(n-1) 7) 得出最终结论,在n阶台阶，一次有1、2、…n阶的跳的方式时，总得跳法为： 1 , (n=0 ) f(n) = 1 , (n=1 ) 2*f(n-1),(n>=2)
@skl--java public class Solution09 { public static int jumpFloor(int target) { if(target < 0) { return 0; } else if(target == 1 || target == 0) { return 1; } else { return jumpFloor(target - 1) * 2; } } public static void main(String[] args) { Solution09 t = new Solution09(); int a = t.jumpFloor(5); System.out.println(a + "种跳法"); } }我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
2*n的大矩形，和n个2*1的小矩形 其中target*2为大矩阵的大小 有以下几种情形： (1)target < 1 大矩形为 < 2*1,直接return 0； (2)️target = 1大矩形为2*1，只有一种摆放方法，return1； (3)️target = 2 大矩形为2*2，有两种摆放方法，return2； (4)️target = n 分为两种情况考虑： 若第一次摆放一块 2*1 的小矩阵，则摆放方法总共为f(target - 1)
√√若第一次摆放一块1*2的小矩阵，则摆放方法总共为f(target-2) 因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)
√√××所以，target = n时，矩形覆盖方法共有：1*f(target - 1) + 1*f(target -2) 即：f(target - 1) + f(target -2)
@skl--java package training; public class Solution10 { public int RectCover(int target) { if(target < 1) { return 0; } if(target == 1 || target == 2) { return target; } else { return RectCover(target - 1) + RectCover(target - 2); } } public static void main(String[] args) { Solution10 t = new Solution10(); int a = t.RectCover(4); System.out.println("覆盖种数：" + a); } }