LeetCode 字符串专题

﹏ヽ暗。殇╰゛Y 2022-10-16 06:09 172阅读 0赞

## 两个字符串直接操作 ##

### [415. 字符串相加][415.] ###

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

提示：

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. 字符串相乘][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;
        }
    };

[415.]: https://leetcode-cn.com/problems/add-strings/
[Link 1]: https://leetcode-cn.com/problems/add-binary/
[43.]: https://leetcode-cn.com/problems/multiply-strings/