总言
主要内容：编程题举例，熟悉理解字符串类题型。
文章目录
- 总言
- 1、字符串
- 2、最长公共前缀（easy）
- 2.1、题解
- 3、最长回文子串 (medium)
- 3.1、题解
- 4、二进制求和（easy）：高精度加法
- 4.1、题解
- 5、字符串相乘（medium）：高精度乘法
- 5.1、题解
- Fin、共勉。
1、字符串
主要在于熟悉字符串类的OJ题常用容器和接口。主要与其它算法结合使用。
2、最长公共前缀（easy）
题源：链接。
2.1、题解
1）、思路分析
这里需要注意理解，一个字符串的前缀是从该字符串的第一个字符起始的一个子串。
方法一： 字符串两两比较，可以先找出前两个的最长公共前缀，然后拿这个最长公共前缀依次与后⾯的字符串比较，获取新的最长公共前缀，这样所有字符串比较完成，就能获取到最终结果。
方法二： 统一比较所有字符串中 i 位置处的字符是否相同。何时结束比较？（遍历到某一字符串的尾部，或当前遍历字符与其它字符不相同，说明此前的字符均为公共前缀。）
2）、题解
字符串两两进行比较的写法：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
//一个字符串的前缀是从该字符串的第一个字符起始的一个子串
string ret = strs[0];//PS：数组中只有一个字符串，也满足条件（不进入循环，直接返回strs[0]）。
for(int i = 1; i < strs.size(); ++i)
{
ret = stringcompare(ret,strs[i]);
}
return ret;
}
//两字符串比较
string stringcompare(string& s1, string& s2)
{
int i = 0;
int len = min(s1.size(), s2.size());
while(i < len && s1[i] == s2[i]) //当两字符串均存在，且当前位置元素相同时
i++;
return s1.substr(0,i);//string substr (size_t pos = 0, size_t len = npos) const;
}
};
字符串统一进行比较的写法：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ref = strs[0];//以第一个字符串作为参照，后续字符串进行比较判断
for(int i = 0; i < ref.size(); ++i)//遍历字符串strs[0]，与其它字符串逐个比较i位置处的字符
{
for(int j = 1; j < strs.size(); ++j)//j表示第j个字符串，比较的是其第i个字符。
{
if(i > strs[j].size() || ref[i] != strs[j][i])//这里字符长度与字符元素都要进行判断
return ref.substr(0,i);
}
}
return ref;
}
};
3、最长回文子串 (medium)
题源：链接。
3.1、题解
1）、思路分析
我们可以利用回文子串的性质。若一个字符串是回文串，从其中心位置开始向两边扩散，有左右两侧元素相等。
以上是回文子串长度为奇数的情况，设当前遍历到的元素 i 为中心元素，则有left = i -1，right = i + 1，比较判断s[left]和s[right]，若符合则继续往两侧扩散寻找。
此外，我们还需要考虑偶数情况。如下：可以让left = i; right = i + 1或right = i; left = i - 1，依次往两边扩散比较。
2）、题解
整体可以套两层循环完成，外层用于遍历中心元素i，寻找每回合的回文子串，内层用于判断当前回合中，回文子串的扩散长度。
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int begin = 0; // 用于记录最长数组的起始下标。
int len = 0; // 用于记录最长数组的长度。
for (int i = 0; i < n; ++i) {
// 以i为中点，向两边扩散
// 以偶数扩展
int left = i;
int 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; // (right - 1) - (left + 1) + 1;
}
// 以奇数扩展
left = i;
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; // (right - 1) - (left + 1) + 1;
}
}
return s.substr(begin, len);
}
};
4、二进制求和（easy）：高精度加法
题源：链接。
4.1、题解
1）、思路分析
背景介绍： 此题实则为 高精度计算。高精度计算通常用于处理那些超出了标准数据类型（如 int, float, double 等）能够表示的范围或精度的数字。高精度计算通常涉及字符串或数组来表示大数字，并使用特殊的算法来进行加、减、乘、除等操作。
题解： 类似这样的题，我们在链表的两数相加中也做过，这里运用的方法原理不变，模拟列竖式计算两个数之和的过程即可。需要注意：
①这里是二进制，因此两数相加时应该是逢二进一。
②链表的题里直接给了我们逆序，方便了位数之间的运算，这里题目给我们的是正常顺序的字符串，在进行运算时需要对进位做处理。
2）、题解
以下为题解，总思想不变。但这里我们从字符串末尾开始往前运算。对于最终输出结果，可以先获取到一个逆序的字符串再逆置回来，或者直接使用头插获得正序的字符串。
class Solution {
public:
string addBinary(string a, string b) {
int sum = 0;//用于记录相位运算结果
int cur1 = a.size()-1, cur2 =b.size()-1;//分别用于遍历两字符串(注意运算要从低位开始，这里是字符串尾位置)
string ret;//用于记录返回结果
while(cur1 >= 0 || cur2 >= 0 || sum)
{
if(cur1 >= 0)
sum += a[cur1--] -'0';
if(cur2 >= 0)
sum += b[cur2--] -'0';
ret += sum % 2 + '0';
//ret.insert(0, 1, sum % 2 + '0');//若不用+=结合逆置，这里也可以用insert头插
sum /= 2;
}
reverse(ret.begin(),ret.end());//字符串逆置
return ret;
}
};
5、字符串相乘（medium）：高精度乘法
题源：链接。
5.1、题解
1）、思路分析
此题方法：无进位相乘然后相加，最后处理进位。
整体思路就是模拟我们列竖式计算两个数相乘的过程。但是为了书写代码的方便性，可对其进行优化：在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。 （所得结果和常规的列竖式计算相同）
关于两数相乘的位数证明：相关链接。
2）、题解
class Solution {
public:
string multiply(string num1, string num2) {
//先对字符串逆序
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int m = num1.size();
int n = num2.size();
vector<int> tmp(m + n -1);//用于存储无进位相乘后相加结果
//无进位相乘相加
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
tmp[j+i] += (num2[i] - '0')*(num1[j] - '0');//这里要注意相乘后结果应该放在哪位上。
}
}
//处理结果（tmp数组，处理进位）
int sum = 0; int i = 0;
string ret;
while(i < tmp.size() || sum)
{
if(i <tmp.size())
sum += tmp[i++];
ret += sum % 10 + '0';
sum /= 10;
}
//处理前导零
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
//逆置返回
reverse(ret.begin(), ret.end());
return ret;
}
};
Fin、共勉。
