个人备案网站做淘宝客,福田瑞沃q5,武冈网站建设多少钱,大专电子商务主要学什么快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、最长公共前缀二、最长回文子串三、二进制求和四、字符串相乘 引言
字符串题#xff0c;大多数是模… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、最长公共前缀二、最长回文子串三、二进制求和四、字符串相乘 引言
字符串题大多数是模拟题或者考察其他算法。通过本专题了解字符串题型的函数接口和常用做法。
一、最长公共前缀 思路
先处理边界数组为空返回空串先用字符串tmp存储第一个字符串再与其他字符串两两比较保留相同的部分比较完后最后保留下来的tmp即为最长公共前缀
class Solution
{
public:string longestCommonPrefix(vectorstring strs){if(strs.size() 0) return ;string tmp strs[0];for(int i1; istrs.size(); i){int cur 0;while(cur tmp.size() cur strs[i].size() tmp[cur] strs[i][cur]){cur;}tmp.resize(cur);}return tmp;}
};二、最长回文子串 思路
中心扩展算法暴力解法的优化利用了回文串对称的性质进行枚举遍历字符串对于每一个位置分别进行奇数长度和偶数长度的枚举分别进行结果更新注意遍历的过程中只记录起始位置和长度最后再创建子串
class Solution
{
public:string longestPalindrome(string s){int pos 0, len 0;for(int i0; is.size(); i){int left1 i, right1 i;//奇数个while(left1 0 right1 s.size() s[left1] s[right1]){left1--;right1;}if(right1 - left1 - 1 len){pos left1 1;len right1 - left1 - 1;}int left2 i, right2 i 1;//偶数个while(left2 0 right2 s.size() s[left2] s[right2]){left2--;right2;}if(right2 - left2 - 1 len){pos left2 1;len right2 - left2 - 1;}}return s.substr(pos, len);}
};三、二进制求和 思路
高精度加法分别从两个字符串的尾部开始向前遍历模拟列竖式的过程如果cur1、cur2存在则取出对应位置的数字否则返回0将取出的数字与进位相加再进行取模和整除操作更新结果字符串和进位循环条件两个字符串没遍历完或者进位不为0只要有一个满足则循环继续最后逆置字符串返回
class Solution
{
public:string addBinary(string a, string b){string s;int cur1 a.size() - 1, cur2 b.size() - 1, carry 0;while(cur1 0 || cur2 0 || carry){int n1 cur1 0 ? a[cur1--] - 0 : 0;int n2 cur2 0 ? b[cur2--] - 0 : 0;int n n1 n2 carry;s n % 2 0;carry n / 2;}reverse(s.begin(), s.end());return s;}
};四、字符串相乘 思路
高精度乘法先无进位相乘再处理进位最后处理前导零无进位相乘开辟tmp数组大小为m n - 1分别从两个字符串的尾部开始向前遍历对应下标i j进行无进位相乘处理进位从后向前遍历tmp数组处理进位的同时更新结果字符串处理前导零当结果字符串长度大于1且尾部为零尾删逆置字符串返回
class Solution
{
public:string multiply(string n1, string n2){//无进位相乘int m n1.size(), n n2.size();vectorint tmp(m n - 1);for(int im-1; i0; i--){for(int jn-1; j0; j--){tmp[i j] (n1[i] - 0) * (n2[j] - 0);}}//处理进位string s;int cur m n - 2, carry 0;while(cur 0 || carry){if(cur 0) carry tmp[cur--];s carry % 10 0;carry / 10;}//去除前导零while(s.size() 1 s.back() 0) s.pop_back();//逆序reverse(s.begin(), s.end());return s;}
};真诚点赞手有余香
