《算法题讲解指南：优选算法-字符串》--61.最长公共前缀，62.最长回文子串，63.二进制求和，64.字符串相乘

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录61.最长公共前缀题目链接题目描述题目示例解法一(两两比较)算法思路解法二(统一比较)算法思路C算法代码(解法一两两比较)C算法代码(解法二统一比较)算法总结及流程解析62.最长回文子串题目链接题目描述题目示例解法(中心扩散)算法思路C算法代码算法总结及流程解析63.二进制求和题目链接题目描述题目示例3.解法(模拟十进制的大数相加的过程)算法思路C算法代码64.字符串相乘题目链接题目描述题目示例解法(无进位相乘然后相加最后处理进位)算法思路C算法代码(解法一“模拟”列竖式运算)C算法代码(解法二先无进位相乘再相加最后处理进位)算法总结及流程解析结束语61.最长公共前缀题目链接14. 最长公共前缀 - 力扣LeetCode题目描述题目示例解法一(两两比较)算法思路我们可以先找出前两个的最长公共前缀然后拿这个最长公共前缀依次与后面的字符串比较这样就可以找出所有字符串的最长公共前缀。解法二(统一比较)算法思路题目要求多个字符串的公共前缀我们可以逐位比较这些字符串哪一位出现了不同就在哪一位截止。C算法代码(解法一两两比较)class Solution { public: string longestCommonPrefix(vectorstring strs) { //解法一字符串两两比较 string ret strs[0]; for(int i 1; i strs.size(); i) { int index 0; while(index min(ret.size(), strs[i].size()) ret[index] strs[i][index]) { index; } ret strs[i].substr(0, index); } return ret; } };C算法代码(解法二统一比较)class Solution { public: string longestCommonPrefix(vectorstring strs) { //解法二统一比较 string ret; int index; for(int i 0; i strs[0].size(); i) { index i; for(int j 1; j strs.size(); j) { if(index strs[j].size() || strs[0][index] ! strs[j][index]) { ret strs[0].substr(0, index); return ret; } } } ret strs[0].substr(0, index 1); return ret; } };算法总结及流程解析62.最长回文子串题目链接5. 最长回文子串 - 力扣LeetCode题目描述题目示例解法(中心扩散)算法思路枚举每一个可能的子串非常费时有没有比较简单一点的方法呢?对于一个子串而言如果它是回文串并且长度大于2那么将它首尾的两个字母去除之后它仍然是个回文串。如此这样去除一直除到长度小于等于2时呢?长度为1 的自身与自身就构成回文;而长度为2的就要判断这两个字符是否相等了。从这个性质可以反推出来从回文串的中心开始往左读和往右读也是一样的。那么是否可以枚举回文串的中心呢?从中心向两边扩展如果两边的字母相同我们就可以继续扩展;如果不同我们就停止扩展。这样只需要一层for循环我们就可以完成先前两层for循环的工作量。C算法代码class Solution { public: string longestPalindrome(string s) { int left 0; int right 0; int len 0; int begin 0; string ret; //中心扩展算法 for(int i 0; i s.size(); i) { left right i; //奇数长度的扩展 while(left 0 right s.size() s[left] s[right]) { left--; right; } if(len right - left - 1) { begin left 1; len right - left - 1; } //偶数长度的扩展 if(i 1 s[i] s[i - 1]) { left i - 1; right i; while(left 0 right s.size() s[left] s[right]) { left--; right; } if(len right - left - 1) { begin left 1; len right - left - 1; } } } ret s.substr(begin, len); return ret; } };算法总结及流程解析63.二进制求和题目链接67. 二进制求和 - 力扣LeetCode题目描述题目示例3.解法(模拟十进制的大数相加的过程)算法思路模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和我们不是逢十进一而是逢二进一。C算法代码class Solution { public: string addBinary(string a, string b) { int ai a.size() - 1; int bi b.size() - 1; string ret; int rem 0; while(ai 0 || bi 0 || rem) { if(ai 0) { rem a[ai] - 0; } if( bi 0) { rem b[bi] - 0; } ret to_string(rem % 2); rem / 2; ai--; bi--; } reverse(ret.begin(), ret.end()); return ret; } };64.字符串相乘题目链接43. 字符串相乘 - 力扣LeetCode题目描述题目示例解法(无进位相乘然后相加最后处理进位)算法思路整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性我们选择一种优化版本的就是在计算两数相乘的时候先不考虑进位等到所有结果计算完毕之后再去考虑进位。如下图C算法代码(解法一“模拟”列竖式运算)class Solution { public: string addBinary(string a, string b) { reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int ai a.size() - 1; int bi b.size() - 1; string ret; int rem 0; while(ai 0 || bi 0 || rem) { if(ai 0) { rem a[ai] - 0; } if( bi 0) { rem b[bi] - 0; } ret to_string(rem % 10); rem / 10; ai--; bi--; } return ret; } string multiply(string num1, string num2) { //解法一“模拟”列竖式运算 if(num1 0 || num2 0) { return 0; } reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); string ret 0; for(int i 0; i num2.size(); i) { int rem 0; string tmp; int T i; while(T--) { tmp 0; } int j 0; while(j num1.size() || rem) { if(j num1.size()) { rem ((num2[i] - 0) * (num1[j] - 0)); } tmp to_string(rem % 10); rem / 10; j; } ret addBinary(tmp, ret); } reverse(ret.begin(), ret.end()); return ret; } };C算法代码(解法二先无进位相乘再相加最后处理进位)class Solution { public: string multiply(string num1, string num2) { //解法二先无进位相乘再相加最后处理进位 if(num1 0 || num2 0) { return 0; } //1、准备工作 reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int m num1.size(); int n num2.size(); vectorint tmp(m n - 1); //2、先无进位相乘再相加 for(int i 0; i num2.size(); i) { for(int j 0; j num1.size(); j) { tmp[i j] ( num1[j] - 0) * (num2[i] - 0); } } //3、最后处理进位 string ret; int rem 0; int i 0; while(i tmp.size() || rem) { if(i tmp.size()) { rem tmp[i]; } ret to_string(rem % 10); rem / 10; i; } reverse(ret.begin(), ret.end()); return ret; } };算法总结及流程解析结束语到此61.最长公共前缀62.最长回文子串63.二进制求和64.字符串相乘 这四道算法题就讲解完了。最长公共前缀的两种解法两两比较和统一比较 最长回文子串的中心扩散法二进制求和的模拟竖式加法字符串相乘的两种解法模拟竖式乘法和无进位相乘再处理进位。每种解法都提供了C代码实现和思路解析涵盖字符串处理中的常见问题包括前缀匹配、回文检测、二进制运算和大数相乘等典型场景。希望大家能有所收获