LeetCode 字符串专题-蒲公英云

LeetCode 字符串专题

两个字符串直接操作

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。同这题二进制求和

提示：

num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式

// 模拟整数相加
class Solution {
public:
    string addStrings(string num1, string num2) {
        string res = "";
        int i1 = num1.size()-1, i2 = num2.size()-1;
        int add = 0;
        while(i1 >= 0 || i2 >= 0 || add != 0){
            int a = i1 >= 0 ? num1[i1] - '0':0;
            int b = i2 >= 0 ? num2[i2] - '0':0;
            int c = a + b + add;
            res += c % 10 + '0';
            add = c / 10;
            i1--;
            i2--;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

43. 字符串相乘

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

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        //字符串乘法模拟
        int len2 = num2.length();
        string cur1 = multiply2(num1, num2[len2-1]); 
        for(int i=1; i<num2.length(); ++i){
            string cur2 = multiply2(num1, num2[len2-i-1]);
            for(int j=0; j<i; ++j){
                cur2 += '0';
            }
            cur1 = addStrings(cur1, cur2);
        }
        return cur1;
    }
    string multiply2(string num1, char c){
        int len1 = num1.length();
        int add = 0;
        int b = c-'0';
        string cur = "";
        for(int i=0; i<len1; ++i){
            int a = num1[len1-i-1] - '0';
            cur += (a * b + add) % 10 + '0';
            add = (a * b + add) / 10;
        }
        if(add != 0){
            cur += add + '0';
        }
        reverse(cur.begin(), cur.end());
        return cur;
    }
    string addStrings(string num1, string num2) {
        string res = "";
        int i1 = num1.size()-1, i2 = num2.size()-1;
        int add = 0;
        while(i1 >= 0 || i2 >= 0 || add != 0){
            int a = i1 >= 0 ? num1[i1] - '0':0;
            int b = i2 >= 0 ? num2[i2] - '0':0;
            int c = a + b + add;
            res += c % 10 + '0';
            add = c / 10;
            i1--;
            i2--;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};