数据结构-字符串、链表、树、栈和队列

题目描述——替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int length=str.length();
        int num=0;
        //先计算空格数
        for(int i=0;i<length;i++)
        {
            if(str.charAt(i)==' ')
                num++;
        }
        //计算替换之后的字符串的长度
        int newlength=length+num*2;
        int indexold=length-1;
        int indexnew=newlength-1;
        str.setLength(newlength);//扩大长度，防止越界
        for(;indexold>=0 && indexold<indexnew;indexold--)
        {
            if(str.charAt(indexold)==' ')
            {
                str.setCharAt(indexnew--,'0');
                str.setCharAt(indexnew--,'2');
                str.setCharAt(indexnew--,'%');
            }
            else
            {
                str.setCharAt(indexnew--,str.charAt(indexold));
            }
        }
        return str.toString();
    }
}

测试用例

输入的字符串中包含空格（空格位于最前面；空格位于最后面；空格位于中间；字符串中有连续多个空格）。
输入的字符串中没有空格。
特殊输入测试（字符串为空；字符串只有一个空格；字符串是连续多个空格）。

题目描述——从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1
输入:{67,0,24,58}
返回值:[58,24,0,67]
方法1：使用递归。实现简单，但当链表非常长时，会导致函数调用层级很深，从而导致函数调用栈溢出。
方法2：利用栈的特性（先进后出）。相比较递归，用栈基于循环实现的代码鲁棒性更好。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> s=new Stack<>();
        while(listNode!=null)
        {
            s.push(listNode.val);
            listNode=listNode.next;
        }
        ArrayList<Integer> a=new ArrayList<>();
        while(!s.isEmpty())
        {
            a.add(s.pop());
        }
        return a;
    }
}

测试用例
功能测试（输入的链表有多个节点；输入的链表只有一个结点）。
特殊输入测试（空链表）。

题目描述——用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    //入队列全由Stack1实现
    public void push(int node) {
        stack1.push(node);
    }
    //出队列时由Stack2实现
    public int pop() {
        if(stack2.isEmpty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

测试用例

往空队列里添加、删除元素。
往非空队列里添加、删除元素。
连续删除元素直至队列为空。

题目描述——重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

/*
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
*/
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length<=0)
            return null;
        if(pre.length==1)
            return new TreeNode(pre[0]);
        int rootval=pre[0];
        TreeNode root=new TreeNode(rootval);
        int rootindex=0;
        for(int i=0;i<in.length;i++)
        {
            if(in[i]==rootval)
            {
                rootindex=i;
                break;
            }
        }
        root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootindex+1),Arrays.copyOfRange(in,0,rootindex));
        root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,rootindex+1,pre.length),Arrays.copyOfRange(in,rootindex+1,in.length));
        return root;
    }
}

测试用例

普通二叉树（完全二叉树；不完全二叉树）。
特殊二叉树（所有节点都没有右子节点的二叉树；所有节点都没有左子节点的二叉树；只有一个节点的二叉树）。
特殊输入测试（空二叉树；输入的前序遍历序列和中序遍历序列不匹配）。