(字符串 ) 151. 反转字符串中的单词 ——【Leetcode每日一题】

news/2024/11/13 4:34:35/

❓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 . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
  • s 包含英文大小写字母数字和空格 ' '
  • s 中 至少存在一个 单词

进阶:如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O ( 1 ) O(1) O(1) 额外空间复杂度的 原地 解法。

💡思路:

不使用辅助空间,那么只能在原字符串数组上下功夫了。

我们将整个字符串都反转过来,那么单词的顺序指定是倒序了,只不过单词本身也倒序了,那么再把单词反转一下,单词不就正过来了:

  1. 移除多余空格;(一个erase本来就是 O ( n ) O(n) O(n)的操作, 所以这里使用快慢指针 平移,然后resize())
  2. 将整个字符串反转;
  3. 将每个单词反转。

🍁代码:(Java、C++)

Java

class Solution {public String reverseWords(String s) {StringBuilder sb = new StringBuilder();int start = 0, end = s.length() - 1;while(s.charAt(start) == ' ') start++;while(s.charAt(end) == ' ') end--;while(start <= end){//删除空格char c = s.charAt(start);if(c != ' ' || sb.charAt(sb.length() - 1) != ' ') sb.append(c);start++;}sb.reverse();//整个字符串反转int n = sb.length();start = 0;for(int i = 0; i < n; i++){//反转每个单词while(i < n && sb.charAt(i) != ' ') i++;end = i - 1;while(start < end){char c = sb.charAt(start);sb.setCharAt(start, sb.charAt(end));sb.setCharAt(end, c);start++;end--;}start = i + 1;}return sb.toString();}
}

C++

class Solution {
public:string reverseWords(string s) {int slow = 0;for(int i = 0; i < s.size(); ++i){if(s[i] != ' '){//遇到非空格就处理,即向前移动,以删除所有空格if(slow != 0) s[slow++] = ' ';//在单词前添加空格while(i < s.size() && s[i] != ' '){//补上该单词,遇到空格说明单词结束s[slow++] = s[i++];}}}s.resize(slow);slow的大小即为去除多余空格后的大小reverse(s.begin(), s.end());//整个字符串反转for(int start = 0, i = 0; i <= s.size(); i++){//反转每个单词if(s[i] == ' ' || i == s.size()){reverse(s.begin() + start, s.begin() + i);start = i + 1;}}return s;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为输入字符串的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n),取决于使用的语言中字符串类型的性质。如果字符串是可修改的(C++),那么我们可以直接在原字符串上修改,空间复杂度为 O ( 1 ) O(1) O(1),(Java)否则需要使用 O ( n ) O(n) O(n) 的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/172648.html

相关文章

飞桨 GPU 训练

飞桨官网介绍使用流程 paddle —— 飞桨的深度学习核心框架本地 padddlepaddle 的安装和卸载安装查看当前安装的版本卸载 启动 GPU 训练指定 GPU 飞桨创建项目PaddlePaddle 2.1.2 下的对比修改为 paddlepaddle2.4.0 CUDA 飞桨 飞桨官网&#xff1a;https://www.paddlepaddle.o…

Android 加载第三方sdk 踩坑指南

踩坑指南1:加载 so System.load() 或 System.loadLibrary() 区别 在 Java 中&#xff0c;System.load() 和 System.loadLibrary() 都是用于加载本地库&#xff08;Native Library&#xff09;的方法。本地库是一种使用本地语言&#xff08;如 C 或 C&#xff09;编写的库&am…

linux ac97声卡驱动下载,AC97声卡如何在Linux操作系统中进行驱动

AC97是工业标准&#xff0c;除有版本号之分外&#xff0c;还有芯片厂商之分&#xff0c;要区分对待。 AC97声卡有两部分&#xff1a;主板芯片组的南桥(South Bridge)和Audio Codec。主板芯片厂商有Intel、Via、SiS、nVidia、Ali等。 常见的Audio Codec芯片有RealTek的ALC系列、…

win7如何安装无线网卡驱动程序?具体安装步骤

win7如何安装无线网卡驱动程序&#xff1f;电脑安装无线网卡驱动后&#xff0c;就能帮助用户快速连接wifi&#xff0c;很多用户还不知道如何操作吧&#xff0c;下面就来看看小编带来的win7安装无线网卡驱动的方法介绍。 win7如何安装无线网卡驱动程序&#xff1f; 1、首先&…

怎么在win7上安装AIR780E的USB驱动

前面写的教程里有讲到win10自带USB驱动&#xff0c;但是win7要自己安装&#xff0c;很多人说不会装&#xff0c;装上不能用之类的&#xff0c;今天就写教程记录一下怎么在win7上安装AIR780E的USB驱动。 一、准备工作 需要开发板一块电脑一台&#xff0c;win7系统TYPEC数据线一…

AD9371、AD9361、ADRV9009驱动开发、调试

ADRV9361、AD9371、9009是有ADI开发的射频直采芯片。 ADI官方提供的demo都是给予总线架构的&#xff0c;个人认为不方便移植&#xff0c;下面就单独就AD9371的开发架构做一个简单的说明&#xff1a; ADI官方驱动是基于总线架构的&#xff0c;具体的架构如下图所示&#xff1a; …

华硕rt-ac85p更换新驱动(一)

ap_cfg.c文件需要添加如下内容&#xff0c;否则led和webui会不正常&#xff0c;其他需要声明的自行添加到头文件就可以了 case CMD_RTPRIV_IOCTL_ASUSCMD://RTMPIoctlAsusHandle(pAd, wrq, subcmd, pData, Data);if ( subcmd ASUS_SUBCMD_CHLIST) {UINT32 i;UCHAR BandIdx;CHA…

Linux ALSA音频驱动二:ALSA驱动注册

在系统/dev/snd下可查看注册成功的声卡信息&#xff0c;如下所示。 ubuntuubuntu:~$ ls -l /dev/snd total 0 drwxr-xr-x 2 root root 60 4月 7 09:22 by-path crw-rw---- 1 root audio 116, 2 4月 7 09:22 controlC0 // 通路控制 crw-rw---- 1 root audio 116,…