1， /* * 在一个二维数组中，每一行都按照从左到右递增的顺序排序， * 每一列都按照从上到下递增的顺序排序。 * 请完成一个函数，输入这样的 * 一个二维数组和一个整数，判断数组中是否含有该整数。 */ 2， /* * 请实现一个函数，将一个字符串中的空格替换成“%2 * 0”。例如，当字符串为We Are Happy.则经过替换 * 之后的字符串为We Are Happy。 */ 3， /* * 输入一个链表，从尾到头打印链表每个节点的值。 */ 4， /* * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 * 假设输入的前序遍历和中序遍历的结果中都 * 不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8 * }和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 */ 5，用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 6，把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 7，大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项 8，一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法 9，一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
package jianzhioffer; import java.util.ArrayList; import java.util.Arrays; import java.util.Queue; import java.util.Stack; public class Solution { public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } /* * 在一个二维数组中，每一行都按照从左到右递增的顺序排序， * 每一列都按照从上到下递增的顺序排序。 * 请完成一个函数，输入这样的 * 一个二维数组和一个整数，判断数组中是否含有该整数。 */ public boolean Find(int target, int [][] array) { for(int i=0;i<array.length;i++){ for(int j=0;i<array[i].length;j++){ if(array[i][j]==target){ return true; } } } return false; } /* * 请实现一个函数，将一个字符串中的空格替换成“%2 * 0”。例如，当字符串为We Are Happy.则经过替换 * 之后的字符串为We Are Happy。 */ public String replaceSpace(StringBuffer str){ for(int i=0;i<str.length();i++){ if(str.charAt(i)==' '){ //str.setCharAt(i, '%'); str.replace(i, i+1, " "); } } return str.toString(); } /* * 输入一个链表，从尾到头打印链表每个节点的值。 */ // public ArrayList<Integer> printListFromTailToHead(ListNode listNode){ // Stack<Integer> stack=new Stack<Integer>(); // while(listNode!=null){ // stack.push(listNode.val); // listNode=listNode.next; // } // ArrayList<Integer> arrays=new ArrayList<Integer>(); // // while(!stack.isEmpty()){ // arrays.add(stack.pop()); // } // return arrays; // } public ArrayList<Integer> printListFromTailToHead(ListNode listNode){ ArrayList<Integer> array=new ArrayList<Integer>(); ListNode item=listNode; while(item!=null){ array.add(item.val); item=listNode.next; } Integer temp; Integer n=array.size(); for(int i=0;i<n;i++){ temp=array.get(i); array.set(i, array.get(n-i)); array.set(n-i, temp); } return array; } /* * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 * 假设输入的前序遍历和中序遍历的结果中都 * 不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8 * }和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 */ public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode reConstructBinaryTree(int [] pre,int [] in) { int length=in.length; TreeNode root=new TreeNode(pre[0]); if(length==1){ root.left=null; root.right=null; return root; } int rootval=root.val; int i=0; int n=in.length; for(i=0;i<n;i++){ if(in[i]==rootval){ break; } } if(i>0){ int[] pre1=new int[i]; int[] in1=new int[i]; for(int j=0;j<i;j++){ pre1[j]=pre[j+1]; } for(int k=0;k<i;k++){ in1[k]=in[k]; } root.left=reConstructBinaryTree(pre1, in1); } else{ root.left=null; } if(n-1-i>0){ int[] pre2=new int[n-1-i]; int[] in2=new int[n-1-i]; for(int j=i+1;j<n;j++){ pre2[j-i-1]=pre[j]; in2[j-i-1]=in[j]; } root.right=reConstructBinaryTree(pre2, in2); } else{ root.right=null; } return root; } /* * 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 */ Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { this.stack1.add(node); } /* * pop中先把stack1pop出来后获取最开始的元素之后，然后要回复原状 */ public int pop() { while(!(stack1.empty())){ stack2.push(stack1.pop()); } int value = stack2.pop(); while(!(stack2.empty())){ stack1.push(stack2.pop()); } return value; } /* * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 */ public int minNumberInRotateArray(int [] array) { if(array.length==0) return 0; int i=0; int min=array[0]; int index=0; int n=array.length; for(i=0;i<n;i++){ if(min>array[i]){ min=array[i]; index=i; } } int temp; for(i=0;i<index;i++){ temp=array[n-index+1]; array[n-index+1]=array[i]; array[i]=temp; } return min; } /* * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 */ public int Fibonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(n==2) return 1; int[] array=new int[n]; array[0]=1; array[1]=1; for(int i=2;i<n;i++){ array[i]=array[i-1]+array[i-2]; } System.out.println(Arrays.toString(array)); return array[n-1]; } /* * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法 */ public int JumpFloor(int target) { if(target<=0) return 0; if(target==1) return 1; if(target==2) return 2; int[] array=new int[target+1]; array[0]=0; array[1]=1; array[2]=2; for(int i=3;i<=target;i++){ array[i]=array[i-1]+array[i-2]; } System.out.println(Arrays.toString(array)); return array[target]; } /* * 一只青蛙一次可以跳上1级台阶，也可以跳上2级…… * 它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 */ public int JumpFloorII(int target) { if(target==0) return 0; if(target==1) return 1; int[] array=new int[target+1]; array[0]=0; array[1]=1; for(int i=2;i<=target;i++){ array[i]=2*array[i-1]; } System.out.println(Arrays.toString(array)); return array[target]; } /* * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ */ public static void main(String[] args){ System.out.println(new Solution().JumpFloorII(3)); } }