Day11 344反转字符串 541反转字符串II 替换数字 151 反转字符串中的单词

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"]

? ? ? ? ?本题是字符串章节的第一题，首先想到的是直接调用库函数reverse，传入起始和节数迭代器即可，但是对我们没有太大的训练帮助，代码如下；

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(),s.end());
    }
};

? ? ? ? ?这里我们从头开始写，在反转链表里，我们采用了双指针的方法，那么反转字符串的时候，是否也能采用这个方法呢，因为字符串也是一种数组，在内存中是连续分布的，所以会更简单一些，定义两个指针，一个在字符串前面，一个在字符串后面，一直交换直到抵达中间，时间复杂度为n，代码如下：

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

? ? ? ? 其中，swap是个典型的交换函数，比较好写，这里也不过多的赘述了。

?541 反转字符串II

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

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

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

? ? ? ? 这道题也是模拟，不涉及算法，但是刚开始读题的时候可能会读不懂，大体意思就是如果每次的一批数据为2k，那就反转前k个，如果小于k，那就全反转，如果不到2k但是大于k，那就反转前k个，仔细一看还是比较乱的。

? ? ? ? 但是肯定要用循环来遍历元素，既然如此，每次i++以后要证明处理呢，还要搞一个计数器，这就比较麻烦了，既然如此，不如每次就遍历2k个，这样就高效遍历了。如果i+k小于等于size，那就说明此次能够反转这次遍历的k个元素，而不需要全部反转。如果i+k大于size了，那就说明要反转元素一定小于k个了，此时将后面的元素全部都反转即可。总的来说，主要就是看这次是要反转k个元素还是要反转剩余的所有元素。这个i+k就是要看剩下的元素够不够了。同时注意，如果使用reverse，默认的迭代器是左闭右开的，所以要注意取值的范围。时间复杂度为n，代码如下：

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;
    }
};

? ? ? ? 同时，本题也可以不适用库函数reverse，而是可以自己写一个，这样就不需要考虑迭代器的左闭右开了，而是变成左闭右闭。代码如下：

class Solution {
public:
    void reverse(string& s, int start, int end) {
        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 个字符
            if (i + k <= s.size()) {
                reverse(s, i, i + k - 1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s, i, s.size() - 1);
        }
        return s;
    }
};

? ? ? ? 还有一种解题思路：定义一个pos指针，用while循环，当指针还在字符串里的时候就持续循环，中间过程和上面同理，最后每次让pos+2k的长度，其实和上面的for循环差不太多。

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size(),pos = 0;
        while(pos < n){
            //剩余字符串大于等于k的情况
            if(pos + k < n) reverse(s.begin() + pos, s.begin() + pos + k);
            //剩余字符串不足k的情况 
            else reverse(s.begin() + pos,s.end());
            pos += 2 * k;
        }
        return s;
    }
};

替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

? ? ? ? 本题我的想法是创建一个新的字符串，遍历s，对于数字和字母分别给新的result字符串赋不同的值，最后打印出来即可，代码如下：

#include<iostream>
using namespace std;

int main()
{
    string s;
    while(cin>>s)
    {
        string result;

        for(int i = 0; i <s.size();i++)
        {
            if(s[i] >=  '0' && s[i]<= '9')
            {
                result += 'n';
                result += 'u';
                result += 'm';
                result += 'b';
                result += 'e';
                result += 'r';
            }
            else
            {
                result += s[i];
            }
        }
        for(auto i : result)
            cout<<i;
        cout<<endl;
    }
}

? ? ? ? 本题还可以使用双指针法：

?????????先扩充字符串的大小，之后从后向前替换数字字符，也就是双指针法，i指向新长度的末尾，j指向就长度的末尾，遇到数字和字母分别采用不同的移动方法。为什么不从前向后填充呢，因为这样的话，每次添加元素都要讲添加元素之后的所有元素整体向后移动。

? ? ? ? 这样做有两个好处：不用申请新的数组，避免移动问题。

? ? ? ? 时间复杂度为n，代码如下：

#include<iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int count = 0; // 统计数字的个数
        int sOldSize = s.size();
        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 sNewSize = s.size();
        // 从后先前将空格替换为"number"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] > '9' || s[j] < '0') {
                s[i] = s[j];
            } else {
                s[i] = 'r';
                s[i - 1] = 'e';
                s[i - 2] = 'b';
                s[i - 3] = 'm';
                s[i - 4] = 'u';
                s[i - 5] = 'n';
                i -= 5;
            }
        }
        cout << s << endl;
    }
}

151 反转字符串中的单词

?

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出:?"blue is sky the"

示例 2：
输入: " ?hello world! ?"
输出:?"world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good ? example"
输出:?"example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

?????????首先假设空格问题解决，我们要怎么处理呢，可以先将整个字符串反转过来，再把每一个单词反转一下，利用两个reverse函数就可以解决，重点是处理空格的问题。

? ? ? ? 移除空格可以使用erase函数，分前中后分别删除不同区域多余的空格，但是erase的时间复杂度就已经是n了，外面嵌套循环就变成了n2，代码如下：

void removeExtraSpaces(string& s) {
    for (int i = s.size() - 1; i > 0; i--) {
        if (s[i] == s[i - 1] && s[i] == ' ') {
            s.erase(s.begin() + i);
        }
    }
    // 删除字符串最后面的空格
    if (s.size() > 0 && s[s.size() - 1] == ' ') {
        s.erase(s.begin() + s.size() - 1);
    }
    // 删除字符串最前面的空格
    if (s.size() > 0 && s[0] == ' ') {
        s.erase(s.begin());
    }
}

? ? ? ? 这是我们想到了之前的移除元素那道题，用的快慢双指针法，这题也可以尝试一下，同样分为前中后分别删除空格，代码如下：

//版本一 
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
            continue;
        } else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}

? ? ? ? 这段代码其实还可以继续优化：直接去除所有空格，并在相邻单词之间添加空格，最外层的for循环是遍历快指针fast（i），之后如果遇到非空格就进行处理，因为这是本次第一次遇到非空格，所以slow要在前面再补一个空格，之后开始读取这一整个单词，fast和slow同时向前移动，直到最后将字符串重组为slow的大小。

// 版本二 
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
    int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
            if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
            while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow); //slow的大小即为去除多余空格后的大小。
}

? ? ? ? 总的代码如下所示：时间复杂度为n。

class Solution {
public:
    string delete_space(string &s)
    {
        int slow = 0;
        for(int fast = 0; fast < s.size(); fast++)
        {
            if(s[fast] != ' '){
                if(slow != 0)
                    s[slow++] = ' ';
                while(fast < s.size() && s[fast] != ' ')
                    s[slow++] = s[fast++];
            }
        }
        s.resize(slow);
        return s;
    }

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

????????这里我是采用了库函数里的reverse，我们也可以自己定义一个reverse，代码如下：

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};