leetcode-翻转字符串里的单词
leetcode-翻转字符串里的单词
程序员小王
发布于 2019-05-05 16:33:09
发布于 2019-05-05 16:33:09
代码可运行
运行总次数：0
代码可运行
耗时一天时间竟然还是没有做出来
，整理出来下面三个思路。
主要涉及while循环和重复内存拷贝这2个问题。
平时根本体会不到。
151. 翻转字符串里的单词
- 去空格 多个只保留一个，字符串开始不是空格
- 单词顺序不变，但是字符串位置发生了翻转
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"测试
输入: " hello world! " 输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
开头存在空格
只存在一个空格
结尾存在空格
方法1 不需要考虑任何复杂情况
执行用时 : 16 ms, 在Reverse Words in a String的C++提交中击败了16.12% 的用户
内存消耗 : 10.6 MB, 在Reverse Words in a String的C++提交中击败了0.93% 的用户
class Solution {
public:
string reverseWords(string s) {
stack<string> stk;//LIFO context (last-in first-out)
int pos = 0;
string res;
while (pos < s.length()) {
int end, start;
while(s[pos] == ' ' && pos < s.length())
pos++;
start = pos;
while (s[pos] != ' ' && pos < s.length())
pos++;
end = pos;
if (end == start)
break;
stk.push(s.substr(start, end - start));
}
while (!stk.empty()) {
res += stk.top();
stk.pop();
if (!stk.empty())
res += " ";
}
return res;
}
};旁白：
- while适合用于状态变化控制，说高大上点就是while适合做状态机，而for仅仅是为了循环而循环
- while语句的历史更久，表达方式上更自由灵活，常用于无法事先判断循环次数的循环。譬如经典的计算C风格字符串的长度的代码，又如后根遍历二叉树的非递归实现。此时用while语句会使程序更清晰。
- 嵌套循环应该遵循“外小内大”的原则
方法2 去空格 然后翻转
class Solution {
public:
void reverse(string &s, int l, int r) {
while (l < r) swap(s[l++], s[r--]);
}
void reverseWords(string &s) {
int w = 0, r = 0, sz = s.size();
while (r < sz) {
if (s[r] == ' ') {
++r;
if (w - 1 >= 0 && s[w - 1] != ' ' && r < sz) s[w++] = ' '; // if not added space
}
else s[w++] = s[r++];
}
s.resize(w);
if (s.back() == ' ') s.resize(s.size() - 1); // remove possible space at the end of string
w = r = 0, sz = s.size();
while (r < sz) {
while (r < sz && s[r] != ' ') ++r;
reverse(s, w, r - 1);
while (r < sz && s[r] == ' ') ++r;
w = r;
}
reverse(s, 0, sz-1);
}
};方法3 合并1和2
class Solution {
public:
void reverseWords(string &s) {
int sz = s.size();
int i = 0, j = 0;
while (i < sz)
{
while (i < sz && s[i] == ' ') i++; //i is the start of the word
if (i < sz && j > 0)
s[j++] = ' ';
int start = j;
while (i < sz && s[i] != ' ')
s[j++] = s[i++];
reverse(s.begin()+start, s.begin()+j);
}
s.resize(j);
reverse(s.begin(), s.end());
}
};内存不重叠的拷贝。移动位置操作
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
