[题解]剑指 Offer 58 - I. 翻转单词顺序(C++)
2021/8/23 14:05:44
本文主要是介绍[题解]剑指 Offer 58 - I. 翻转单词顺序(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. ",则输出"student. a am I"。
示例 1:
输入: "the sky is blue" 输出: "blue is sky the"
示例 2:
输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
说明:
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
- 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
要翻转单词的顺序同时保持单词内字符的顺序,很自然地想到利用栈先进后出的特性。遍历s把单词逐个入栈,然后抛出单词直到栈空,记得在首个单词以外的单词前面加上空格。
时间复杂度O(n),空间复杂度O(n)。
代码
class Solution { public: string reverseWords(string s) { stack<string> stk; for(int left = 0; left < s.size(); ++left) { if(s[left] != ' ') { int right = left; while(right < s.size() && s[right] != ' ') right++; string tmp(s.begin() + left, s.begin() + right); stk.push(tmp); left = right; } } string ans = ""; while(!stk.empty()) { if(!ans.empty()) ans += ' '; ans += stk.top(); stk.pop(); } return ans; } };
改进
用栈解决需要额外O(n)的空间,能不能直接在传入的s上原地修改?利用c++的翻转函数reverse(也可以自己实现)可以做到,先翻转整个字符串,然后用双指针,write指向要写入的位置,read指向读到单词的位置;read读到单词时,用wordend向后遍历到空格或者字符串结束,把wordend遍历到的字符写到write指向的位置,然后再在新字符串离翻转新写进来的这个单词。注意每次写入单词前除了首个单词外要加上空格。
时间复杂度O(n),空间复杂度O(1)。
代码
class Solution { public: string reverseWords(string s) { reverse(s.begin(), s.end()); int write = 0, n = s.size(); for(int read = 0; read < n; ++read) { if(s[read] != ' ') { if(write != 0) s[write++] = ' '; int wordend = read; while(wordend < n && s[wordend] != ' ') s[write++] = s[wordend++]; reverse(s.begin() + write - (wordend - read), s.begin() + write); read = wordend; } } s.erase(s.begin() + write, s.end()); return s; } };
这篇关于[题解]剑指 Offer 58 - I. 翻转单词顺序(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享