题目一：
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路1：遍历每一行，然后对每一行进行二分查找，复杂度为n*logn
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++)
{
int min=0;
int max = array[i].length-1;
while(min<=max){
int mid = (min+max)/2;
if(target>array[i][mid])
min=mid+1;
else if(target<array[i][mid])
max=mid-1;
else
return true;
}
}
return false;
}
}思路二：
选取二维数组的一个角，比如选左下（不能选左上和右下，会产生岔路），target大于角则往右移一个（右边递增），target小于角则往上移一个（上面递减），不断如此就可以找到了
public class Solution {
public boolean Find(int target, int [][] array) {
int row=0;
int col=array.length-1;
while(col>=0&&row<array[col].length){
if(target<array[col][row])
col--;
else if(target>array[col][row])
row++;
else
return true;
}
return false;
}
}题目二：
题目描述
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer stb_new = new StringBuffer();
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(c==' ')
stb_new.append("%20");
else
stb_new.append(c);
}
return stb_new.toString();
}
}题目三：
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode!=null)
{
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}题目四：
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||in==null||pre.length==0||in.length==0)
return null;
TreeNode node = new TreeNode(pre[0]);
//pre[0]是根节点 注意！1.通过遍历可以知道 中序的in数组里 i所处的位置，左边是左子树 右边是右子树
//2.通过此时的i可以得出左右子树个数，就可以得出pre前序遍历中哪些是左子树的前序遍历
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;
}
}