151.翻转字符串里的单词
题目链接:https://leetcode.cn/problems/reverse-words-in-a-string/description/
文章讲解:https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
视频讲解:https://www.bilibili.com/video/BV1c8411P7iz/?spm_id_from=autoNext&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：
使用双指针的方法
class Solution {
public:// 翻转函数 左闭右开void reverse(string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {swap(s[i], s[j]);}}string reverseWords(string s) {// 1、去空格int i = 0;int j = 0;for (; j < s.size(); j++) {if (s[j] != ' ') { // 快指针指向的不能是空格if (i != 0) {//除了第一个单词，在后面的单词前面添加一个空格s[i++] = ' ';}while (j < s.size() && s[j] != ' ') {//当快指针不是空格时，就赋值给慢指针s[i++] = s[j++];}}}s.resize(i); // slow的大小即为去除多余空格后的大小。// 2、翻转字符串reverse(s, 0, s.size() - 1);// 3、单个单词进行翻转int start = 0;for (i = 0; i <= s.size();i++) {if (i == s.size() || s[i] == ' ') {reverse(s, start, i - 1);start = i + 1;}}return s;}
};
卡码网：55.右旋转字符串
题目链接:添加链接描述
文章讲解:添加链接描述
视频讲解:
实现情况：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;std::string rightRotateSimple(std::string s, int k) { if (s.empty() || k == 0) return s; k = k % s.length(); return s.substr(s.length() - k) + s.substr(0, s.length() - k);
} int main(void){int k ;string s;cin >> k >> s;string result = rightRotateSimple(s, k);cout << result << endl; return 0;}
#include <iostream>
#include <string>using namespace std;int main(void){int k ;string s;cin >> k >> s;if (s.empty() || k == 0|| k >= s.length()) return -1; string result = s.substr(s.length() - k) + s.substr(0, s.length() - k);cout << result << endl; return 0;
}
#include <iostream>
#include <string>
#include<algorithm>//reverse
using namespace std;int main(void){int k ;string s;cin >> k >> s;if (s.empty() || k == 0|| k >= s.size()) return -1; int len = s.size(); //获取长度reverse(s.begin(), s.end()); // 整体反转reverse(s.begin(), s.begin() + k); // 先反转前一段，长度nreverse(s.begin() + k, s.end()); // 再反转后一段cout << s << endl; return 0;
}
KMP算法了解一下
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个文本字符串S内查找一个词W的出现位置。该算法由Donald Knuth、Vaughan Pratt和James H. Morris三人于1977年联合发表。相比于简单的暴力匹配算法（即逐个字符比较），KMP算法通过预处理词W来避免在主字符串S中不必要的回溯，从而大大提高了匹配效率。
基本思想
KMP算法的核心在于，当在文本S中匹配词W时，如果遇到不匹配的字符，算法能够利用之前已经部分匹配的信息，将词W“滑动”到一个更有可能的位置，而不是从头开始重新匹配。这通过计算词W的“部分匹配表”（也称为“前缀函数”或“失败函数”）来实现。
部分匹配表（Prefix Function）
部分匹配表是一个数组π，其中π[j]表示词W中位置j之前的子串（不包括位置j的字符）的最长相同前后缀的长度（包括前缀和后缀本身为空的情况）。这个表在算法开始之前通过预处理词W得到。
算法步骤
预处理：计算词W的部分匹配表π。
匹配过程：
初始化两个指针，i指向文本S的当前位置，j指向词W的当前位置。
当i小于S的长度且j小于W的长度时，执行循环：
如果S[i]等于W[j]，则两个指针都向前移动一位（i++，j++）。
如果S[i]不等于W[j]，则j根据部分匹配表π回退到π[j-1]的位置（即j = π[j-1]），而i保持不变，继续比较。
如果j等于W的长度，说明找到了一个匹配，算法可以输出匹配的位置（通常是i-j+1，因为i已经指向了匹配词末尾的下一个字符），并根据需要继续搜索其他匹配或结束。
