【LeetCode】【C++】string OJ必刷题

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》

🌝每一个不曾起舞的日子，都是对生命的辜负

目录

前言

【LeetCode】415.字符串相加

【LeetCode】43.字符串相乘 

 【LeetCode】125.验证回文字符串

【LeetCode】541.反转字符串Ⅱ

【LeetCode】557.反转字符串中的单词Ⅲ

前言

利用string的一些常用方法解题，本篇文章不乏有你眼前一亮的优秀方法，欢迎大家订阅。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码：🌟fanfei_c的仓库🌟

=========================================================================

【LeetCode】415.字符串相加

=================================原题链接=================================

415. 字符串相加https://leetcode.cn/problems/add-strings/

 =========================================================================

题目：

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

实际应用中，可能会有一些非常大的数字要求进行计算，甚至long long类型都无法容纳。

那么此时我们就需要利用字符串，简称“大数运算”。

思路：

实际上就是简单的加法的思路，主要难点在于如何控制进位。

代码实现（未优化）：

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1=num1.size()-1,end2=num2.size()-1;
        string retStr;
        int next=0;
        
        while(end1>=0 || end2>=0)
        {      
            int val1=0,val2=0;   
            if(end1>=0)
                val1=num1[end1--]-'0';//拿到末尾数字
            if(end2>=0)
                val2=num2[end2--]-'0';//拿到末尾数字
            int ret=val1+val2+next;
            next=ret/10;//得到进位
            ret%=10;//得到该位计算结果
            retStr.insert(retStr.begin(),'0'+ret);
        }
        if(next==1)//如果进位有剩余，不要忘记进位补充到数字中
        {
            retStr.insert(retStr.begin(),'1');
        }
        return retStr;
    }
};

 为什么时间复杂度会这么高呢？

实际上是因为insert方法，整个算法最后的时间复杂度为O(N^2)，insert为头插，每次头插都需要挪动后面的元素，这也是导致了时间复杂度偏高的原因，那么如何解决呢？

优化思路：

• 我们知道尾插在这里的效率肯定是强于头插的，唯一需要解决的问题就是尾插得到的字符串是“反”的，那我们只需要调用reverse方法翻转字符串即可。

  代码实现（优化）：

  class Solution {
  public:
      string addStrings(string num1, string num2) {
          int end1 = num1.size() - 1, end2 = num2.size() - 1;
          string retStr;
          int next = 0;
          while (end1 >= 0 || end2 >= 0)
          {
              int val1 = 0, val2 = 0;
              if (end1 >= 0)
                  val1 = num1[end1--] - '0';
              if (end2 >= 0)
                  val2 = num2[end2--] - '0';
              int ret = val1 + val2 + next;
              next = ret / 10;
              ret %= 10;
              retStr += (ret + '0');
          }
          if (next == 1)//如果有剩余进位则尾插剩下的进位数字
          {
              retStr += '1';
          }
          reverse(retStr.begin(), retStr.end());
          return retStr;
      }
  };

  ---

  

  ---

  【LeetCode】43.字符串相乘 

  =================================原题链接=================================

  43.字符串相乘 https://leetcode.cn/problems/multiply-strings/description/

   =========================================================================

  题目：

  给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

  注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

  

  ---

   思路：

  乘法的进位与加法有相似之处，但不好控制的是被乘数乘以乘数的每一位所得到的结果需要错位相加。

  比如：

  

  代码实现：

  class Solution {
  public:
      //乘方法
      string multiply(string num1, string num2) {
          int end1 = num1.size() - 1, end2 = num2.size() - 1;
          string reg;
          int next = 0;
          string retStr;
          //判断是否有字符串为0，如有直接输出0
          if(num1=="0")
          {
              return num1;   
          }
          if(num2=="0")
          {
              return num2;
          }
          while (end2 >= 0)//双层循环，因为根据乘法，我们知道被乘数每个数字都要被乘数乘
          {
              while (end1 >= 0)//内层循环得到的reg是被乘数乘个/十/百/···的结果
              {
                  int val1 = 0, val2 = 0;
                  if (end1 >= 0)
                      val1 = num1[end1--] - '0';
                  val2 = num2[end2] - '0';
                  int ret = val1 * val2 + next;
                  next = ret / 10;
                  ret %= 10;
                  reg += (ret + '0');
              }
              if (next != 0)//将未加的进位补上
              {
                  reg += (next + '0');
              }
              reverse(reg.begin(), reg.end());//由于之前在尾插，数字为反着的，所以这里反转回来
              //之前采用尾插是因为尾插的复杂度低于头插
              
              //这步是为了错位相加用，比如当被乘数乘乘数的十位得到的数字，应该比被乘数乘乘数的个位多一位0，才能保证乘法逻辑的正确
              for (int i = 0; i  
   【LeetCode】125.验证回文字符串
   
  =================================原题链接=================================
   
  125.验证回文字符串https://leetcode.cn/problems/valid-palindrome/description/
   
   =========================================================================
   
   
   
  题目：
   
   
  如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
   
   
  字母和数字都属于字母数字字符。
   
   
  给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
   
   
   
  判断回文是我们的老朋友了，利用左右指针即可轻松解决，需要注意的无非就是字符的转化。
   
  代码实现：
   
  class Solution {
  public:
      bool isDigtalOrWord(char ch)
      {
          if ((ch >= '0' && ch = 'A' && ch = 'a' && ch