题目描述——替换空格
请实现一个函数,将一个字符串中的每个空格替换成“%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;
    }
}

测试用例

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