关于数据结构与算法:字符串

反转字符串

leetcode.344

链接https://leetcode.cn/problems/...
解题办法：双指针
l，r指针别离放在字符串的首尾两端，每次替换两个字符
每替换一次指针向两头挪动一位

leetcode解题代码

class Solution {public:  void reverseString(vector<char>& s) {      int l = 0, r = s.size() - 1;      while (l < r){          swap(s[l], s[r]);          l ++, r --;      }  }};

leetcode.541

链接https://leetcode.cn/problems/...
解题办法：双指针
定义保护的区间[l, r]，每次保护2k个数

leetcode解题代码

class Solution {public:  string reverseStr(string s, int k) {      int n = s.size();      for (int i = 0; i < n - 1; i += k * 2){          int l = i, r = min(i + k, n);          reverse(s.begin() + l, s.begin() + r);      }      return s;  }};

反转字符串中的单词

题目类型：给一个字符串组成的句子(带空格或标点)，而后对句中单个字符串进行一系列解决
这类题目能够分为两类，一类是有前置或者后置空格的，另一类是没有前置和后置空格的

leetcode.58

链接https://leetcode.cn/problems/...
解题办法：创立一个长期字符串（用来存每一个单词），和一个答案数组
遍历原字符串，如果遍历到空格，判断长期字符串是否为空
如果长期字符串非空则阐明曾经遍历完一个单词，将其退出答案数组中并清空长期字符串
如果遍历到的不是空格，将其退出长期字符串中

leetcode解题代码

class Solution {public:  int lengthOfLastWord(string s) {      s += " ";// 在字符串开端加上一个空格避免脱漏最初一个单词      string temp = "";      vector<string> res;      for (auto c: s){          if (c == ' '){              if (!temp.empty()){                  res.push_back(temp);                  temp.clear();              }          }          else temp += c;      }      if (res.empty()) return 0;      return res.back().size();  }};

leetcode.557

链接https://leetcode.cn/problems/...
解题办法：与上一题相似

leetcode解题代码

class Solution {public:  string reverseWords(string s) {      s += " ";      string temp = "";      vector<string> res;      for (auto c: s){          if (c == ' '){              if (!temp.empty()){                  res.push_back(temp);                  temp.clear();              }          }          else temp += c;      }      s.clear();      for (auto c: res){          reverse(c.begin(), c.end());          s += c + ' ';      }      s.pop_back();// 一开始加了一个空格记得删掉      return s;  }};

剑指offer.58(leetcode.151)

链接https://leetcode.cn/problems/...
https://leetcode.cn/problems/...
解题办法：与上一题相似

leetcode解题代码

class Solution {public:  string reverseWords(string s) {      s += " ";      string temp;      vector<string> res;      for (auto c: s){          if (c == ' '){              if (!temp.empty()){                  res.push_back(temp);                  temp.clear();              }          }          else temp += c;      }      s.clear();      reverse(res.begin(), res.end());      for (auto c: res){          s += c + ' ';      }      s.pop_back();      return s;  }};

ACM模式调试

输出字符串s

the sky is blue

输入

blue is sky the

调试代码

#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;int main(){    string s;    getline(cin, s);        s += ' ';    string temp;    vector<string> res;    for (auto c: s){        if (c == ' '){            if (!temp.empty()){                res.push_back(temp);                temp.clear();            }        }        else temp += c;    }        s.clear();    reverse(res.begin(), res.end());    for (auto c: res){        s += c + ' ';    }    s.pop_back();        cout << s << endl;    return 0;}

字符串中的其余操作（替换空格，旋转字符串等）

剑指offer.05

链接https://leetcode.cn/problems/...
解题办法：翻新新字符串，遍历原字符串找到空格替换即可

leetcode解题代码

class Solution {public:  string replaceSpace(string s) {      string res;      for (auto c: s){          if (c == ' '){              res += "%20";          }          else res += c;      }      return res;  }};

leetcode.796

链接https://leetcode.cn/problems/...
解题办法：如果字符串goal能通过字符串s旋转失去
那么字符串goal肯定是字符串s+s的字串，工夫复杂度为O(n^2)
（本题能够用KMP和字符串哈希求解，工夫复杂度能够降到O(n)）

leetcode解题代码

class Solution {public:  bool rotateString(string s, string goal) {      if (s.size() != goal.size()) return false;      s += s;      return s.find(goal) != std::string::npos;  }};

剑指offer.58

链接https://leetcode.cn/problems/...
解题办法：整体旋转
别离旋转前半部分和后半局部

leetcode解题代码

class Solution {public:  string reverseLeftWords(string s, int n) {      reverse(s.begin(), s.end());      reverse(s.begin(), s.end() - n);      reverse(s.end() - n, s.end());      return s;  }};

解题参考：https://www.acwing.com/
刷题程序参考：https://www.programmercarl.com/