算法：字符串相关
目录
题目一：最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 ""
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
解法一：两两比较
解法一就是两两比较的策略，先进行前两个字符串的比较，比较完后，将前两个字符串的公共前缀再与第三个字符串比较，从而得到前三个字符串的公共前缀，以此类推
代码如下：
class Solution
{
public:
string findCommon(string& s1, string& s2)
{
int i = 0;
//i有可能会出现越界的情况，所以i小于s1s2长度时再循环判断
while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
i++;
return s1.substr(0, i);
}
string longestCommonPrefix(vector<string>& strs)
{
int n = strs.size();
//same字符串就是存储最长公共前缀的字符串
string same = strs[0];
for(int i = 1; i < n; i++)
same = findCommon(same, strs[i]);
return same;
}
};解法二：统一比较
统一比较也就是一次性将所有字符串的同一位置作比较，判断是否该位置相同，直到出现不同的字符时为止
这里会出现越界的情况，出现越界说明某一个字符串已经结束了，那么也就可以终止比较了
代码如下：
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
int i = 0;
//以第一个字符串为基准，与其他所有字符串做比较
for(i = 0; i < strs[0].size(); i++)
{
//ch表示第一个字符串当前循环到的字符
char ch = strs[0][i];
//循环strs中其余的字符串，其余字符串的i位置字符与ch做比较
for(int j = 1; j < strs.size(); j++)
{
//如果i大于当前字符串的长度，说明当前字符串已经没有元素了
if(i > strs[j].size() || strs[j][i] != ch)
return strs[0].substr(0, i);
}
}
return strs[0];
}
};题目二：最长回文子串
给你一个字符串 s，找到 s 中最长的 回文子串
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
普通的暴力枚举算法，设置两个指针，一个 i 一个 j ，固定 i ，向后移动 j ，每次移动 j 都需要判断 i 和 j 之间的字符串是否是回文子串，此时移动 j 和判断 i、j 之间是否是回文子串，这里的时间复杂度是O(N^2)，又因为外面嵌套着一层 i ，用于遍历整个字符串，所以整个暴力枚举的时间复杂度是非常高的，达到了O(N^3)，下面看优化后的中心扩展算法：
解法：中心扩展算法
中心扩展算法就是：
①固定一个中心点
②从中心点开始，向两边扩展(奇数和偶数长度都需要考虑到)
也就是每次固定一个中心点 i，每次向 i 的左边和右边扩展，判断是否是回文串，这种算法遍历 i 时间复杂度是O(N)，嵌套的向 i 的左边和右边扩展，时间复杂度也是O(N)，所以最终是O(N^2)，会比上面所说的暴力解法，优化非常多
需要注意的就是中心扩展算法的第二点，需要考虑奇数和偶数，因为奇数是将left和right指针，从 i 位置开始一左一右移动，而偶数需要left在 i 位置，right在 i + 1位置，然后再一左一右移动
需要注意代码中的长度是 right - left - 1，因为当前 left 和 right 指向元素如果相同，需要将left--，right++，此时如果不相同就退出循环，所以 left 和 right 都比回文串多移动了一个位置，所以长度才是 right - left - 1 计算的，具体见下图：
如上图所示，left和right指向当前时退出循环，所以回文子串aa的长度就是：
right - left - 1 = 3 - 0 - 1 = 2
代码如下：
class Solution
{
public:
string longestPalindrome(string s)
{
if(s.size() == 1) return s;
int n = s.size(), begin = 0, size = 0;
for(int i = 0; i < n; i++)
{
//先做奇数长度的扩展
int left = i, right = i;
//left和right符合条件，且指向元素相等再进入循环
while(left >= 0 && right < n && s[left] == s[right])
{
--left;
++right;
}
//如果长度更大，更新begin与size
if((right - left - 1) > size)
{
size = right - left - 1;
begin = left + 1;
}
//再做偶数长度的扩展
left = i, right = i + 1;
//left和right符合条件，且指向元素相等再进入循环
while(left >= 0 && right < n && s[left] == s[right])
{
--left;
++right;
}
//如果长度更大，更新begin与size
if((right - left - 1) > size)
{
size = right - left - 1;
begin = left + 1;
}
}
return s.substr(begin, size);
}
};题目三：二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
这道题就是计算高精度的加法，进行一个模拟运算，模拟列竖式计算的过程
需要设定两个指针cur1和cur2，分别指向两个字符串，再设定一个变量t ，表示进位
代码如下：
class Solution
{
public:
string addBinary(string a, string b)
{
//t表示相加后的进位
int t = 0;
string ret;
int cur1 = a.size()-1, cur2 = b.size()-1;
//cur1或cur2 >= 0表示字符串没遍历完，t>0表示还剩一个进位
while(cur1 >= 0 || cur2 >= 0 || t)
{
if(cur1 >= 0) t += a[cur1--] - '0';
if(cur2 >= 0) t += b[cur2--] - '0';
ret += to_string(t % 2);
t /= 2;
}
//从后向前加的，刚好反过来了，需要逆置
reverse(ret.begin(), ret.end());
return ret;
}
};题目四：字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
解法一：模拟竖式运算
就是数学上，乘法列的竖式，这是最容易想到的方法
如下所示：
我们可以理解为，下面的456的每一位分别乘上面的123，再相加，有三点细节：
①高位相乘需要补0，因为738和615相加时错了一位，可以理解为 738 + 6150
②处理前导0，可能出现123 × 0 的情况，这时答案是000，需要处理一下
③注意计算结果的顺序，因为计算时是逆序计算的，乘法都是从最后一位开始计算的
但是这种方法并不好写代码，我们需要借助这种方法来优化一下
解法二：对解法一优化
无进位相乘再相加，最后一步再处理进位：
即相乘时不管是多少，都不进位，最后加完后再进位
同样，在开始计算时，先逆序，这里由于相乘后可能是两位数，所以就不能使用string表示了，可以采用一个数组存储
由于逆序了，所以123对应的的下标是2,1,0，456对应的下标也是2,1,0
有一个非常好用的规律：i 和 j 下标的数相乘，结果恰好放在数组第 i + j 位上
①定义一个长度是 m + n - 1 数组tmp(m和n对应两个相乘数字的长度)
正在相乘的两个数字的下标分别是 i，j，将计算的结果放在数组的第 i + j 位上
②最后加完以后，需要处理进位
③处理前置0
代码如下：
class Solution
{
public:
string multiply(string num1, string num2)
{
//先逆序两个字符串
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
//定义一个数组tmp
int m = num1.size(), n = num2.size();
vector<int> tmp(m + n - 1);
//无进位相乘然后相加
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
//处理进位
string ret;
int t = 0, cur = 0;
while(cur < m + n - 1 || t != 0)
{
if(cur < m + n - 1) t += tmp[cur++];
ret += to_string(t % 10);
t /= 10;
}
if(t) ret += to_string(t);
//处理前置0
while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};字符串相关的题目到此结束
原文地址：https://blog.csdn.net/m0_64411530/article/details/140248250
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！