经典题记录 字符串相加/相乘

1. LeetCode 415 字符串相加

代码一：代码简短，但需要借助额外的一个string来保存结果，更占用内存。

class Solution {
public:
    string addStrings(string num1, string num2) {
        string ans="";
        int size1=num1.size();
        int size2=num2.size();
        int size=max(size1,size2);
        int flag=0;  //表示进位
        for(int i=size1-1,j=size2-1;i>=0||j>=0||flag>0;i--,j--){
            int x=i<0?0:num1[i]-'0';
            int y=j<0?0:num2[j]-'0';
            flag=flag+x+y;
            char ch=(flag%10)+'0';
            ans=ch+ans;
            flag=flag/10;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码二：相比代码一行数多点，但是运行时间短一点，内存占用更少。

string add(string str1,string str2){ //字符串相加
    int size1 = str1.size();
    int size2 = str2.size();
    if(size1>size2){
        for (int i = 0; i < size1 - size2;i++)
            str2 = "0" + str2;
    }
    if(size2>size1){
        for (int i = 0; i < size2 - size1;i++)
            str1 = "0" + str1;
    }
    int flag = 0;
    int size = max(size1, size2);
    for (int i = size - 1; i >= 0;i--){
        flag = flag + (str1[i] - '0') + (str2[i] - '0');
        str1[i] = (flag % 10)+'0';
        flag /= 10;
    }
    if(flag){
        char x = flag + '0';
        str1 = x + str1;
    }
    return str1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode 43 字符串相乘

代码：

class Solution {
public:
    string add(string str1,string str2){ //数字字符串相加
        string str="";
        int flag=0;
        for(int i=str1.size()-1,j=str2.size()-1;i>=0||j>=0;i--,j--){
            int x =i<0?0:str1[i]-'0'; //i等于0表示最高位了，i<0时前面没有数字了
            int y =j<0?0:str2[j]-'0'; //j等于0表示最高位了，j<0时前面没有数字了
            flag+=x+y; //当前位的和
            char ch=flag%10+'0';
            flag/=10;
            str=ch+str;
        }
        if(flag){
            char x = flag + '0';
            str = x + str;
        }
        return str;
    }

    string multiply(string num1, string num2) { //数字字符串相乘
        if(num1=="0"||num2=="0")
            return "0";
        string ans=""; 
        for(int i=num2.size()-1;i>=0;i--){
            char ch=num2[i];
            string tmp="";
            int flag=0;
            for(int j=num1.size()-1;j>=0;j--){
                int x=num1[j]-'0';
                int y=ch-'0';
                int n=x*y+flag;
                flag=n/10;//进位
                char a=n%10+'0';
                tmp=a+tmp;
            }
            if(flag){
                char x=flag+'0';
                tmp=x+tmp;
            }
            for(int k=0;k<num2.size()-1-i;k++) //后面补零
                tmp+="0";
            ans=add(ans,tmp);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47