代码随想录算法训练营第八天| 344.反转字符串、541. 反转字符串II、卡码网：54.替换数字 、 151.翻转字符串里的单词、卡码网：55.右旋转字符串

双指针、三数之和、四数之和、剪枝去重
最重要的收获是如何适当的去重

344.反转字符串

思路：
1、相向指针向内交换

代码实现

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size()-1;
        int tempNum;
        while(left < right){
            tempNum = s[left];
            s[left] = s[right];
            s[right] = tempNum;
            left++, right--;
        }
    }
};

541. 反转字符串II

问题关键：

1. 在遍历数组时判断剩余字符大小
2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符；剩余字符少于 k 个，则将剩余字符全部反转。
3. 交换操作与344.反转字符串相似

代码实现

class Solution {
public:
    void reverse(string &s, int left, int right) {
        char tempNum;
        while(left < right){
            tempNum = s[left];
            s[left] = s[right];
            s[right] = tempNum;
            left++, right--;
        }
    }
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i=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;
    }
};

卡码网：54.替换数字

代码实现

using namespace std;

void THnumber(string s){
    string newS = "";
    for(char c : s){
        if(c < 'a' || c > 'z') {
            newS += "number";
            //cout << "number";
        }
        else{
            newS += c;
            //cout << c;
        }
    }
    cout << newS << endl;
}

int main(){
    string s;
    cin >> s;
    THnumber(s);

151.翻转字符串里的单词

问题关键信息：

1. 单词顺序颠倒,单词内部字符的顺序不可以变
2. s中可能会存在前导空格、尾随空格或者单词间的多个空格。

思路：
1、遍历数组确认每个单词首尾的下标，然后保存进新字符串
2、确认每个单词首尾的下标：
当前元素是空格，而且前一个元素非空格，则前一位为某个单词的末尾字符；
当前元素非空格，而且前一个元素是空格，则当前元素为某个单词的首端字符
3、特殊情况下确认每个单词首尾的下标：
特殊情况一：字符串末尾无空格
特殊情况二：字符串首端无空格

代码实现

class Solution {
public:
    string reverseWords(string s) {
        string newS = "";

        int fast = s.size()-1;
        int start, end;
        //特殊情况一：字符串末尾无空格
        if(s[fast] != ' ') end = fast;
        for(fast; fast > 0;fast--){
            if(s[fast] == ' '){
                if(s[fast-1] != ' '){//当前元素是空格，而且前一个元素非空格，则前一位为某个单词的末尾字符
                    end = fast-1;
                }
            }
            else{
                if(s[fast-1] == ' '){//当前元素非空格，而且前一个元素是空格，则当前元素为某个单词的首端字符
                    start = fast;
                    for(int i = start; i <= end; i++){
                        newS += s[i];
                    }
                    newS += ' ';
                }
            }
        }
        //特殊情况二：字符串首端无空格
        if(s[0] != ' '){
            start = 0;
            for(int i = start; i <= end; i++){
                        newS += s[i];
            }
            newS += ' ';
        }

        newS.resize(newS.size()-1);
        return newS;
    }
};