526互联

[7]-代码随想录算法训练营-day8-字符串-part1

发布时间 2023-09-17 14:11:01作者: 缪白（Miubai）

代码随想录算法训练营第八天|数组字符串-part1

1.Leecode 344. 反转字符串

  1. 题目

  2. 思路

  3. 刷随想录后想法

    • 双指针，用swap

  4. 实现困难

    • 无

  5. 实现代码

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

  6. 学习收获

2.Leecode 541. 反转字符串 II

  1. 题目

  2. 思路

    • 借鉴344反转字符串

  3. 刷随想录后想法

    • 步长2k
    • 借用判定条件判断

  4. 实现困难

    • 过程理解不难，代码

  5. 实现代码

    class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)){
            //2k步长
            if (i + k <= s.size()){
                //剩余的字符大于等于k个
                reverse(s.begin() + i, s.begin() + i + k);
            }else {
                //剩下的字符不足k个
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

  6. 学习收获

    • 边界值条件判定分析

3.Leecode 05. 替换空格

  1. 题目

  2. 思路

    • 遍历，替换

  3. 刷随想录后想法

    • 统计空格，拓展原字符串空间，节省空间同时节省时间复杂度

  4. 实现困难

    • 发现题读错了。。。

  5. 实现代码

    class Solution {
public:
    string replaceSpace(string s) {
        int count = 0 ;
        int oldSize = s.size();
        for (int i = 0; i < s.size(); i++){
            if(s[i] == ' '){
                count++;
            }
        }

        //扩展s空间
        s.resize(s.size() + 2 * count);
        int newSize = s.size();

        for (int i = oldSize - 1, j = newSize -1; i < j; i--){
            if ( s[i] != ' '){
                s[j] = s[i];
                j--;
            }else{
                s[j] = '0';
                s[j - 1] = '2';
                s[j-2] = '%';
                j = j - 3;
            }
        }
        return s;
    }
};

  6. 学习收获

    • 关于c++拓展字符串空间的方法
    • 双指针关于插入字符的方法

4.Leecode 151. 反转字符串中的单词

  1. 题目

  2. 思路

    • 双指针，从尾部开始取出s的单词，存放到t字符串中

  3. 刷随想录后想法

    • 先整体翻转字符串
    • 再翻转每个单词内部字符串的字符

  4. 实现困难

    • 多余空格处理
    • 空间复杂度为O(1)
    • 边界条件处理

  5. 实现代码

    class Solution {
public:
    string deleteSpase(string s){
        //删除多余的空格
        int size = s.size();
        int slow =0;
        int fast = 0;
        for ( ; fast < size; fast++){
            if( s[fast] != ' '){
                if (slow != 0){
                    //如果不是首字母，需要加一个空格
                    s[slow] = ' ';
                    slow++;
                }
                //移动字符串
                while(s[fast] != ' ' && fast < size){
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }
            }
        }
        //需要删除多余的空间，否则会溢出
        s.resize(slow);
        return s;
    }

    void revString(string &str, int start, int end){
        //翻转传入的字符串

        for (; start < end; start++, end--){
            swap(str[start], str[end]);
        }
    }

    string reverseWords(string s) {
        s = deleteSpase(s);

        revString(s, 0, s.size()-1);
        //翻转每一个单词
        for (int fast = 0, slow = 0; fast <= s.size(); fast++){
            //slow移动规则，不仅仅只有空格，还要考虑尾部的情况
            if (s[fast] == ' ' || fast == s.size()){
                revString(s, slow, fast - 1);
                slow = ++fast;
            }
        }
        return s;
    }  
};

  6. 学习收获

    • 使用O(1)的空间思考问题
    • 两次反转字符串得到正序
    • 双指针的应用拓展
    • 同时发现本人代码相比卡哥代码在时间和内存上任然存在差距

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

  1. 题目

  2. 思路

    • for循环一个一个翻转

  3. 刷随想录后想法

    • 先翻转前n个
    • 然后翻转剩余的
    • 最后整体翻转

  4. 实现困难

  5. 实现代码

    class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

  6. 学习收获

    • get一种新的解题方法