1、344反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

  • 左右双指针

我的思路： 这道题很常规的问题，直接左右双指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0,right = s.size()-1;
        while(left<right){
            auto temp = s[right];
            s[right] = s[left];
            s[left] = temp;
            left++;
            right--;
        }
    }
};

2、541反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

我的思路： 这道题和上一道题类似，都是反转字符串，只是这道题是分区域反转。直接使用左右双指针一个一个区域的反转就行。

代码随想录： 直接用了for循环，非主要考察的部分可以直接用库函数，例如reverse

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
class Solution {
public:
    string reverseStr(string s, int k) {
        int left = 0, right = k-1;
        while(left < s.size()){
            right = right < s.size()?right:s.size()-1;
            int i =left,j = right;
            while(i<j){
                auto temp = s[j];
                s[j] = s[i];
                s[i] = temp;
                i++;
                j--;
            }
            left = left+2*k;
            right = left+k-1;
        }
        return s;
    }
};
// 代码随想录
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

3、卡码网-54替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

我的思路： 我想的就是很简简单方法，直接依次遍历，遇到数字就换成number，结果用一个新字符串存储。
代码随想录： 做到极致，不申请多余的临时变量。如果不申请临时的空间在原来的上面修改时会覆盖那些还没有遍历过的字符，核心还是解决覆盖问题。 在88合并两个有序数组中遇到过类似的做法，从后往前排就可以避免覆盖。

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
54
55
#include <string>
#include <iostream>
using namespace std;

void transNum(string &str){
    string temp;
    for(int i = 0;i<str.size();i++){
        if('0'<=str[i]&& str[i]<='9'){
            temp+="number";
        }else{
            temp+=str[i];
        }
    }
    str = std::move(temp);
}

int main(){
    string str;
    std::cin >> str;
    transNum(str);
    std::cout << str;
}
//代码随想录
#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int sOldIndex = s.size() - 1;
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1;
        // 从后往前将数字替换为"number"
        while (sOldIndex >= 0) {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            } else {
                s[sNewIndex--] = s[sOldIndex];
            }
            sOldIndex--;
        }
        cout << s << endl;       
    }
}