右旋字符串
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出共一行，为进行了右旋转操作后的字符串。
数学问题，模拟即可。
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
int k;
cin >> k;
string s;
cin >> s;
int n = s.size();
k %= n; // 处理 k 大于字符串长度的情况
int count = 0; // 跟踪已处理的字符数
for (int start = 0; count < n; ++start) {
char temp = s[start];
int current = start;
do {
int next = (current + k) % n;
swap(temp, s[next]);
current = next;
count++;
} while (current != start); // 完成一个循环
}
cout << s;
}
151 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
此题为2025年中国科学技术大学计算机学院夏令营机试真题。
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]);
}
void removeExtraSpaces(string& s) {
int i = 0;
while (i < s.size()) {
if (i > 0 && s[i] == s[i – 1] && s[i] == ' ') {
s.erase(s.begin() + i);
}
else i++;
}
if (s[0] == ' ') s.erase(s.begin());
if (s[s.size() – 1] == ' ') s.erase(s.begin() + s.size() – 1);
}
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() – 1);
int start = 0;
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') {
reverse(s, start, i – 1);
start = i + 1;
}
}
return s;
}
};
28 找出字符串第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
板子题，KMP老生常谈。这个版本代码的j表示匹配前缀后缀长度。
class Solution {
public:
int strStr(string haystack, string needle) {
return kmp(haystack, needle);
}
int kmp(string text, string pattern) {
int results = -1;
int n = text.length();
int m = pattern.length();
if (m == 0) return results;
vector<int> next = getNext(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) j = next[j – 1];
if (text[i] == pattern[j]) j++;
if (j == m) return i – m + 1;
}
return -1;
}
vector<int> getNext(const string& pattern) {
int m = pattern.length();
vector<int> next(m);
next[0] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[j] != pattern[i]) j = next[j – 1];
if (pattern[i] == pattern[j]) j++;
next[i] = j;
}
return next;
}
};
459 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
进行数学上的一些处理即可。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
vector<int> next = getNext(s);
int length = next[s.length() – 1];
if (length == 0) return false;
int err = s.length() – length;
if (s.length() % err == 0) return true;
else return false;
}
vector<int> getNext(const string& pattern) {
int m = pattern.length();
vector<int> next(m);
next[0] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[j] != pattern[i]) j = next[j – 1];
if (pattern[i] == pattern[j]) j++;
next[i] = j;
}
return next;
}
};
