题目一：二维数组中的查找
题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
二维数组的矩形是有序的，且向右向下递增。从第一行最后一列开始比较，如果target小于该对象，则跳过该列向左比较，如果target大于该对象，则跳过该行向下比较。直到找到target相等或者找完整个二维数组。
public boolean Find(int target, int [][] array) {
if(array == null || array.length < 1 || array[0].length < 1){
return false;
}
int rows = array.length;
int cols = array[0].length;
int row = 0;
int col = cols - 1;
while (row < rows && col < cols && row >=0 && col >= 0){
if(array[row][col] == target){
return true;
}else if(array[row][col] > target){
col--;
}else{
row++;
}
}
return false;
}
题目二：二维数组中的查找
题目描述：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路：
1.直接用replaceAll函数
public String replaceSpace(StringBuffer str) {
String string = str.toString();
return string.replaceAll("\\s","%20");
}
2.采用遍历的方式修改字符串
public String replaceSpace(StringBuffer str) {
StringBuffer out = new StringBuffer();
for(int i = 0; i < str.toString().length(); i++){
char b = str.charAt(i);
if(String.valueOf(b).equals(" ")){
out.append("%20");
}else{
out.append(b);
}
}
return out.toString();
}
题目三：从尾到头打印链表
题目描述：
输入一个链表，从尾到头打印链表每个节点的值。
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
解题思路：
1.遍历链表获得每个元素，采用栈结构实现先进后出。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<>();
if(listNode != null){
arrayList.add(listNode.val);
while (listNode.next != null){
listNode = listNode.next;
arrayList.add(0,listNode.val);
}
}
return arrayList;
}
2.采用递归的方式
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
this.printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}
题目四：重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
if(startPre>endPre||startIn>endIn){
return null;
}
TreeNode root=new TreeNode(pre[startPre]);
//对中序数组进行输入边界的遍历
for(int i = startIn; i <= endIn; i++){
if(in[i]==pre[startPre]){
//重构左子树，注意边界条件
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
//重构右子树，注意边界条件
root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
}
}
return root;
}
题目五：用两个栈实现队列
题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路：
两个栈，一个栈为入栈，一个栈为出栈，加入队列则添加到入栈，踢出队列则在出栈中pop，如果出栈为空，则遍历清空入栈，将元素以相反顺序添加到出栈中。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.empty()){
while (!stack1.empty()){
int i = stack1.pop();
stack2.push(i);
}
}
return stack2.pop();
}
