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

链接 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 --;
      }
  }
};

链接 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;
  }
};

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

链接 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();
  }
};

链接 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;
  }
};

链接 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;
}

链接 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;
  }
};

链接 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;
  }
};

链接 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/

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

反转字符串

leetcode.344

leetcode.541

反转字符串中的单词

leetcode.58

leetcode.557

剑指 offer.58(leetcode.151)

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

剑指 offer.05

leetcode.796

剑指 offer.58