【刷题】Leetcode 415 字符串相加和 34 字符串相乘

叫我龙翔

发布于 2024-03-11 08:34:03

1010

发布于 2024-03-11 08:34:03

文章被收录于专栏：就业 C++ 综合学习

Leetcode 415 字符串相加

题目描述

逻辑很简单，对应位置相加，并进位即可。

思路一（模拟大法版！！！）

本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位？因此我们只要将这个过程用代码写出来即可。

class Solution {
public:
    string addStrings(string num1, string num2) {

    int carry = 0;

    string::reverse_iterator it1 = num1.rbegin() ;
    string::reverse_iterator it2 = num2.rbegin() ;
    string res = "";

    while (it1 != num1.rend() || it2 != num2.rend() || carry) {

        int n1 = 0, n2 = 0;
        if (it1 != num1.rend()) {
            n1 = *it1 - '0';
            it1++;
        }
        if (it2 != num2.rend()) {
            n2 = *it2 - '0';
            it2++;
        }
        int result = n1 + n2 + carry;

        res += (result % 10) + '0';
        carry = result / 10;

    }

    reverse(res.begin(), res.end());

        return res;
    }
};

来看效果：

非常好！！！！！！过啦！！！！！！！！

Leetcode 34 字符串相乘

题目描述

根据描述，这道题实际上就是模拟一下乘法运算，这是又又又用到了乘法器原理（实际上就是竖式运算），不得不说竖式运算真的是神！！！如果要用竖式乘法就要分布相乘，然后在加到一起，这时又会用到字符串相加的知识。所以这道题可谓一箭双雕。该题的难点应该是如何保证模拟过程的顺利进行。

思路一（模拟大法版）

两个乘数选择其一进行逐个相乘操作
每次相乘获得一个数并对应相对的数量级
每次相加到一起这样就完成我们的操作。

如果num和num2之一是0，则直接将0作为结果返回即可。

如果num和num2都不是0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num，乘数是num2。

需要注意的是，num2除了最低位以外，其余的每一位的运算结果都需要补0。 我们进行一下图解：

这样就看见进行我们的代码编写工作了！！！干就完了！如果看不出错误请在VS中进行调试哦！

class Solution {
public:
	//求和函数
    string addStrings(string num1, string num2) {
		//进位
        int carry = 0;
		//迭代器版
        string::reverse_iterator it1 = num1.rbegin();
        string::reverse_iterator it2 = num2.rbegin();
        string res = "";
		//加完为止
        while (it1 != num1.rend() || it2 != num2.rend() || carry) {
		// 进行计算
            int n1 = 0, n2 = 0;
            if (it1 != num1.rend()) {
                n1 = *it1 - '0';
                it1++;
            }
            if (it2 != num2.rend()) {
                n2 = *it2 - '0';
                it2++;
            }
            // 结果
            int result = n1 + n2 + carry;
			//该位置 为结果取余数
            res += (result % 10) + '0';
            //进位
            carry = result / 10;

        }
		//不要忘记反转！！！
        reverse(res.begin(), res.end());

        return res;
    }

    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        //乘数1 
        int p1 = num1.size() - 1;

        string ans = "0";
        while (p1 >= 0) {

            //乘数2
            int p2 = num2.size() - 1;
            //开始乘  
            //数字 1  进位数  结果
            int carry = 0; string tmp = "";
            while (p2 >= 0 || carry) {
				//进行计算
                int n1 = 0, n2 = 0;
                if (p1 >= 0) {
                    n1 = num1[p1] - '0';
                }
                if (p2 >= 0) {
                    n2 = num2[p2] - '0';
                    p2--;
                }
				//该步的结果
                int result = n1 * n2 + carry;
                tmp += result % 10 + '0';
                carry = result / 10;

            }
			//不要忘记反转！！！
            reverse(tmp.begin(), tmp.end());
            //对应数量级一定要搞清楚
            for (int i = 0; i < num1.size() - p1 - 1; i++) {
                tmp += '0';
            }
            //加到答案中
            ans = addStrings(ans, tmp);
            p1--;
        }
        return ans;
    }
};

来看效果：