2.替換空格
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”警儒。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' '){
                str.deleteCharAt(i);
                str.insert(i,"%20");
            }    
        }
        return str.toString();
    }
}

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder sb = new StringBuilder();
        int j = 0;
        int i = 0;
        for(;i<str.length();i++){
            if(str.charAt(i)==' '){
                if(j!=i){
                    sb.append(str.subSequence(j, i));
                    sb.append("%20");
                }else{
                    sb.append("%20");
                }
                j=i+1;
            }
        }
        if(j != i){
            sb.append(str.subSequence(j,str.length()));
        }
        return sb.toString();
    }
}

3.從尾到頭打印鏈表
輸入一個(gè)鏈表追逮，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(listNode == null){
            return res;
        }
        ArrayList<ListNode> listNodes = new ArrayList<ListNode>();
        listNodes.add(listNode);
        while(listNode.next!=null){
                listNode = listNode.next;
                listNodes.add(listNode);
        }
        
        for(int i= listNodes.size()-1;i>=0;i--){
            int item = listNodes.get(i).val;
            res.add(item);
        }
        return res;
    }
}

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(listNode ==null){
            return list;
        }
        while(listNode!=null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

4.重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果粹舵，請(qǐng)重建出該二叉樹钮孵。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字捣郊。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}鞍盗，則重建二叉樹并返回涮因。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0){
            return null;
        }
        return build(pre,in,0,0,pre.length);
    }
    
    public TreeNode build(int[] pre,int[] in,int preStart,int inStart,int size){
        if(size==0){
            return null;
        }
        int nodeVal = pre[preStart];
        TreeNode treeNode = new TreeNode(nodeVal);
        
        int leftSize = 0;
        int rightInStart = inStart;
        for(;leftSize < size;leftSize++,rightInStart++){
            if( in[rightInStart] == nodeVal ){
                rightInStart++;
                break;
            }
        }
        int rightSize = size - leftSize - 1;
            
        treeNode.left  = build( pre , in , preStart + 1 , inStart , leftSize);
        treeNode.right = build( pre , in , preStart + leftSize+1,rightInStart,rightSize);
        return treeNode;
    }
}