【string题解 C++】字符串相乘 | 翻转字符串III：翻转单词

目录

字符串相乘

题面

错误记录

Way1 拆分成“先乘后加”

思路

实现

时空复杂度分析

反思

Way2 用数组

思路

实现

时空复杂度分析

翻转字符串III：翻转字符串中的单词

题面

错误记录

思路1 遍历找单词

实现

思路2 暴力解法

实现

---

字符串相乘

题面

力扣（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(num1=="0"||num2=="0"){   //如果有一个被乘数是0，那结果直接返回0
            return "0";
        }
        int n1=num1.size(),n2=num2.size();   
        string ret,combine_ret;
        for(int i=n1-1;i>=0;i--){   
            //每次都要把上一次的更新一下
            ret.clear();
            int add_num=0;    //用于保存进位
            for(int j=n2-1;j>=0;j--){
                int tmp=(num1[i]-'0')*(num2[j]-'0')+add_num;
                int present_num=tmp%10;     //当前位
                ret.insert(ret.begin(),present_num+'0');
                add_num=tmp/10;
            }
            
            if(add_num){      //如果还有剩余的add_num，别忘了进位  
                ret.insert(ret.begin(),add_num+'0');
            }
            
            int add_num_of_zero=n1-1-i;   //补0
            while(add_num_of_zero){
                ret.push_back('0');
                add_num_of_zero--;
            }
            combine_ret=addString(combine_ret,ret);
        }
        return combine_ret;
    }
    
    string addString(string s1,string s2){   //这里字符串相加 采用的是补0的思路，很实用
        int n1=s1.size(),n2=s2.size();
        string StrRet;
        //通过在前面补0的方法，让n1和n2位数对齐
        while(n1>n2){
            s2.insert(s2.begin(),'0');
            n2++;
        }
        while(n2>n1){
            s1.insert(s1.begin(),'0');
            n1++;
        }
​
        int add_num=0;
        for(int i=n1-1;i>=0;i--){
            int tmp=(s1[i]-'0')+(s2[i]-'0')+add_num;
            add_num=tmp/10;
            StrRet.insert(StrRet.begin(),tmp%10+'0');
        }
      
        if(add_num){       //如果还有剩余的add_num，别忘了进位
            StrRet.insert(StrRet.begin(),add_num+'0');
        }
        return StrRet;
    }
};

时空复杂度分析

时间复杂度为O(n1*n2)，其中n1、n2分别是num1、num2的长度。

空间复杂度O(1)

反思

1.每次循环开始前 ，别忘了刷新变量！要再设回初始值。

2.字符串相加，用补0的思路，很好用。先将俩字符串的位数 用0补得整齐，后面就很好计算了。

3.最常犯的错误是：没把数字转化成askii码存进字符串

for(int i=n1-1;i>=0;i--){
            int tmp=AddNum+(s1[i]-'0')+(s2[i]-'0');
            ret.insert(ret.begin(),tmp%10);   //应为tmp%10+'0'
            AddNum=tmp/10;
        }

4.这个思路的亮点在于 拆分成先乘后加 和 补0。

Way2 用数组

思路

1.开大小为n1+n2的数组（记得初始化为0）。

因为两数相乘，乘积的位数 是不会超过 被乘数的位数之和的，所以这个大小一定够用了。

2.从右往左遍历被乘数的每个位数，结果挨个放进数组里。

3.把数组的数存进字符串，同时要考虑进位。

实现

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0"){
            return "0";
        }
        int n1=num1.size(),n2=num2.size();
        int NumArr=n1+n2;
        int*arr=new int[NumArr]();  //注意这种写法 可以初始化为0
​
        int k=NumArr-1;
        for(int i=n1-1;i>=0;i--){
            int CopyK=k;     
            for(int j=n2-1;j>=0;j--){
                int tmp=(num1[i]-'0')*(num2[j]-'0');
                arr[k--]+=tmp;
            }
            k=CopyK-1;
        }
​
        //把数组内容存进字符串
        string ret;
        int AddNum=0;
        for(int i=NumArr-1;i>=0;i--){
            //进位
            AddNum=arr[i]/10;
            if(i>0){
            arr[i-1]+=AddNum;    //这里要小心，i-1是很容易越界的！所以要加个条件判断 
            }
​
            ret.insert(ret.begin(),arr[i]%10+'0');
        }
        if(AddNum){
            ret.insert(ret.begin(),AddNum+'0');
        }
        delete[] arr;
        for(int i=0;i
            if(ret[i]!='0'){
                return ret.substr(i);
            }
        }
        return ret;
    }
};

时空复杂度分析

时间复杂度为O(n1*n2+n1+n2)，n1、n2分别为num1、num2的大小

空间复杂度为O(n1+n2)

翻转字符串III：翻转字符串中的单词

题面

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

难度：简单

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = "Let's take LeetCode contest"
 
输出："s'teL 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 num=s.size();
        int front_i=0;
        for(int i=0;i
            if(s[i]==' '){
                if(front_i!=0){
                    front_i+=1;
                }
                swap(s,front_i,i-1);
                front_i=i;  
            }
        }
        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(left
        std::swap(s[left],s[right]);
        left++;
        right--;
        }
    }
    string reverseWords(string s) {
        int num=s.size();
        int front_i=0;
        for(int i=0;i
            if(s[i]==' '){      //找到空格的位置
                if(front_i!=0){
                    front_i+=1;
                }
                swap(s,front_i,i-1);
                front_i=i;  
            }
        }
        //处理下最后一个词
        if(front_i!=0){
            front_i+=1;
        }
        swap(s,front_i,num-1);
        return s;
    }
};

第二种：这种方法我第一次没写出来，那个循环给我绕晕了。这种方法挺好的，得多写几遍！！！

class Solution {
public:
    string reverseWords(string s) {
        int num=s.size();
        int i=0;
        while(i
            int start=i;
            while(i' '){   //注意看这个循环条件！！要加上i
            i++;
            }  
            //当出了循环，str[i]就是空格
            int left=start;
            int right=i-1;
            while(left
                swap(s[left],s[right]);
                left++;
                right--;
            }
​
            while(i' '){  
                i++;
            }
        }
        return s;
    }
};

反思：

第二种思路我当时没写出来，问题就出在那个大循环while(i

while(i
{
    i++;
}

这个框架太经典了，结果限制住了我的思路。实际上，我不应该先把i++;写上的，后面得把这个循环多写几遍，多体会一下。

然后就是要注意，大while()里包小while()，小while()加上大while()的判断条件，会更安全，不容易越界。

思路2 暴力解法

思路1里，我们是手动翻转字符串的，但实际上可以直接用库里的reverse、find函数。

思路2则不用遍历字符串的每一个字符，而是用find找到空格，，然后从空格的后一个 接着去找 下一个空格。

当没有空格时，说明是最后一个单词，翻转，然后break跳出循坏。

注意，这种写法，循环里也没有经典的"i++;"，所以不要一写循环就把i++;给添上，不要 被习惯限制住思路！

实现

class Solution {
public:
    string reverseWords(string s) {
        int num=s.size();
        int i=0;
        while(i
            size_t pos=s.find(' ',i);   //注意这里用size_t
            if(pos!=string::npos){
                reverse(s.begin()+i,s.begin()+pos);  //因为是从i开始找的，所以要加i
                i=pos+1;                           //现在要从空格的下一位开始找
            }                                     //注意reverse是左闭右开，右边是开区间
            else{
                reverse(s.begin()+i,s.end());   //没有空格了，说明这已经是最后一个单词了
                break;
            }
        }
        return s;
    }
};