代码随想录笔记--字符串篇

这篇具有很好参考价值的文章主要介绍了代码随想录笔记--字符串篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1--反转字符串

2--反转字符串II

3--反转字符串中的单词

4--KMP算法

5--重复的子字符串


1--反转字符串

代码随想录笔记--字符串篇,数据结构&LeetCode,数据结构

主要思路:

        双指针算法,交换两个指针的字符;

#include <iostream>
#include <vector>

class Solution {
public:
    void reverseString(std::vector<char>& s) {
        if(s.size() == 0) return;
        int l = 0, r = s.size() - 1;
        while(l < r){
            std::swap(s[l], s[r]);
            l++;
            r--;
        }
    }
};

int main(int argc, char* argv[]){
    // s = ["h","e","l","l","o"]
    std::vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    Solution S1;
    S1.reverseString(s);
    for(auto c : s) std::cout << c << " ";
    std::cout << std::endl;
    return 0;
}

2--反转字符串II

代码随想录笔记--字符串篇,数据结构&amp;LeetCode,数据结构

主要思路:

        以 2k 个字符为一组进行遍历;

#include <iostream>
#include <string>
#include <algorithm>

class Solution {
public:
    std::string reverseStr(std::string s, int k) {
        for(int i = 0; i < s.length(); i += 2*k){
            if(i + k <= s.length()) {
                std::reverse(s.begin() + i, s.begin() + i + k);
            }
            else{
                std::reverse(s.begin() + i, s.end());
            }           
        }
        return s;
    }
};

int main(int argc, char* argv[]){
    // s = "abcdefg", k = 2
    std::string test = "abcdefg";
    int k = 2;
    Solution S1;
    std::string res = S1.reverseStr(test, k);
    std::cout << res << std::endl;
    return 0;
}

3--反转字符串中的单词

代码随想录笔记--字符串篇,数据结构&amp;LeetCode,数据结构

主要思路1:

        遍历提取每一个有效的单词,存储在一个栈中,最后遍历栈连接字符串即可;空间复杂度为O(N);

#include <iostream>     
#include <stack>         
#include <string>       

class Solution {
public:
    std::string reverseWords(std::string s) {
      std::stack<std::string> stk;
      std::string tmp = "";
      for(int i = 0; i < s.length(); i++){
         if(s[i] == ' ' && tmp == "") continue; // 单词前的空格
         else if(s[i] == ' ' && tmp != ""){ // 单词间的空格
            stk.push(tmp);
            tmp = "";
         }
         else{
            tmp += s[i];
         }
      }
      stk.push(tmp); //最后一个有效单词
      std::string res;
      while(!stk.empty()){
         if(res.length() == 0) res += stk.top();
         else{
            res += " ";
            res += stk.top();
         }
         stk.pop();
      }
      return res;
    }
};

int main (int argc, char *argv[]){
   std::string test = "the sky is blue";
   Solution S1;
   std::string res = S1.reverseWords(test);
   std::cout << res << std::endl;
   return 0;
}

主要思路2:

        不使用辅助空间,要求空间复杂度为O(1);首先使用快慢指针剔除多余的空格,接着反转所有字符,最后对单词的字符进行再次反转;

#include <iostream>             
#include <string>       
#include <algorithm>

class Solution {
public:
    std::string reverseWords(std::string s) {
      //去除多余的空格(参考移除数组的元素,使用快慢指针)
      removeExtraSpace(s);
      //反转所有字符
      std::reverse(s.begin(), s.end());
      //按单词再次反转
      int start = 0;
      for(int i = 0; i < s.length(); i++){
         // 遇到单词间的空格 
         if(s[i] == ' ') {
            std::reverse(s.begin()+start, s.begin()+i);
            start = i + 1;
         }
      }
      // 反转最后一个单词
      std::reverse(s.begin()+start, s.end());
      return s;
    }

    void removeExtraSpace(std::string &s){
      int slow = 0;
      for(int fast = 0; fast < s.length(); fast++){
         if(s[fast] == ' ') continue;
         if(slow != 0){ // 单词间的空格
            s[slow] = ' ';
            slow++;
         }
         while(fast < s.length() && s[fast] != ' '){ //将非空格字符覆盖到slow的位置
            s[slow] = s[fast];
            slow++;
            fast++;
         }
      }
      s.resize(slow);
    }
};

int main (int argc, char *argv[]){
   std::string test = "the sky is blue";
   Solution S1;
   std::string res = S1.reverseWords(test);
   std::cout << res << std::endl;
   return 0;
}

4--KMP算法

数据结构笔记--KMP算法的实现

5--重复的子字符串

代码随想录笔记--字符串篇,数据结构&amp;LeetCode,数据结构

主要思路:

代码随想录笔记--字符串篇,数据结构&amp;LeetCode,数据结构文章来源地址https://www.toymoban.com/news/detail-690267.html

#include <iostream>
#include <string>
#include <algorithm>

class Solution {
public:
    bool repeatedSubstringPattern(std::string s) {
        std::string ss = s + s;
        ss = ss.substr(1, ss.size() - 2);
        if(ss.find(s) != -1) return true;
        else return false;
    }
};

int main(int argc, char* argv[]){
    // s = "abab"
    std::string test = "abab";
    Solution S1;
    bool res = S1.repeatedSubstringPattern(test);
    if(res) std::cout << "true" << std::endl;
    else std::cout << "false" << std::endl;
    return 0;
}

到了这里,关于代码随想录笔记--字符串篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包