【刷题】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♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

相关文章
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
4天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
4天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
4天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
4天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
4天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
4天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
4天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数