怎样做网站的反链,好网站建设公司有多少,深圳做外贸网站哪家好,网站ip解析文章目录 前言一、最长回文子串1.题目解析2.算法原理3.代码编写 二、字符串相乘1.题目解析2.算法原理3.代码编写 总结 前言
一、最长回文子串
1.题目解析
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。
示例 1#xff1a; 输入#xff1a;s “babad” 输出找到 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 begin0;int len0;int ns.size();for(int i0;in;i){int lefti;int righti;//奇数长度while(left0rightn-1s[left]s[right]){left--;right;}if(right-left-1len){beginleft1;lenright-left-1;}//偶数lefti;righti1;while(left0rightn-1s[left]s[right]){left--;right;}if(right-left-1len){beginleft1;lenright-left-1;}}return s.substr(begin,len);}
};二、字符串相乘
1.题目解析
43. 字符串相乘
2.算法原理
我们可以按照正常加减法进行进位计算但是会很麻烦 无进位相乘然后相加最后处理进位。 我们需要对两个数组进行逆序。 同时处理前导0的场景。
我们利用一个数组进行存储二者相乘结果正好可以放在下标相加的位置。
3.代码编写
class Solution {
public:string multiply(string num1, string num2) {int mnum1.size();int nnum2.size();//两个字符串逆序reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());//数组存储vectorintv(mn-1);//无进位相乘并相加for(int i0;im;i){for(int j0;jn;j){//转化成数字v[ij](num1[i]-0)*(num2[j]-0);}}//处理进位int cur0;//遍历vint t0;//记录进位string ret;//可能单独进位while(curmn-1||t){if(curmn-1) tv[cur];rett%100;t/10;}//处理前导0while(ret.size()1ret.back()0) ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};总结
以上就是今天要讲的内容 。希望对大家的学习有所帮助仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
