算法训练之字符串
♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥
♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥
♥♥♥我们一起努力成为更好的自己~♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥
✨✨✨✨✨✨个人主页✨✨✨✨✨✨
在计算机科学的世界中，字符串无处不在——从日常的文本搜索到复杂的密码学算法，它都是不可或缺的基础元素。掌握高效的字符串处理技巧，不仅能提升编程能力，更能为解决现实问题提供强大支持。这一篇博客我们进行关于字符串算法题目的练习，准备好了吗~我们发车去探索字符串的奥秘啦~🚗🚗🚗🚗🚗🚗
目录
最长公共前缀😍
最长回文子串😁
二进制求和❤
字符串相乘😀
最长公共前缀😍
最长公共前缀
题目要求我们求一个字符串数组的最长公共前缀，如果是两个字符串，我们可以分别使用两个指针从头开始遍历来找到最长公共前缀，现在是一个字符串数组，那么我们同样可以采用类似的方法，这里给出两种算法思路~
算法思路1：两两比较
遍历字符串数组，依次两两比较得到最长公共前缀子串，再将最长公共前缀子串与后续字符串比较依此类推比较，最终得到所有字符串的最长公共前缀~
代码实现：
//字符串数组最长公共前缀
class Solution
{
public:string longestCommonPrefix(vector<string>& strs){//处理边界情况if (strs.size() == 1)return strs[0];string ret = strs[0];for (int i = 1; i < strs.size(); i++){string tmp = strs[i];int index = 0;while (index < ret.size() && index < tmp.size() && ret[index] == tmp[index])//判断对应字符是否相等{index++;}ret = ret.substr(0, index);//substr第二个参数是截取的个数}return ret;}
};算法思路2：统一比较
我们可以以一个字符串作为标准，其他的字符串按照下标统一进行比较，直到没有相同字符就停止~
代码实现：
//统一比较
class Solution
{
public:string longestCommonPrefix(vector<string>& strs){//处理边界情况if (strs.size() == 1){return strs[0];}//统一比较string ret;//以第一个字符串作为标准for (int i = 0; i < strs[0].size(); i++){for (int j = 1; j < strs.size(); j++)//后面的字符串统一比较{//字符不相等或者长度不一样直接返回if (strs[j][i] != strs[0][i] || i > strs[j].size())return ret;}ret.push_back(strs[0][i]);//插入相同字符}return ret;}
};
顺利通过~
最长回文子串😁
最长回文子串
回文字符串我们都知道他的概念，从头开始和从末尾开始都是一样的，现在我们要在一个字符串中找到最长回文子串，这里我们给出算法思路~
算法思路：中心扩展法
回文字符串最重要的一个特点就是关于一个字符中心对称，那么我们就可以利用这个特点使用中心扩展法，选择一个中心点往两边开始走，这里需要特别注意的是回文字符串有字符个数为奇数或者偶数的两种情况，所以我们需要两种情况都考虑到比较得到最长回文子串
画图理解：
代码实现：
//最长回文子串
class Solution
{
public:string longestPalindrome(string s){string ret;for (int i = 0; i < s.size(); i++){//奇数情况int left = i - 1, right = i + 1;string ret1 = findS(s, left, right);//偶数情况left = i, right = i + 1;string ret2 = findS(s, left, right);//更新结果ret1 = (ret1.size() > ret2.size()) ? ret1 : ret2;ret = (ret1.size() > ret.size()) ? ret1 : ret;}//返回结果return ret;}//根据left和right找回文子串string findS(string s, int left, int right){while (left >= 0 && right < s.size() && s[left] == s[right]){left--;right++;}return s.substr(left + 1, right - left - 1);}
};
顺利通过~
二进制求和❤
二进制求和
二进制求和与我们的十进制求和事实上是类似的，二进制是满二进一，十进制是满十进一，解决这个问题，我们只需要模拟加法的过程就可以了~
算法思路：模拟加法过程
①逆序字符串，让低位在下标小的地方
②从低位开始模拟加法，进行进位（满二进一），尾插到结果字符串中（字符串下标小的地方是低位）
③逆序结果字符串就是我们的结果
代码实现：
//二进制求和
class Solution
{
public:string addBinary(string a, string b){//逆序字符串reverse(a.begin(), a.end());reverse(b.begin(), b.end());int n_val = 0;//记录进位int i = 0;//记录处理位string ret;//记录结果while (i < a.size() || i < b.size() || n_val){if (i < a.size())n_val += (a[i] - '0');if (i < b.size())n_val += (b[i] - '0');ret.push_back(n_val % 2 + '0');n_val /= 2;//进位i++;//走到高位}//逆序结果reverse(ret.begin(), ret.end());return ret;}
};
顺利通过~
字符串相乘😀
字符串相乘
字符串相乘一般也就是来处理我们的大数相乘，我们的处理方法与模拟乘法过程类似，但是需要简单变化一下~
算法思路：模拟乘法过程优化（无进位相乘后相加，处理进位）
①逆序输入字符串
让数字的个位对齐下标 0，后续计算可直接从下标 0 开始（即从个位开始操作），避免手动对齐位数。
②逐位相乘并累加
相同位权的乘积存放在数组相同偏移位置
③统一处理进位
④去除前导零
此时
ret是逆序状态，从ret末尾（即实际结果的高位）开始删除连续的'0'。
注意边界保护：若结果全为 0，至少保留一个'0'（如while (ret.size()>1 && ret.back()=='0')）。⑤逆序结果字符串
将
ret从低位在前转为高位在前的正常顺序
画图理解：
以456*34为例：
代码实现：
//字符串相乘
class Solution
{
public:string multiply(string num1, string num2){//逆序字符串reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());int n1 = num1.size(), n2 = num2.size();//记录对应位结果vector<int> arr(n1 + n2);for (int i = 0; i < n1; i++){for (int j = 0; j < n2; j++){//先相乘再相加arr[i + j] += (num1[i] - '0') * (num2[j] - '0');}}//从低位开始处理进位，也就是下标小的地方string ret;int n_val = 0;int index = 0;while (index < n1 + n2 || n_val){if (index < n1 + n2){n_val += arr[index];}ret.push_back(n_val % 10 + '0');n_val /= 10;//进位index++;}//处理前导0（没有逆序前在后面）while (ret.size() > 1 && ret.back() == '0'){ret.pop_back();}//逆序结果字符串reverse(ret.begin(), ret.end());//返回结果return ret;}
};
顺利通过~
♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
✨✨✨✨✨✨个人主页✨✨✨✨✨✨