1.二维数组中查找
2.替换空格
3.从尾到头打印链表
4.重建二叉树
5.用两个栈实现队列
6.旋转数组的最小数字
7.斐波那契数列
8.跳台阶
9.变态跳台阶
10.矩形覆盖
1.二维数组中查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
方法一，从左下开始遍历，大就往右，小就往上
public static boolean Find(int target, int [][] array) {
int len=array.length-1;
int i=0;
while((len>=0)&&(i<array[0].length)){
if(array[len][i]==target)
return true;
else if(array[len][i]>target)
len--;
else if(array[len][i]<target)
i++;
}
return false;
}
方法二 二分法 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案。
public static boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++){
int low=0;
int high=array[i].length-1;
while(low<=high){
int mid=(low+high)/2;
if(target>array[i][mid])
low=mid+1;
else if(target<array[i][mid])
high=mid-1;
else
return true;
}
}
return false;
@Test
public void test(){
int arrays[][]={{1,4,7,9},{2,7,8,11},{4,8,12,19}};
if(Find(12,arrays))
System.out.println("数据含有这样的整数");
else
System.out.println("没有这样的整数");
}
3.从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
利用栈存储，后进先出特性
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList list=new ArrayList<Integer>();
Stack<Integer> stack=new Stack<>();
while(listNode!=null){
stack.push(listNode.val);
listNode=listNode.next;
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode reConstructBinaryTree(int[] pre,int[] in){
if(pre.length==0||in.length==0)
return null;
TreeNode node=new TreeNode(pre[0]);
for(int i=0;i<in.length;i++){
if(pre[0]==in[i]){
node.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
node.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
}
}
return node;
}
方便理解再举个例子：
前序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
第一步，根据前序遍历的特点，我们知道根结点为G
第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。
第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
5.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty())
throw new RuntimeException("queue is empty");
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
6.旋转数字的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{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] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误， 因此high = mid
但情形(1)中low = mid + 1就不会错误
public int minNumberInRotateArray(int [] array) {
if(array.length==0)
return 0;
int low=0;int high=array.length-1;
while(low<high){
int mid=low+(high-low)/2;
if(array[mid]>array[high]){
low=mid+1;
}else if(array[mid]==array[high]){
high=high-1;
}else{
high=mid;
}
}
return array[low];
}
7.斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
public int Fibonacci(int n) {
if(n==1)
return 1;
if(n==2)
return 1;
if(n>2)
return Fibonacci(n-1)+Fibonacci(n-2);
return 0;
}
8.跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
两种跳法，1阶或者2阶，那么
假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2).
可以得出总跳法为: f(n) = f(n-1) + f(n-2) 。通过实际的情况可以得出：一阶f(1) = 1 ,两阶f(2) = 2。得出的是一个斐波那契数列：
| 1, (n=1)
f(n) = | 2, (n=2)
| f(n-1)+f(n-2) ,(n>2,n为整数)
// 2 ---> 11,2 2
// 3 ---> 12,21,111 3
// 4 ---> 112,121,211,1111,22
// 5 ---> 1112,1121,1211,2111,221,122,212,11111 8
if(target<=0)
return -1;
if(target==1)
return 1;
if(target==2)
return 2;
return JumpFloor(target-1)+JumpFloor(target-2);
public int JumpFloor2(int target) {
if(target==1)
return 1;
if(target==2)
return 2;
int first=1,second=2,third=0;
for(int i=3;i<=target;i++){
third=first+second;
first=second;
second=third;
}
return third;
}
9.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
关于本题，前提是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阶的 跳法数。
2.n = 1时，只有1种跳法，f(1) = 1
3. n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），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(0) + f(1) + f(2) + f(3) + ... + f(n-1)
6. 由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = 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)
public int JumpFloorII(int target) {
/*
* 1 -- >1 1
* 2 --> 11,2 2
* 3 -->12,21,111,3 4
* 4 -->1111,121,112,211,22,13,31,4 8
*/
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的大矩形，总共有多少种方法？
斐波那契数列
2*n的大矩形，和n个2*1的小矩形
其中target*2为大矩阵的大小
有以下几种情形：
1.target <= 0 大矩形为<= 2*0,直接return 1；
2.target = 1大矩形为2*1，只有一种摆放方法，return1；
3.target = 2 大矩形为2*2，有两种摆放方法，return2；
4.target = n 分为两步考虑：
第一次摆放一块 2 *1 的小矩阵，则摆放方法总共为f(target - 1)
第一次摆放一块12的小矩阵，则摆放方法总共为f(target-2)
因为，摆放了一块12的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)
public int RectCover(int target){
if(target<1)
return 0;
if(target*2==2)
return 1;
if(target*2==4)
return 2;
return RectCover(target-1)+RectCover(target-2);
}
