目录
一.leetcode：43. 字符串相乘
1.问题描述
2.问题分析
3.问题求解
二. leetcode：541. 反转字符串 II
1.问题描述
2.题解
三. leetcode：125. 验证回文串
1.问题描述
2.双指针法求解
一.leetcode：43. 字符串相乘
- 字符串相乘 - 力扣（Leetcode）
1.问题描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
注意：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字字符组成。
num1 和 num2 都不包含任何前导零。
题解接口：
class Solution
{
public:
string multiply(string num1, string num2)
{
}};
2.问题分析
关于两个乘积的结果的分析
假设num1为n位数,num2为m位数，则num1与num2的乘积最多为n+m位数。
为了方便计算，我们可以先将数字字符串转换成相应的数字数组
3.问题求解
第一步
封装一个转换函数将数字字符串倒序存入相应的数字数组(倒不倒序其实无所谓)
void convert(string& nums, int* const Anum)
{
int end = nums.size();
int start = 0;
for (start = 0; start < nums.size(); start++)
{
Anum[start] = nums[end - 1]-'0'; //-'0'是为了将字符转换为相应数字
end--;
}
}第二步
动态开辟一个数组Anum1用于倒序存储字符串num1对应的数字
动态开辟一个数组Anum2用于倒序存储字符串num2对应的数字
动态开辟一个数组Answer用于倒序存储两数相乘的计算结果
创建一个string StrAns用于存储最后要输出的结果。
int ptrnum1 = num1.size();
int ptrnum2 = num2.size();
int* const Anum1 = new int[ptrnum1];
int* const Anum2 = new int[ptrnum2];
int* const Answer = new int[ptrnum1 + ptrnum2]{0};//存储结果的数组中所有元素初始化为0
string StrAns;
StrAns.reserve(ptrnum1 + ptrnum2);
convert(num1,Anum1);
convert(num2,Anum2);注意利用reserve接口提前为StrAns字符串预留好存储空间，避免后续扩容增加时间消耗
第三步(算法部分)
基本思路是用三个数组模拟竖式乘法：
循环框架：
for(i=0;i<ptrnum1;i++)
{
for(j=0;j<ptrnum2;j++)
{
;
}
;
}变量limitAnswer用来记录计算结果的位数；
变量tem用来保存当前(两个数某两位的乘积+进位+存储结果的数组的原位)的和；
变量carry用来保存进位；
int limitAnswer = 0;
int i=0;
int j=0;
int tem=0;
int carry=0;
for(i=0;i<ptrnum1;i++)
{
for(j=0;j<ptrnum2;j++)
{
tem = carry + Anum1[i]*Anum2[j] + Answer[j+i];
Answer[i+j]=tem%10; //tem的个位就是当前Answer对应位的取值
carry = tem/10; //tem取十位数得到下一位的进位
}
if(carry)
{
Answer[i+j]=carry;//该轮循环计算完后若还存在进位则将进位置于当前结果的最高位
//的下一位
carry=0;
limitAnswer=i+j; //记录当前结果的位数
}
else
{
limitAnswer = i+j-1;//记录当前结果的位数
}
}
算法动画演示：
代码段实际计算过程中Answer中的数字是逆序存储的
第四步
将结果倒序存入用于作返回值的对象StrAns的字符串中：
for(i=limitAnswer;i>=0;--i)
{
StrAns += (Answer[i]+'0');
}完整题解代码：
class Solution
{
public:
void convert(string& nums, int* const Anum)
{
int end = nums.size();
int start = 0;
for (start = 0; start < nums.size(); start++)
{
Anum[start] = nums[end - 1]-'0';
end--;
}
}
string multiply(string num1, string num2)
{
if("0"==num1||"0"==num2)
{
return "0";
}
int ptrnum1 = num1.size();
int ptrnum2 = num2.size();
int* const Anum1 = new int[ptrnum1];
int* const Anum2 = new int[ptrnum2];
int* const Answer = new int[ptrnum1 + ptrnum2]{0};
string StrAns;
StrAns.reserve(ptrnum1 + ptrnum2);
convert(num1,Anum1);
convert(num2,Anum2);
int limitAnswer = 0;
int i=0;
int j=0;
int tem=0;
int carry=0;
for(i=0;i<ptrnum1;i++)
{
for(j=0;j<ptrnum2;j++)
{
tem = carry + Anum1[i]*Anum2[j] + Answer[j+i];
Answer[i+j]=tem%10;
carry = tem/10;
}
if(carry)
{
Answer[i+j]=carry;
carry=0;
limitAnswer=i+j;
}
else
{
limitAnswer = i+j-1;
}
}
for(i=limitAnswer;i>=0;--i)
{
StrAns += (Answer[i]+'0');
}
return StrAns;
}};
二. leetcode：541. 反转字符串 II
- 反转字符串 II - 力扣（Leetcode）
1.问题描述
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
2.题解
class Solution
{
public:
string reverseStr(string s, int k)
{
int n = s.length();
for (int i = 0; i < n; i += 2 * k)
{
reverse(s.begin() + i, s.begin() + min(i + k, n));
}
return s;
}};
min是C++标准库命名空间std中的一个函数，用于返回两个数中的较小值
reverse是C++标准库命名空间std中的一个函数，用于string对象的字符串逆序，形参为两个string对象的迭代器(初学者可以类比为指针)
将迭代器类比为指针: s.begin()相当于指向string字符串首元素的指针
三. leetcode：125. 验证回文串
1.问题描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串 。
给你一个字符串 s，如果它是回文串 ，返回 true ；否则，返回 false 。
示例 ：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
2.双指针法求解
本题利用双指针法可以同时节省时间和空间：
创建两个下标变量，其中一个起始位置指向字符串首字符，另外一个起始位置指向字符串末尾字符。
起始位置指向字符串首字符的指针向后遍历，起始位置指向字符串末尾字符的指针向前遍历
题解代码：
class Solution
{
public:
bool isword (char & c) //封装一个字符判断函数
{
if((c>='a'&&c<='z') ||( c>='0'&&c<='9'))
{
return true;
}
else if((c>='A'&&c<='Z')) //大写转小写
{
c+=32;
return true;
}
return false;
}
bool isPalindrome(string s)
{
int right= s.size()-1;
int left=0;
while(right>left)
{
while(right>left && !isword(s[left])) //左指针跳过非数字字母字符
{
left++;
}
while(right>left && !isword(s[right])) //右指针跳过非数字字母字符
{
right--;
}
if(s[left]!=s[right]) //若过程中有字符不相同则说明不是回文串
{
return false;
}
left++;
right--;
}
return true;
}};
注意内层循环条件中right>left不能少。
