代码随想录算法训练营Day8 | 字符串part01

344.反转字符串

leetcode链接
代码随想录链接
一刷状态：通过

思路

思路简单，从两边向中间遍历，交换两边的元素。

class Solution {
public:
    void swap(char& a, char& b)
    {
        char temp = a;
        a = b;
        b = temp;
    }

    void reverseString(vector<char>& s) {
        for(int i = 0; i<s.size()/2; i++)
        {
            swap(s[i], s[s.size()-1-i]);
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

541. 反转字符串II

leetcode链接
代码随想录链接
一刷状态：通过

思路

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i<s.size(); i+=2*k)
        {
            if(i+k<s.size())
            {
                reverse(s.begin()+i, s.begin()+i+k);
            }
            else
            {
                reverse(s.begin()+i, s.end());
            }
                
        }
        return s;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

替换数字

卡码网题目链接
代码随想录链接
一刷状态：未解出（思路不清晰）

思路

先扩充空间，再从后往前填充number。

#include<iostream>
#include<string>

using namespace std;

int main()
{
    string str;
    int nums = 0;
    cin>>str;
    
    for(auto s:str)
    {
        if(s>='0'&&s<='9') nums++;
    }
    
    if(nums==0) 
    {
        cout<<str;
        return 0;
    }
    
    int f = str.size()-1;
    
    str.resize(nums*5+f+1);
    
    int b = str.size()-1;
    
    while(f<b)
    {
        if(str[f]>='0'&&str[f]<='9')
        {
            str[b--] = 'r';
            str[b--] = 'e';
            str[b--] = 'b';
            str[b--] = 'm';
            str[b--] = 'u';
            str[b--] = 'n';
            f--;
            
        }
        else
        {
            str[b--] = str[f];
            f--;
        }
        
    }
    
    cout<<str;
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

151.翻转字符串里的单词

leetcode链接
代码随想录链接
一刷状态：通过（思路不够清晰）

思路

• 移除多余空格
  • 跳过前面的空格
  • 使用双指针法，遇到字母前的空格则保留空格，其余都跳过
  • 补充最后是空格的情况，因为只遍历到s.size()-1
• 将整个字符串反转
• 将每个单词反转

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        // 除去多余的空格
        // 跳过前面的空格
        int k = 0;
        while(s[k]==' '){k++;}

        // 使用双指针法，遇到字母前的空格则保留空格，其余都跳过
        int j = 0;
        for(int i=k; i<s.size()-1; i++)
        {
            if(s[i]!=' ')
            {
                s[j++] = s[i]; 
            }
            else if(s[i]==' '&&s[i+1]!=' ')
            {
                s[j++] = ' ';
            }
        }
        // 补充最后是空格的情况，因为只遍历到s.size()-1
        if(s[s.size()-1]!=' ') s[j++] = s[s.size()-1]; 
        s.resize(j);

        int start = 0;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]==' ')
            {
                reverse(s.begin()+start, s.begin()+i);
                start = i+1;
            }
        }
        reverse(s.begin()+start, s.end());
        return s;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

右旋字符串

卡码网题目链接
代码随想录链接
一刷状态：未通过（思路不清晰）

思路：

各自翻转，然后再整体翻转

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    string s;
    
    cin>>n>>s;
    
    // 各自翻转，然后再整体翻转
    reverse(s.begin(), s.end()-n);
    reverse(s.end()-n, s.end());
    reverse(s.begin(), s.end());
    
    cout<<s;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21