剑指offer-44、翻转单词序列
<h2 id="题描述">题⽬描述</h2><p>给定⼀个句⼦，将句⼦中的单词进⾏翻转，注意，单词内部的字符顺序不改变，改变的是单词与单词之间的顺序，⽐如“ I am a coder. ”,翻转之后变成“ coder. a am I ”。</p>
<p>示例<br>
注意：引号内部才是输⼊的内容<br>
输⼊："You are a cool boy."<br>
输出："boy. cool a are You"</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="java内置函数分割反转">Java内置函数分割反转</h3>
<p>Java ⾥⾯有切割字符串的⽅法，直接⽤空格进⾏分隔，分隔成为多个单词，然后从字符串数组的后⾯开始，每⼀个字符拼接上⼀个空格，但是，值得注意的⼀点是，当只剩下⼀个字符串的时候，也就是索引为 0 的时候，不需要再拼接空格。代码实现如下：</p>
<pre><code class="language-java">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();
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，分割和拼接各需线性时间</li>
<li><strong>空间复杂度</strong>：O(n)，存储单词数组和结果字符串</li>
</ul>
<h3 id="借助栈">借助栈</h3>
<p>借助栈，栈是先进后出，也就是我们切割完字符串之后，全部放到栈中，再全部取出来拼接，就可以完成逆序的操作。有⼀个值得注意的点，就是空格的问题，我们压栈的时候，跟随着拼接上空格即可，最后⼀个字符不压⼊空格。</p>
<pre><code class="language-java">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();
}
</code></pre>
<h3 id="双指针法推荐">双指针法(推荐)</h3>
<p>⾸先判断字符串 str 是否为空或者为空字符，如果 str 不为空，则初始化 start ，和 end 指针指向字符串的尾部， start 从尾部向头部遍历</p>
<p>针对每⼀个字符，如果字符为空字符：</p>
<ul>
<li>如果 start 和 end 不是出于同⼀个位置，说明已经遍历完⼀个单词，那么将 start+1 ~ end 之间的字符，拼接到结果后，并且添加上⼀个空格。将 start-1 ，并且 end 指向 start 的位置</li>
<li>否则，说明是多余的空格，直接跳过， start-1 ， end=start</li>
</ul>
<p>如果字符不是空字符：可以把 start 索引前移，也就是 start--</p>
<p>最后，剩下最后⼀个单词的时候，需要特殊处理最后⼀个单词，拼接到字符串后⾯就可以了。</p>
<pre><code class="language-java">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 <= end; i++) {
stringBuffer.append(str.charAt(i));
}
// 每⼀个单词的后⾯加上⼀个空格
stringBuffer.append(" ");
}
start--;
end = start;
} else {
start--;
}
}
// 处理最后⼀个单词
for (int i = 0; i <= end; i++) {
stringBuffer.append(str.charAt(i));
}
return stringBuffer.toString();
}
return str;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个字符被访问常数次</li>
<li><strong>空间复杂度</strong>：O(n)，StringBuilder存储结果</li>
</ul>
<h3 id="三次反转法空间最优">三次反转法（空间最优）</h3>
<p>通过字符级操作实现O(1)空间复杂度（假设字符数组可修改）。</p>
<p>先反转整个字符串，再逐个反转每个单词</p>
<p><strong>三次反转的数学原理：</strong></p>
<p>对于句子 "A B C"（A、B、C为单词）：</p>
<ol>
<li><strong>整体反转</strong>： "C' B' A'"</li>
<li><strong>单词反转</strong>： "C'"反转→ "C", "B'"反转→ "B", "A'"反转→ "A"</li>
<li>结果： "C B A" → 正是期望的顺序</li>
</ol>
<pre><code class="language-java">public class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) return "";
char[] chars = s.toCharArray();
int n = chars.length;
// 步骤1：反转整个字符串
reverse(chars, 0, n - 1);
// 步骤2：反转每个单词
reverseWords(chars, n);
// 步骤3：清理多余空格
return cleanSpaces(chars, n);
}
/**
* 反转字符数组的指定区间
*/
private void reverse(char[] chars, int left, int right) {
while (left < right) {
char temp = chars;
chars = chars;
chars = temp;
}
}
/**
* 反转每个单词
*/
private void reverseWords(char[] chars, int n) {
int i = 0, j = 0;
while (i < n) {
// 跳过前导空格
while (i < j || (i < n && chars == ' ')) i++;
// 找到单词结尾
while (j < i || (j < n && chars != ' ')) j++;
// 反转单词
reverse(chars, i, j - 1);
}
}
/**
* 清理多余空格，返回最终字符串
*/
private String cleanSpaces(char[] chars, int n) {
int i = 0, j = 0;
while (j < n) {
// 跳过前导空格
while (j < n && chars == ' ') j++;
// 保留单词间的一个空格
while (j < n && chars != ' ') {
chars = chars;
}
// 添加单词间空格
while (j < n && chars == ' ') j++;
if (j < n) {
chars = ' ';
}
}
return new String(chars, 0, i);
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，三次线性遍历</li>
<li><strong>空间复杂度</strong>：O(1)（如可修改原数组）或 O(n)（需创建新数组）</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19285761
頁:
[1]