用动态和静态设计一个网站,四川建设信息网,海南最近三天的新闻大事,专门做旅游尾单的网站其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一#xff1a;双指针
2.2 方法二#xff1a;分割 倒序
三、代码
3.1 方法一#xff1a;双… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一双指针
2.2 方法二分割 倒序
三、代码
3.1 方法一双指针
3.2 方法二分割 倒序
四、复杂度分析
4.1 方法一双指针
4.2 方法二分割 倒序 前言
这是力扣的151题难度为中等解题方案有很多种本文讲解我认为最奇妙的两种。 一、题目描述
给你一个字符串 s 请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。
示例 1 输入s the sky is blue
输出blue is sky the 示例 2 输入s hello world
输出world hello
解释反转后的字符串中不能存在前导空格和尾随空格。示例 3 输入s a good example
输出example good a
解释如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个。提示
1 s.length 104s 包含英文大小写字母、数字和空格 s 中 至少存在一个 单词
进阶如果字符串在你使用的编程语言中是一种可变数据类型请尝试使用 O(1) 额外空间复杂度的 原地 解法。 二、题解 2.1 方法一双指针
思路与算法
先去首尾空格。倒序遍历字符串 s 记录单词左右索引边界 i , j 。每确定一个单词的边界则将其添加至单词列表 res 。最终将单词列表拼接为字符串去掉尾部空格并返回即可。
2.2 方法二分割 倒序
思路与算法
以空格为分割符完成字符串分割后若两单词间有 x1 个空格则在单词列表 strs 中此两单词间会多出 x−1 个 “空单词” 即 。
解决方法倒序遍历单词列表并将单词逐个添加至 StringBuilder 遇到空单词时跳过。 三、代码
3.1 方法一双指针
Java版本
class Solution {public String reverseWords(String s) {s s.trim(); // 删除首尾空格int j s.length() - 1, i j;StringBuilder res new StringBuilder();while (i 0) {while (i 0 s.charAt(i) ! ) i--; // 搜索首个空格res.append(s.substring(i 1, j 1)).append( ); // 添加单词while (i 0 s.charAt(i) ) i--; // 跳过单词间空格j i; // j 指向下个单词的尾字符}return res.toString().trim(); // 转化为字符串并返回}
}Python版本
class Solution:def reverseWords(self, s: str) - str:s s.strip() # 删除首尾空格i j len(s) - 1res []while i 0:while i 0 and s[i] ! : i - 1 # 搜索首个空格res.append(s[i 1: j 1]) # 添加单词while i 0 and s[i] : i - 1 # 跳过单词间空格j i # j 指向下个单词的尾字符return .join(res) # 拼接并返回3.2 方法二分割 倒序
Java版本
class Solution {public String reverseWords(String s) {String[] split s.trim().split( );StringBuilder res new StringBuilder();for (int i split.length - 1; i 0; i--) {if (!split[i].equals()) {res.append(split[i]).append( );}}return res.toString().trim();}
} Python版本
class Solution:def reverseWords(self, s: str) - str:return .join(s.strip().split()[::-1]) 四、复杂度分析
4.1 方法一双指针
时间复杂度 O(N) 其中 N 为字符串 s 的长度线性遍历字符串。空间复杂度 O(N) 新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 ≤ N 占用 O(N) 大小的额外空间。
4.2 方法二分割 倒序
时间复杂度 O(N) 总体为线性时间复杂度各函数时间复杂度和参考资料链接如下。 split() 方法 为 O(N) 。trim() 和 strip() 方法 最差情况下当字符串全为空格时为 O(N) 。join() 方法 为 O(N) 。reverse() 方法 为 O(N) 。 空间复杂度 O(N) 单词列表 strs 占用线性大小的额外空间。
