剑指offer_02_空格替换/从尾到头打印链表
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。
*
- 解题思路
- 利用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;
}
} 
