算法的学习笔记—翻转单词顺序列(牛客JZ73)

😀前言
在《剑指 Offer》系列题中，有一道关于翻转单词顺序的经典题目。给定一个由多个单词组成的字符串，需要将每个单词的顺序颠倒。这道题考察了对字符串的操作技巧，尤其是如何在限定空间内完成字符串的翻转。本文将详细解析这道题的解题思路，并提供代码实现。

🏠个人主页：尘觉主页

🥰翻转单词顺序列

😊题目链接

牛客网

❤️‍🔥题目描述

给定一个字符串，其包含若干个单词（单词之间由一个空格分隔），请将字符串中单词的顺序翻转。例如：

• 输入："I am a student."
• 输出："student. a am I"

💓解题思路

本题的关键在于 逐步翻转字符串。一种有效的解法是分为以下几个步骤：

1. 翻转每个单词：通过遍历字符串，将每个单词分别翻转。这样每个单词的字符顺序会变为逆序。
2. 整体翻转：在每个单词都逆序的基础上，翻转整个字符串。这样就达到了将单词顺序颠倒的效果。

这类似于 两次翻转 的操作：第一次翻转每个单词的字符顺序，第二次翻转整个字符串的顺序。

隐含条件

题目隐含了一个条件，即尽量不要使用额外的空间。如果不借助辅助空间（如额外的数组），则在原字符串上进行字符交换会显得更高效。

💞实现代码

以下是 Java 实现代码：

public class ReverseSentence {public String ReverseSentence(String str) {int n = str.length();char[] chars = str.toCharArray(); // 将字符串转换为字符数组int i = 0, j = 0;// 翻转每个单词while (j <= n) {if (j == n || chars[j] == ' ') { // 遇到空格或末尾时，翻转单词reverse(chars, i, j - 1);i = j + 1; // 更新 i 到下一个单词的开头}j++;}// 翻转整个字符串reverse(chars, 0, n - 1);return new String(chars); // 将字符数组转换回字符串}private void reverse(char[] c, int i, int j) {while (i < j) {swap(c, i++, j--); // 交换字符，实现翻转}}private void swap(char[] c, int i, int j) {char t = c[i];c[i] = c[j];c[j] = t;}public static void main(String[] args) {ReverseSentence rs = new ReverseSentence();String input = "I am a student.";String result = rs.ReverseSentence(input);System.out.println(result); // 输出："student. a am I"}
}

代码解析

• 变量定义：chars 是字符串的字符数组，用来保存中间结果；i 和 j 分别用于标记每个单词的起始和结束位置。
• 逐个翻转单词：通过 while 循环和条件判断，当遇到空格或字符串结尾时，调用 reverse 函数翻转单词。
• 整体翻转：在所有单词都翻转完后，对整个字符数组进行翻转，实现单词顺序的颠倒。
• 辅助方法 reverse：用于在给定的起始和结束索引之间反转字符顺序。
• 辅助方法 swap：用于交换两个字符，帮助 reverse 方法实现翻转。

示例运行

在上述代码中，若输入为 "I am a student."，代码会执行以下几步：

1. 翻转每个单词：
   • "I" -> "I"
   • "am" -> "ma"
   • "a" -> "a"
   • "student." -> ".tneduts"
2. 整体翻转字符数组，得到结果："student. a am I"

最终输出 "student. a am I"。

时间复杂度分析

该算法的时间复杂度为 O(n)，其中 n 为字符串的长度。我们对每个字符至多只访问两次（一次翻转单词，一次整体翻转），因此效率较高。

😄总结

本题使用了 双重翻转 的方法，巧妙地实现了翻转单词顺序的效果。通过这个思路，可以在不使用额外空间的情况下，完成对字符串的高效处理。在面试中，掌握该解法对于处理其他字符串类问题也有很大帮助。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞