目录
1.反转字符串
2.反转字符串II
3.替换数字
4.翻转字符串里面的单词
5.右旋&&左旋字符串
1.反转字符串
题目描述:
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1:
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例 2:
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
思路:
使用双指针法
对于字符串,我们定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。
注意:
注意i的限定范围
代码:
class Solution {
public:void reverseString(vector<char>& s) {int start = 0;int end = s.size() - 1;for (int i = start, j = end; i < s.size()/2; i++, j--) {swap(s[i], s[j]);}}
};
2.反转字符串II
题目描述:
给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路:
分成两部分进行处理:
1.每计数到2k个字符,或者剩余字符小于2k但是大于等于k个,就反转前k个字符
2.剩余字符少于k个,反转剩余字符
注意:
reverse接受的是迭代器参数,表示要反转的范围,接受的参数是字符串的起始位置和结束位置
代码:
/*库函数reverse的版本*/
class Solution {
public:/*reverse可以写为如下*/void reverse(string& s, int start, int end) {//接收数组s,起始元素和终止元素for (int i = start, j = end; i < j; i++, j--) {swap[s[i], s[j]];}}string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += (2 * k)) {//1.每隔2k个字符的前k个字符进行反转//2.剩余字符小于2k但是大于或者等于k个,则反转前面k个字符/*使用自定义的reverse函数的情况下*/if (i + k <= s.size()) {reverse(s, i, i + k - 1);continue;}else {//剩余字符少于k个,则将剩余字符全部反转reverse(s, i, s.size() - 1);}/*使用系统自带的库函数的情况下*/if(i+k<=s.size()){reverse(s.begin()+i,s.begin()+i+k);//reverse函数,接受两个迭代器参数,表示要反转的范围,接受的参数是字符串的起始位置和结束位置}else {reverse(s.begin()+i,s.end());}}return s;}
};
3.替换数字
题目描述:
给定一个字符串 s,它包含小写字母和数字字符,请编写一个函数,将字符串中的字母字符保持不变,而将每个数字字符替换为number。
例如,对于输入字符串 "a1b2c3",函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b",函数应该将其转换为 "anumberb"
输入:一个字符串 s,s 仅包含小写字母和数字字符。
输出:打印一个新的字符串,其中每个数字字符都被替换为了number
样例输入:a1b2c3
样例输出:anumberbnumbercnumber
数据范围:1 <= s.length < 10000。
思路:
使用双指针法
i指向新长度的末尾,j指向旧长度的末尾
从后往前遍历
先扩充数组
然后再倒序扩充(oldindex,newindex)
注意:
while是关键循环,因为需要一直执行
代码:
int main() {string s;while (cin >> s) {int count = 0;int oldindex = s.size() - 1;for (int i = 0; i < s.size(); i++) {if (s[i] >= '0' && s[i] <= '9') {count++;}}s.resize(s.size() + count * 5);int newindex = s.size() - 1;//关键循环,不断寻找符合条件的数字while (oldindex >= 0) {if (s[oldindex] >= '0' && s[oldindex] <= '9') {s[newindex--] = 'r';s[newindex--] = 'e';s[newindex--] = 'b';s[newindex--] = 'm';s[newindex--] = 'u';s[newindex--] = 'n';}//遇到不符合的情况的处理else {//此处如果写为s[newindex--] = s[oldindex--]//会报错,因为会超出oldindex范围s[newindex--] = s[oldindex];}oldindex--;}cout << s << endl;}
}
4.翻转字符串里面的单词
题目描述:
给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: "the sky is blue"
输出: "blue is sky the"
示例 2:
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
思路:
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
注意:
难度较高,条理需要清晰,先去除多余的空,然后再进行翻转处理
代码:
class Solution {void Reverse(string& s,int start,int end) {for (int i = start, j = end; i < j;i++,j--) {swap(s[i],s[j]);}}void removeextra(string& s) {int slow = 0;for (int i = 0; i < s.size(); i++) {if (s[i] != ' ') {if (slow != 0) s[slow++] = ' ';while (i < s.size() && s[i] != ' ') {s[slow++] = s[i++];}}}s.resize(slow);}string fanzhuan(string& s) {int start = 0;int end = s.size()-1;removeextra(s);Reverse(s, start,end);for (int i = 0; i <= s.size(); i++) {if (s[i] == ' ' || i == s.size()) {Reverse(s, start, i-1);start = i + 1;}}return s;}
};
5.右旋&&左旋字符串
题目描述:
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k,请编写一个函数,将字符串中的后面 k 个字符移到字符串的前面,实现字符串的右旋转操作。
例如,对于输入字符串 "abcdefg" 和整数 2,函数应该将其转换为 "fgabcde"。
输入:输入共包含两行,第一行为一个正整数 k,代表右旋转的位数。第二行为字符串 s,代表需要旋转的字符串。
输出:输出共一行,为进行了右旋转操作后的字符串。
思路:
先整体翻转
然后前k个翻转
然后后面的翻转
注意:
注意翻转的顺序
reverse接受的是迭代器的参数,要格外注意
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main() {int n;string s;cin >> n;cin >> s;int len = s.size(); //获取长度//错误做法//reverse是标准库算法,需要传递迭代器参数//接受两个参数//first:表示要翻转范围的起始位置(包括 first 指向的元素)。//last:表示要翻转范围的结束位置(不包括 last 指向的元素,即[first, last)/*reverse(start, end);reverse(start, start + k - 1);reverse(start + k, end);*/reverse(s.begin(), s.end()); // 整体反转reverse(s.begin(), s.begin() + n); // 先反转前一段,长度nreverse(s.begin() + n, s.end()); // 再反转后一段cout << s << endl;}
左旋操作与此类似
int main() {string s;int n;cin >> s;cout << "please input n";cin >> n;reverse(s.begin(), s.begin() + n);reverse(s.begin() + n, s.end());reverse(s.begin(), s.end());cout << "s ==" << s << endl;
}