【字符串算法题记录】反转字符串中的单词(leetcode)，右旋字符串(kama)——双指针以及反转的奇思妙用

反转字符串中的单词

题目链接

思考

这题的思路顺序是：移除多余空格（双指针法）——》反转整个字符串）——》反转字符串中每个单词。

移除多余空格（双指针法）

因为字符串开头也可能有多个字符，所以我们的两个指针应该从头开始，用快指针判断当前字符是否是题目中的有效字符（非多余空格），慢的则用来将快指针指向字符赋值到自己。具体代码如下：

// 消除多余空格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;
}