反转字符串中的单词
思考
这题的思路顺序是：移除多余空格（双指针法）——》反转整个字符串）——》反转字符串中每个单词。
移除多余空格（双指针法）
因为字符串开头也可能有多个字符，所以我们的两个指针应该从头开始，用快指针判断当前字符是否是题目中的有效字符（非多余空格），慢的则用来将快指针指向字符赋值到自己。具体代码如下：
// 消除多余空格
void eraseSpace(string& s) {
int slow = 0; // 设置慢指针
for(int i = 0; i < s.size(); i++) { // i相当于快指针
if(s[i]!=' ') { // 当i不是空格时，即我们遇到单词的第一个字母啦
if(slow!=0) s[slow++] = ' '; // 首先判断当前是不是第一个单词，因为第一个单词前面不需要空格，所以只要不是第一个单词，我们就在它前面加上空格
while(s[i]!=' ' && i < s.size()) // 循环整个单词到其结尾
s[slow++] = s[i++];
}
}
s.resize(slow);
}
反转字符串
// 反转整个字符串
void reverseString(string& s, int begin, int end) {
for(int i = begin, j = end; i < j; i++, j--)
swap(s[i], s[j]);
}
反转字符串中每个单词
这应该是我们的最后一步，目的是定位到字符串中的单词，对它进行反转。这里我是用while循环到每个单词的末尾，代码随想录中是找到分隔空格来定位单词，两种方法都可以。
- 我的：
string reverseWords(string s) {
eraseSpace(s);
reverseString(s, 0, s.size()-1);
int begin = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]!=' ') {
while (s[i]!=' ' && i < s.size()) i++; // 循环到单词末尾
reverseString(s, begin, i-1); // 反转当前单词
begin = i+1; // 找到下一个单词的开头index
}
}
return s;
}
- 代码随想录：
string reverseWords(string s) {
removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
reverse(s, 0, s.size() - 1);
int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
for (int i = 0; i <= s.size(); ++i) {
if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
start = i + 1; //更新下一个单词的开始下标start
}
}
return s;
整体代码
class Solution {
public:
// 消除多余空格
void eraseSpace(string& s) {
int slow = 0; // 设置慢指针
for(int i = 0; i < s.size(); i++) { // i相当于快指针
if(s[i]!=' ') { // 当i不是空格时，即我们遇到单词的第一个字母啦
if(slow!=0) s[slow++] = ' '; // 首先判断当前是不是第一个单词，因为第一个单词前面不需要空格，所以只要不是第一个单词，我们就在它前面加上空格
while(s[i]!=' ' && i < s.size()) // 循环整个单词到其结尾
s[slow++] = s[i++];
}
}
s.resize(slow);
}
// 反转整个字符串
void reverseString(string& s, int begin, int end) {
for(int i = begin, j = end; i < j; i++, j--)
swap(s[i], s[j]);
}
string reverseWords(string s) {
eraseSpace(s);
reverseString(s, 0, s.size()-1);
int begin = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]!=' ') {
while (s[i]!=' ' && i < s.size()) i++; // 循环到单词末尾
reverseString(s, begin, i-1); // 反转当前单词
begin = i+1; // 找到下一个单词的开头index
}
}
return s;
}
};
右旋字符串
思考
在不利用额外空间的条件下，看似很困难，实际上沿用上题的思想就很简单。拿abcdefg, k=2举例，我们要做的是将最后两个字符放到前面去，即fgabcde。实际上我们可以把整个字符串看成两段：abcde和fg。
- 首先反转整个字符串，这样一来就实现了上面两段字符的反转：
gf edcba； - 然后再分别对这两段进行反转，就得到了我们想要的：
fg abcde。
cpp代码
#include <iostream>
using namespace std;
void reverse(string& s, int begin, int end) {
for(int i = begin, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
int main() {
int k;
string s;
cin >> k; // 获取第一行：右旋转的位数
cin >> s; // 获取第二行：字符串
reverse(s, 0, s.size()-1); // 字符串整体反转
reverse(s, 0, k-1); //反转右旋转的字符
reverse(s, k, s.size()-1); // 反转剩下的字符
cout << s << endl;
}
