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

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

1.Leecode 344. 反转字符串

1. 题目

   • https://leetcode.cn/problems/reverse-string/

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. 题目

   • https://leetcode.cn/problems/reverse-string-ii/

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. 题目

   • https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

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. 题目

   • https://leetcode.cn/problems/reverse-words-in-a-string/

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. 题目

   • https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

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一种新的解题方法