剑指offer-44、翻转单词序列
题⽬描述给定⼀个句⼦，将句⼦中的单词进⾏翻转，注意，单词内部的字符顺序不改变，改变的是单词与单词之间的顺序，⽐如“ I am a coder. ”,翻转之后变成“ coder. a am I ”。
示例
注意：引号内部才是输⼊的内容
输⼊："You are a cool boy."
输出："boy. cool a are You"
思路及解答
Java内置函数分割反转
Java ⾥⾯有切割字符串的⽅法，直接⽤空格进⾏分隔，分隔成为多个单词，然后从字符串数组的后⾯开始，每⼀个字符拼接上⼀个空格，但是，值得注意的⼀点是，当只剩下⼀个字符串的时候，也就是索引为 0 的时候，不需要再拼接空格。代码实现如下：
public class Solution {
public String ReverseSentence(String str) {
if (str == null || str.length() == 0 || str.equals(" ")) {
return "";
}
//去除首尾空格后，按照空格分隔
String[] strs = str.trim().split(" ");
StringBuilder stringBuilder = new StringBuilder();
for (int i = strs.length - 1; i >= 0; i--) {
stringBuilder.append(strs);
stringBuilder.append(i == 0 ? "" : " ");
}
return stringBuilder.toString();
}
}
[*]时间复杂度：O(n)，分割和拼接各需线性时间
[*]空间复杂度：O(n)，存储单词数组和结果字符串
借助栈
借助栈，栈是先进后出，也就是我们切割完字符串之后，全部放到栈中，再全部取出来拼接，就可以完成逆序的操作。有⼀个值得注意的点，就是空格的问题，我们压栈的时候，跟随着拼接上空格即可，最后⼀个字符不压⼊空格。
public String ReverseSentence(String str) {
if (str == null || str.length() == 0)
return str;
StringBuilder stringBuilder = new StringBuilder();
String[] strs = str.split(" ");
if (strs.length == 0)
return str;
Stack < String > stack = new Stack < > ();
for (int i = 0; i < strs.length - 1; i++) {
stack.push(strs);
stack.push(" ");
}
stack.push(strs);
while (!stack.isEmpty()) {
stringBuilder.append(stack.pop());
}
return stringBuilder.toString();
}双指针法(推荐)
⾸先判断字符串 str 是否为空或者为空字符，如果 str 不为空，则初始化 start ，和 end 指针指向字符串的尾部， start 从尾部向头部遍历
针对每⼀个字符，如果字符为空字符：
[*]如果 start 和 end 不是出于同⼀个位置，说明已经遍历完⼀个单词，那么将 start+1 ~ end 之间的字符，拼接到结果后，并且添加上⼀个空格。将 start-1 ，并且 end 指向 start 的位置
[*]否则，说明是多余的空格，直接跳过， start-1 ， end=start
如果字符不是空字符：可以把 start 索引前移，也就是 start--
最后，剩下最后⼀个单词的时候，需要特殊处理最后⼀个单词，拼接到字符串后⾯就可以了。
public class Solution { public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.ReverseSentence("nowcoder. a am I")); } public String ReverseSentence(String str) { if (str != null && str.length() != 0 && !str.equals(" ")) { int start = str.length() - 1, end = start; StringBuffer stringBuffer = new StringBuffer(); for (; start > 0;) { // 如果为空格 if (str.charAt(start) == ' ') { // 且开始索引和结束索引不⼀致的情况 if (start != end) { // 遍历start+1~end的字符，加到 for (int i = start + 1; i 这个好，看起来很实用 热心回复！
页:
[1]