string经典题目(C++)

---

前言

一、最长回文子串

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;//遍历vint t=0;//记录进位string ret;//可能单独进位while(cur<m+n-1||t){if(cur<m+n-1) t+=v[cur++];ret+=t%10+'0';t/=10;}//处理前导0while(ret.size()>1&&ret.back()=='0') ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};

总结

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