admin管理员组文章数量:1487745
算法讲解之字符串
前言：
本文主要讲解算法中和字符串结合的题目，跟字符串结合的算法题种类丰富，主要是跟别的算法结合，下面介绍几道比较经典的题目~
第一道：14. 最长公共前缀
题目描述：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：strs = ["flower","flow","flight"]
输出："fl"题目解析：
我们就以第一个字符串为基准值，然后以第一个字符串的每一个字符与剩下的全部字符串进行比较，直到不相等，break跳出循环即可，注意返回值我们可以用substr来返回，不用再新创建一个字符串存储。
原码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
for(int i = 0;i<strs[0].size();i++)
{
char tmp = strs[0][i];//取一个基准值与剩下比较
for(int j = 1;j<strs.size();j++)
{
if(i == strs[j].size() || strs[j][i] != tmp)
return strs[0].substr(0,i);//以基准字符串返回
}
}
return strs[0];
}
};第二题：
5. 最长回文子串
题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。题目解析：
我们可以用回文字符串的特性来解决这道题，先确定一个中心坐标，然后分别向左右两边扩张，一直到左右指针的字符不一样就停止。这里的从中心向两边遍历的方法需要考虑两种情况——偶数和奇数。
同样，返回值也可以用substr进行原来字符串截取进行返回。
原码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
string longestPalindrome(string s) {
//中心扩展算法
int num = s.size();
//判断特殊情况
if(num == 1 || num == 0) return s;
int index = 0;
int max_len = 0;
for(int i = 0;i<num;i++)//依次枚举所有中点
{
//奇数
int left = i-1,right = i+1;
while(left >= 0 && right < num)
{
if(s[left] == s[right])
{
if(right-left+1 > max_len)
{
max_len = right-left+1;
index = left;
}
left--;
right++;
}
else break;
}
//偶数
left = i;right = i+1;
while(left >= 0 && right < num)
{
if(s[left] == s[right])
{
if(right-left+1 > max_len)
{
max_len = right-left+1;
index = left;
}
left--;
right++;
}
else break;
}
}
if(max_len == 0) return s.substr(0,1);
return s.substr(index,max_len);
}
};第三题：67. 二进制求和
题目描述：
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入:a = "11", b = "1"
输出："100"示例 2：
代码语言：javascript代码运行次数：0运行复制输入：a = "1010", b = "1011"
输出："10101"题目解析：
这题就是标准的高精度算法，本质就是一道模拟题，对小学学过的列竖式运算的模拟！
这题要熟练使用如何将字符转换为数字（- '0'）,将数字转换为字符（+'0'）。
注意reverse逆置函数是C++中已经实现的函数，与swap函数一样。
原码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
string addBinary(string a, string b) {
int num1 = a.size();
int num2 = b.size();
string s;
int index = 0;//记录下标
int bit = 0;//记录进位
for(int i = num1-1,j = num2-1;i > -1 || j > -1 || bit;i--,j--)//注意循环判断条件
{
int tmp = 0;
if(i > -1) tmp += a[i]-'0';
if(j > -1) tmp += b[j]-'0';
tmp += bit;
s += tmp%2 + '0';//再将数字转换为字符
bit = tmp/2;
}
reverse(s.begin(),s.end());
return s;
}
};第四题：43. 字符串相乘
题目描述：
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
代码语言：javascript代码运行次数：0运行复制输入: num1 = "2", num2 = "3"
输出: "6"示例 2:
代码语言：javascript代码运行次数：0运行复制输入: num1 = "123", num2 = "456"
输出: "56088"题目解析：
本题也是一道模拟题，对乘法列竖式运算的模拟，但是如果只是普通的乘法列竖式，未免模拟过于繁琐，因此我们还要了解一种非进位相乘~
这种非进位相乘模拟起来更加简单。无进位相乘然后相加，，最后处理进位。
原码：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0") return "0";
int len1 = num1.size(),len2 = num2.size();
vector<int> arr;
arr.resize(len1+len2);
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
//存储没有进位的答案
for(int i = 0;i<len1;i++)
{
int a = num1[i]-'0';
for(int j = 0;j<len2;j++)
{
int b = num2[j]-'0';
arr[i+j] += a*b;//创建数组记录每一位无进位相乘
}
}
//处理进位
string ans;
int bit = 0;
for(int i = 0;i<len1+len2;i++)
{
arr[i] += bit;
ans += arr[i] % 10 + '0';
bit = arr[i]/10;
}
reverse(ans.begin(),ans.end());
//处理前导0
if(ans[0] == '0')
{
ans.erase(0,1);
}
return ans;
}
};本文标签： 算法讲解之字符串
版权声明：本文标题：算法讲解之字符串 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/shuma/1754809293a3179853.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论