算法训练营Day 8

344.反转字符串

题目链接：https://leetcode.cn/problems/reverse-string
文章讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
视频讲解：https://www.bilibili.com/video/BV1fV4y17748

考察点：双指针, swap

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

541. 反转字符串 II

题目链接：https://leetcode.cn/problems/reverse-string-ii/
文章讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
视频讲解：https://www.bilibili.com/video/BV1dT411j7NN

考察点：双指针

不需要搞复杂逻辑计数, 其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

class Solution {
public:
    string reverseStr(string s, int k) {
        int start;
        int end;
        for(int i=0; i< s.size(); i+=2*k){
            start = i;
            if(i + k > s.size() - 1){
                end = s.size() -1;
            }else{
                end = i+k-1;
            }
            while(start<end){
                swap(s[start],s[end]);
                start++;
                end--;
            }
        }
        return s;
    }
};

剑指 Offer 05. 替换空格

题目链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
文章讲解：https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html

考察点：双指针

首先扩充数组到每个空格替换成"%20"之后的大小,然后从后向前替换空格。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        for(auto c:s){
            if(c == ' ') count++;
        }
        int left=s.size()-1;
        // reallocate menmory
        s.resize(s.size()+count*2);
        int right=s.size()-1;
        while(count>0){
            if(s[left]!=' '){
              s[right]=s[left];
            }else{
                s[right--]='0';
                // right--;
                s[right--]='2';
                // right--;
                s[right]='%';

                count--;                
            }
            left--;
            right--;
        }
        return s;
    }
};

151. 反转字符串中的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/
文章讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
视频讲解:https://www.bilibili.com/video/BV1uT41177fX

考察点：去除空格，双指针，反转

思路：首先去除所有多余空格，再整体反转，再逐词反转。

这套代码有点啰嗦，但速度还是蛮快的。

class Solution {
public:
    string reverseWords(string s) {
        // 去除右侧空格
        int r=s.size()-1;
        while(s[r]==' '){
            r--;
        }
        s.resize(r+1);

        // 去除左侧空格
        int left = 0;
        int right = 0;
        int space_count =0;
        while(s[right]==' '){
            right++;
            space_count++;
        }
        // 去除中间空格
        while(right<s.size()){
            s[left]=s[right];
            if(s[right]==' '&& right+1 < s.size()-1 && s[right+1]==' '){
                left--;
                space_count++;
            }
            left++;
            right++;
        }
        s.resize(s.size()-space_count);  // 此时s为去掉所有多余空格的字符串
        // 翻转整个字符串
        left=0;
        right=s.size()-1;
        while(left<right){
            swap(s[left],s[right]);
            left++;
            right--;
        }
        // 翻转单词
        left = 0;
        right = 0;
        while(right<s.size()){
            int tmp;
            for(right;right<s.size();right++){
                if(s[right]==' '){
                    break;
                }
            }
            tmp = right+1;
            right--;
            while(left<right){
                swap(s[left],s[right]);
                left++;
                right--;
            }
            left=tmp;
            right=tmp;
        }
        return s;
    }
};

剑指 Offer 58 - II. 左旋转字符串

题目链接：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
文章讲解：https://programmercarl.com/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

考察点：双指针, swap

本题不难，以下方法不需要额外空间。注意定义函数的时候不要值传递，要引用传递或者指针传递

class Solution {
public:
    static void reverse(string* s,int start, int end){
        while(start<end){
            swap((*s)[start], (*s)[end]);
            start++;
            end--;
        }
    }
    string reverseLeftWords(string s, int n) {
        reverse(&s,0,s.size()-1);
        reverse(&s,0,s.size()-n -1);
        reverse(&s,s.size()-n,s.size()-1);
        return s;
    }
};