dw怎么做网站教程,房地产项目营销策划方案,域名更换网站,安阳吧字符串相乘
题面
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
给定两个以字符串形式表示的非负整数 num1 和 num2#xff0c;返回 num1 和 num2 的乘积#xff0c;它们的乘积也表示为字符串形式。
注意#xff1a;不能使用任何内置的 BigIn…字符串相乘
题面
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
给定两个以字符串形式表示的非负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。
注意不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 示例 1:
输入: num1 2, num2 3 输出: 6 示例 2:
输入: num1 123, num2 456 输出: 56088 错误记录
我一开始的思路是先把俩字符串转化成整数然后相乘结果再转化成字符串返回回去。然后挣扎了很久每次测试都没问题一提交就报错。后来我仔细看了下题面发现人家早就说明了“不能使用任何内置的 BigInteger 库或直接将输入转换为整数。”
所以这道题要的就是你去模拟乘法的计算过程并且计算过程的数字要以字符的形式存进string中。 Way1 拆分成“先乘后加”
思路 现在目的明确完成两个Part
1.遍历两个字符串将整个的乘法拆分成一部分一部分的乘积。
2.将这些乘积相加即写一个字符串相加的函数。 实现
class Solution {
public:string multiply(string num1, string num2) {if(num10||num20){ //如果有一个被乘数是0那结果直接返回0return 0;}int n1num1.size(),n2num2.size(); string ret,combine_ret;for(int in1-1;i0;i--){ //每次都要把上一次的更新一下ret.clear();int add_num0; //用于保存进位for(int jn2-1;j0;j--){int tmp(num1[i]-0)*(num2[j]-0)add_num;int present_numtmp%10; //当前位ret.insert(ret.begin(),present_num0);add_numtmp/10;}if(add_num){ //如果还有剩余的add_num别忘了进位 ret.insert(ret.begin(),add_num0);}int add_num_of_zeron1-1-i; //补0while(add_num_of_zero){ret.push_back(0);add_num_of_zero--;}combine_retaddString(combine_ret,ret);}return combine_ret;}string addString(string s1,string s2){ //这里字符串相加 采用的是补0的思路很实用int n1s1.size(),n2s2.size();string StrRet;//通过在前面补0的方法让n1和n2位数对齐while(n1n2){s2.insert(s2.begin(),0);n2;}while(n2n1){s1.insert(s1.begin(),0);n1;}
int add_num0;for(int in1-1;i0;i--){int tmp(s1[i]-0)(s2[i]-0)add_num;add_numtmp/10;StrRet.insert(StrRet.begin(),tmp%100);}if(add_num){ //如果还有剩余的add_num别忘了进位StrRet.insert(StrRet.begin(),add_num0);}return StrRet;}
}; 时空复杂度分析
时间复杂度为O(n1*n2)其中n1、n2分别是num1、num2的长度。
空间复杂度O(1) 反思
1.每次循环开始前 别忘了刷新变量要再设回初始值。 2.字符串相加用补0的思路很好用。先将俩字符串的位数 用0补得整齐后面就很好计算了。 3.最常犯的错误是没把数字转化成askii码存进字符串
for(int in1-1;i0;i--){int tmpAddNum(s1[i]-0)(s2[i]-0);ret.insert(ret.begin(),tmp%10); //应为tmp%100AddNumtmp/10;} 4.这个思路的亮点在于 拆分成先乘后加 和 补0。 Way2 用数组
思路 1.开大小为n1n2的数组记得初始化为0。
因为两数相乘乘积的位数 是不会超过 被乘数的位数之和的所以这个大小一定够用了。 2.从右往左遍历被乘数的每个位数结果挨个放进数组里。 3.把数组的数存进字符串同时要考虑进位。 实现
class Solution {
public:string multiply(string num1, string num2) {if(num10||num20){return 0;}int n1num1.size(),n2num2.size();int NumArrn1n2;int*arrnew int[NumArr](); //注意这种写法 可以初始化为0
int kNumArr-1;for(int in1-1;i0;i--){int CopyKk; for(int jn2-1;j0;j--){int tmp(num1[i]-0)*(num2[j]-0);arr[k--]tmp;}kCopyK-1;}
//把数组内容存进字符串string ret;int AddNum0;for(int iNumArr-1;i0;i--){//进位AddNumarr[i]/10;if(i0){arr[i-1]AddNum; //这里要小心i-1是很容易越界的所以要加个条件判断 }
ret.insert(ret.begin(),arr[i]%100);}if(AddNum){ret.insert(ret.begin(),AddNum0);}delete[] arr;for(int i0;iNumArr;i){if(ret[i]!0){return ret.substr(i);}}return ret;}
}; 时空复杂度分析
时间复杂度为O(n1*n2n1n2)n1、n2分别为num1、num2的大小
空间复杂度为O(n1n2) 翻转字符串III翻转字符串中的单词
题面
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
给定一个字符串 s 你需要反转字符串中每个单词的字符顺序同时仍保留空格和单词的初始顺序。 示例 1
输入s Lets take LeetCode contest 输出steL ekat edoCteeL tsetnoc 示例 2:
输入 s God Ding 输出doG gniD 错误记录
第一次写的时候报执行出错修改了好久也没发现错误
class Solution {
public:void swap(string s,int left,int right){while(left!right){std::swap(s[left],s[right]);left;right--;}}string reverseWords(string s) {int nums.size();int front_i0;for(int i0;inum;i){if(s[i] ){if(front_i!0){front_i1;}swap(s,front_i,i-1);front_ii; }}return s;}
};
报错 后来终于揪出来BUG了在这里
void swap(string s,int left,int right){while(left!right){ //这里不能用!得用std::swap(s[left],s[right]);left;right--;}}
当string的大小是偶数个时! 会导致left和right刚好错过。
果然是细节决定成败 思路1 遍历找单词
这题的思路蛮简单的遍历一遍字符串遇到单词就把整个单词swap一下。
至于怎么找到单词
可以通过空格的位置来划分单词。也可以遍历的时候记录下单词的起始位置。这两种找单词的方法都来实现一下。 实现
这种思路下的两种实现方式
第一种 class Solution {
public:void swap(string s,int left,int right){while(leftright){std::swap(s[left],s[right]);left;right--;}}string reverseWords(string s) {int nums.size();int front_i0;for(int i0;inum;i){if(s[i] ){ //找到空格的位置if(front_i!0){front_i1;}swap(s,front_i,i-1);front_ii; }}//处理下最后一个词if(front_i!0){front_i1;}swap(s,front_i,num-1);return s;}
}; 第二种这种方法我第一次没写出来那个循环给我绕晕了。这种方法挺好的得多写几遍
class Solution {
public:string reverseWords(string s) {int nums.size();int i0;while(inum){int starti;while(inums[i]! ){ //注意看这个循环条件要加上inum保证安全i;} //当出了循环str[i]就是空格int leftstart;int righti-1;while(leftright){swap(s[left],s[right]);left;right--;}
while(inums[i] ){ i;}}return s;}
}; 反思
第二种思路我当时没写出来问题就出在那个大循环while(inum){}里我当时一上来就把框架搭好了
while(inum)
{i;
}
这个框架太经典了结果限制住了我的思路。实际上我不应该先把i;写上的后面得把这个循环多写几遍多体会一下。
然后就是要注意大while()里包小while()小while()加上大while()的判断条件会更安全不容易越界。 思路2 暴力解法
思路1里我们是手动翻转字符串的但实际上可以直接用库里的reverse、find函数。
思路2则不用遍历字符串的每一个字符而是用find找到空格然后从空格的后一个 接着去找 下一个空格。
当没有空格时说明是最后一个单词翻转然后break跳出循坏。 注意这种写法循环里也没有经典的i;所以不要一写循环就把i;给添上不要 被习惯限制住思路
实现
class Solution {
public:string reverseWords(string s) {int nums.size();int i0;while(inum){size_t poss.find( ,i); //注意这里用size_tif(pos!string::npos){reverse(s.begin()i,s.begin()pos); //因为是从i开始找的所以要加iipos1; //现在要从空格的下一位开始找} //注意reverse是左闭右开右边是开区间else{reverse(s.begin()i,s.end()); //没有空格了说明这已经是最后一个单词了break;}}return s;}
};
