string经典题目(C++)

文章目录

• 前言
• 一、最长回文子串
• • 1.题目解析
  • 2.算法原理
  • 3.代码编写
• 二、字符串相乘
• • 1.题目解析
  • 2.算法原理
  • 3.代码编写
• 总结

---

前言

一、最长回文子串

1.题目解析

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

2.算法原理

中心扩展算法

回文串有这样一个特点，从中间劈开，两边对称。
固定一个中心点，从中心点开始，向两边扩展。
奇数长度和偶数长度都需要考虑。

3.代码编写

class Solution {
public:
    string longestPalindrome(string s) 
    {
        //中心扩展算法
        int begin=0;
        int len=0;
        int n=s.size();
        for(int i=0;i<n;i++)
        {
            int left=i;
            int right=i;
            //奇数长度
            while(left>=0&&right<=n-1&&s[left]==s[right])
            {
                left--;
                right++;
            }
            if(right-left-1>len)
            {
                begin=left+1;
                len=right-left-1;
            }
            //偶数
            left=i;
            right=i+1;
            while(left>=0&&right<=n-1&&s[left]==s[right])
            {
                left--;
                right++;
            }
            if(right-left-1>len)
            {
                begin=left+1;
                len=right-left-1;
            }

        }
        return s.substr(begin,len);
    }
};

二、字符串相乘

1.题目解析

43. 字符串相乘

2.算法原理

我们可以按照正常加减法进行进位计算，但是会很麻烦，

无进位相乘然后相加，最后处理进位。

我们需要对两个数组进行逆序。

同时处理前导0的场景。

我们利用一个数组进行存储，二者相乘结果正好可以放在下标相加的位置。

3.代码编写

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        int m=num1.size();
        int n=num2.size();
        //两个字符串逆序
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        //数组存储
        vector<int>v(m+n-1);

        //无进位相乘并相加
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                //转化成数字
                v[i+j]+=(num1[i]-'0')*(num2[j]-'0');
                
            }
        }
        //处理进位
        int cur=0;//遍历v
        int t=0;//记录进位
        string ret;
        //可能单独进位
        while(cur<m+n-1||t)
        {
            if(cur<m+n-1) t+=v[cur++];
            ret+=t%10+'0';
            t/=10;
        }
        
        //处理前导0
        while(ret.size()>1&&ret.back()=='0') ret.pop_back();

        reverse(ret.begin(),ret.end());
        return ret;
    }
};

总结

以上就是今天要讲的内容 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ ???? ???? ????