在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析：一个数一定比它左边的大，一定比它上方的大，因此从左下方判断，如果target比当前大，向右移动，如果targe比当前小，向上移动
public class Solution { public boolean Find(int target, int [][] array) { if(array==null||array.length==0||array[0].length==0){ return false; } int i=array.length-1,j=0,col=array[0].length; while(i>=0&&j<col){ if(array[i][j]==target){ return true; }else if(array[i][j]<target){ j++; }else { i--; } } return false; } }请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
public class Solution { public String replaceSpace(StringBuffer str) { return str.toString().replace(" "," "); } } //2 public class Solution { public String replaceSpace(StringBuffer str) { for(int i=0;i<str.length();i++){ if(str.charAt(i)==' '){ str.setCharAt(i,'%'); str.insert(i+1,'2'); str.insert(i+2,'0'); } } return str.toString(); } }输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res=new ArrayList<>(); while(listNode!=null){ res.add(0,listNode.val); listNode=listNode.next; } return res; } }输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析：此题考察二叉树的下先序遍历和中序遍历的性质： 在中序遍历中，左子树的数据一定在该节点的左边，右子树的数据一定在该节点的右边；因此从pre数组中遍历，每遇见一个数都可以将中序遍历的序列一分为二；因此使用分治法
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.Map; import java.util.HashMap; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { Map<Integer,Integer> mid=new HashMap<>(); //记录中序遍历的{val,index} for(int i=0;i<in.length;i++){ mid.put(in[i],i); } TreeNode res=new TreeNode(pre[0]); res.left=help(pre,mid,0,mid.get(pre[0])-1,1); res.right=help(pre,mid,mid.get(pre[0])+1,in.length-1,mid.get(pre[0])+1); return res; } //参数：先序遍历列表，map，中序遍历中的片段（start，end），遍历先序列表的指针 public TreeNode help(int[] pre,Map<Integer,Integer> mid,int st,int end,int preStart){ if(st>end){ return null; } TreeNode curr=new TreeNode(pre[preStart]); int index=mid.get(pre[preStart]); curr.left=help(pre,mid,st,index-1,preStart+1); //下一个右节点在先序遍历中的起始位置应该是：当前的preStrat+左子树节点的个数 curr.right=help(pre,mid,index+1,end,preStart+(index-st)+1); return curr; } }用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
分析：考察栈和队列的性质，栈：先进后出，队列：先进先出；因此负负得正 使用一个栈专门push，一个栈专门pop，如果pop栈空了，就将push栈中的数据添加进pop栈中，此时pop先出栈的就是先入push栈的
import java.util.Stack; public class Solution { Stack<Integer> useStore = new Stack<Integer>(); Stack<Integer> asQueue = new Stack<Integer>(); public void push(int node) { useStore.push(node); } public int pop() { if(asQueue.isEmpty()){ while(!useStore.isEmpty()){ asQueue.push(useStore.pop()); } } return asQueue.pop(); } }题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
分析：遍历，判断连续连个数的大小 二分法：如下
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0){ return 0; } for(int i=0;i<array.length-1;i++){ if(array[i]>array[i+1]){ return array[i+1]; } } return array[0]; } } import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0){ return 0; } int left=0,right=array.length-1,mid=0; //左边的数小于右边的数，说明次片段已经有序，可以跳出循环了 while(array[left]>=array[right]){ //如果相差为1，则一定存在最小值，且是右边的数 if(right-left==1){ mid=right; break; } mid=(right-left)/2+left; //中间的数大于左边的数，说明最小值一定在右边 if(array[mid]>=array[left]){ left=mid; }else{ right=mid; } } return array[mid]; } } import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length==0){ return 0; } int left=0,right=array.length-1,mid=0; while(left<right){ if(array[left]<array[right]){ return array[left]; } mid= (right-left)/2+left; //左边有序 if(array[left]<array[right]){ left=mid; //右边有序 }else if(array[mid]<array[right]){ right=mid; //array[left]==array[mid]==array[right] }else{ left++; } } return array[left]; } }