C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！
文章目录
- 一、反转字符串（力扣344）
- 二、反转字符串 II（力扣541）
- 三、替换数字（卡码网 54）
- 四、翻转字符串里的单词（力扣151）
- 五、右旋字符串（卡码网 55）
- 六、找出字符串中第一个匹配项的下标（力扣28）
- 七、重复的子字符串（力扣459）
一、反转字符串（力扣344）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]
提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符
class Solution {
public:
void reverseString(vector<char>& s) {
// 双指针解决
int begin =0;
int end = s.size()-1;
while(begin<end){
// 交换
char temp = s[begin];
s[begin] = s[end];
s[end] = temp;
begin++;
end--;
}
}
};
二、反转字符串 II（力扣541）
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”
示例 2：
输入：s = “abcd”, k = 2
输出：“bacd”
提示：
1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104
class Solution {
public:
string reverseStr(string s, int k) {
// 每2k个字符移动一次i
for(int i=0;i<s.length();i+=2*k){
// 翻转前k个
if(i+k<s.size()){ // i+k<s.size说明 k<i.size<2*k,需要翻转前k个
reverse(s.begin()+i,s.begin()+i+k);
}
else{
// 将最后所有的剩余元素都翻转
reverse(s.begin()+i,s.begin()+s.size());
}
//
}
return s;
}
};
三、替换数字（卡码网 54）
题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串，其中每个数字字符都被替换为了number
输入示例
a1b2c3
输出示例
anumberbnumbercnumber
提示信息
数据范围：
1 <= s.length < 10000。
#include <iostream>
using namespace std;
int main() {
string inputS;
cin >> inputS;
int count = 0;
// 遍历原来数组,记录其中数字的个数
for (int i = 0; i < inputS.length(); i++) {
if (inputS[i] <= '9' && inputS[i]>='0') {
count++;
}
}
int FLength = inputS.length();
// resize 原来的字符串
inputS.resize(FLength + count * 5);
// 替换原来字符串中的字符，从后向前替换
int j = inputS.length()-1;
for (int i = FLength - 1; j>i; i--,j--) {
if (inputS[i] <= '9' && inputS[i]>='0') {
// 是数字要替换
inputS[j] = 'r';
inputS[j-1] = 'e';
inputS[j-2] = 'b';
inputS[j-3] = 'm';
inputS[j-4] = 'u';
inputS[j-5] = 'n';
j -= 5;
}
else {
inputS[j] = inputS[i];
}
}
cout << inputS << endl;
system("pause");
return 0;
}
四、翻转字符串里的单词（力扣151）
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
class Solution {
public:
string reverseWords(string s) {
// 去除空格
removeSpace(s);
// // 翻转整个句子
reverse(s.begin(), s.end());
// 翻转每个单词
// 首先找到每个单词的位置
int slow=0;
for(int fast=0;fast<s.length();fast++){
if(s[fast+1]==' ' || fast==s.length()-1){
reverseWord(s,slow,fast);
slow = fast+2;
}
}
return s;
}
// 翻转每个单词
void reverseWord(string& s, int begin, int end) {
while (begin < end) {
swap(s[begin], s[end]);
begin++;
end--;
}
}
// 去除字符串中多余的空格
void removeSpace(string& s) {
// 快慢指针去除空格
int slow = 0;
for (int fast = 0; fast < s.length(); fast++) {
if (s[fast] != ' ') {
// 不为空格才进行下面的操作
// 添加每个单词之间的空格，句子开头不加
if (slow != 0) {
s[slow] = ' ';
slow++;
}
while (fast<s.size() && s[fast] != ' ') {
s[slow] = s[fast];
slow++;
fast++;
}
}
}
s.resize(slow);
}
};
五、右旋字符串（卡码网 55）
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
2
abcdefg
输出示例
fgabcde
提示信息
数据范围：
1 <= k < 10000,
1 <= s.length < 10000;
#include <iostream>
using namespace std;
#include<algorithm>
string func(string s,int k){
reverse(s.begin(),s.end());
reverse(s.begin(),s.begin()+k);
reverse(s.begin()+k,s.end());
return s;
}
int main(){
int k;
string s;
cin>>k>>s;
s = func(s,k);
cout<<s<<endl;
return 0;
}
六、找出字符串中第一个匹配项的下标（力扣28）
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
class Solution {
public:
int strStr(string haystack, string needle) {
// 剪枝操作
int hLength = haystack.length();
int nLength = needle.length();
if(needle.length()>haystack.length()){
return -1;
}
// 在haystack中找 neddle
for(int i=0;i<hLength-nLength+1;i++){
if(haystack[i]==needle[0]){
// 定义两个指针
int h=i;
int n=0;
int flag =0;
while(n<nLength){
if(haystack[h]==needle[n]){
h++;
n++;
}
else{
flag = 1;
break;
}
}
if(flag==0){
return i;
}
}
}
return -1;
}
};
七、重复的子字符串（力扣459）
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s = “aba”
输出: false
示例 3:
输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
提示：
1 <= s.length <= 104
s 由小写英文字母组成
class Solution {
public:
bool repeatedSubstringPattern(string s) {
// 两个拼在一起
string addS = s+s;
// 掐头去尾
addS.erase(addS.begin());
addS.erase(addS.end()-1);
if(addS.find(s)!=std::string::npos){
return true;
}
return false;
}
};
![[NSSRound#16 Basic]Web](https://img-blog.csdnimg.cn/direct/ef5a53f569624c988fe3ecab0833b05d.png)
