leetcode：43.字符串相乘(附加一些C++string其他小练习)

目录

一.leetcode：43. 字符串相乘

1.问题描述

2.问题分析

3.问题求解 

二. leetcode：541. 反转字符串 II 

1.问题描述 

2.题解

三. leetcode：125. 验证回文串

1.问题描述

2.双指针法求解 

---

一.leetcode：43. 字符串相乘

43. 字符串相乘 - 力扣（Leetcode）

1.问题描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6"

示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088"

注意：

1 <= num1.length, num2.length <= 200num1 和 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 

541. 反转字符串 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不能少。