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

简介: Leetcode 415 字符串相加


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 字符串相乘

题目描述

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

思路一(模拟大法版)

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

如果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;
    }
};

来看效果:

顺利通过!!!

为我们鼓掌!!!!!!!

送给大家一句我非常喜欢的名言:

我从来不相信什么懒洋洋的自由。我向往的自由是通过勤奋和努力实现的更广阔的人生。——山本耀司

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
25天前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
54 2
|
15天前
|
存储 算法
LeetCode第43题字符串相乘
LeetCode第43题"字符串相乘"的解题方法,通过使用数组存储乘积并处理进位,避免了字符串转换数字的复杂性,提高了算法效率。
LeetCode第43题字符串相乘
|
15天前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
15天前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
|
25天前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
30 3
|
25天前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
13 1
|
25天前
|
Python
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
15 1
|
25天前
|
算法 Python
【Leetcode刷题Python】295. 数据流的中位数
本文介绍了一种使用Python实现的数据结构,用以支持数据流中添加整数并返回当前所有元素的中位数,通过排序列表来计算中位数。
12 1
|
25天前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
15 0
【Leetcode刷题Python】73. 矩阵置零
|
25天前
|
Python
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
15 0