344.反转字符串
简单的开启一天刷题。
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size()-1;
while(left < right){
char temp = s[right];
s[right] = s[left];
s[left] = temp;
left++;
right--;
}
}
};
541. 反转字符串II
这道题稍微想了一下，感觉就是上一道题的变体，稍微改了一下。但觉得应该不是比较好的解法
class Solution {
public:
string smallReverse(string s){
int left = 0;
int right = s.size()-1;
while(left<right){
swap(s[left],s[right]);
left++;
right--;
}
return s;
}
string reverseStr(string s, int k) {
int do_reverse = true;
for(int i=0; i<s.length(); i=i+k){
if(do_reverse){
string reversed_piece = smallReverse(s.substr(i,k));
s.replace(i,k,reversed_piece);
do_reverse = false;
}
else{
do_reverse = true;
}
}
return s;
}
};
看了下Carl的题解，区别就是他用了reverse函数来做，这样会省些事。
剑指Offer 05.替换空格
这道题就是用了刚才刚用到的replace来替换空格的值。不知道算不算投机取巧。
class Solution {
public:
string replaceSpace(string s) {
for(int i=0;i<s.length(); i++){
if(s[i] == ' '){
s.replace(i,1,"%20");
}
}
return s;
}
};
学习了一下Carl的解法，他用了双指针去做这道题，为的是更加优化。首先遍历s，算出来有多少个空格，然后在原本的长度上加上空格数*2，然后从s的后面往前遍历。这样的话，就可以把所有的空格都换成%20了。
151.翻转字符串里的单词
连滚带爬的写了一个不用记录每一个单词再重新组合的方法。
class Solution {
public:
string reverseWords(string s) {
int word_length = 0;
int word_start = 0;
string res;
//cout<<s.length()<<endl;
for(int i=0; i<s.length(); i++){
if(s[i] != ' '){
if(word_length == 0)
word_start = i;
word_length++;
}
if(((s[i] == ' ')||(i == s.length()-1)) && (word_length!=0)){
res = s.substr(word_start,word_length)+" "+res;
word_length = 0;
}
}
return res.substr(0,res.length()-1);
}
};
Carl的解法是先去除多余的空格，然后整体的s进行reverse，然后在挨个单词把它们在逐一reserve回原来单词的顺序。
这里关于去除多余的空格，Carl用了之前题里用到的快慢指针，这样比erase的效率要高。等有空的时候，应该自己手动写一下这个去除空格的方法。
剑指Offer58-II.左旋转字符串
这是道很简单的题，代码如下。
class Solution {
public:
string reverseLeftWords(string s, int n) {
string first_part = s.substr(0,n);
string second_part = s.substr(n,s.length()-n);
return second_part+first_part;
}
};
看了Carl提出的不用额外空间，只在string上修改的要求后，瞄了眼提示，也写出来了。用到了上一题的reserve解法。
class Solution {
public:
string reverseLeftWords(string s, int n) {
int range = s.length()-n;
reverse(s.begin(), s.end());
reverse(s.begin(), s.begin()+range);
reverse(s.begin()+range, s.end());
return s;
}
};
