02.空格替换

• 题目描述

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

• 解题思路

要将字符串中所有的空格替换为"%20",首先考虑到数组的遍历，当遇到空格时，将其换成"%20",但是普通数组长度固定，而且索引不可变，将空格换成"%20"后，数组长度明显改变，而且空格后面的字符索引发生变化。因此使用数组是行不通的，可直接使用StringBuilder，StringBuilder为可变字符序列，其长度不固定，可以进行插入操作。

首先，用str.charAt()方法判断字符串中每个字符是否为 " "。如果是" "，就使用String类中的.append()方法，将"%20"添加到空格处；如果不是" "，就将该位置的字符添加到该位置，因此该位置上的字符未发生变化。遍历完成后，将StringBuilder类的可变字符序列转换成String类型的字符串输出。

Java代码实现如下：

public class Solution {
   public static String replaceSpace(StringBuffer str) {
    if (str == null) {
        return null;
    }
    StringBuilder str2 = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == ' ') {
        str2.append("%20");
        } else {
        str2.append(str.charAt(i));
        }
    }
    return str2.toString();
    }
}

• 解法二

使用java.uitl包中自带的str.replaceAll(regex, replacement)方法

代码如下：

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
}
}

03.从尾到头打印链表

• 题目描述

*输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
*

• 解题思路

1. 利用Stack(栈)先入后出的特性完成

Java代码实现如下：

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
       public ArrayList printListFromTailToHead(ListNode listNode) {
    //使用栈这种数据结构
    Stack stack = new Stack();
    //将链表元素全部存放在栈里面
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList ret = new ArrayList();
   //取出栈里面的元素
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}
    }

2.利用递归（参考大神garss_stars的代码）

public class Solution {
    ArrayList arrayList=new ArrayList();
    public ArrayList printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}