前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode 43 | 字符串相乘

leetcode 43 | 字符串相乘

作者头像
ACM算法日常
发布2018-12-24 14:43:26
1.5K0
发布2018-12-24 14:43:26
举报
文章被收录于专栏:ACM算法日常

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

示例 1:

代码语言:javascript
复制
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

代码语言:javascript
复制
输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

  1. 1.num1num2 的长度小于110。
  2. 2.num1num2 只包含数字 0-9
  3. 3.num1num2 均不以零开头,除非是数字 0 本身。
  4. 4.不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。

分析:由于num1和num2的长度小于110,所以不能利用int,long等整型数据的*运算,因为肯定会超出其所能表示的范围。既然不能将其转为整数相乘,让我们可以怎么做呢?对了,我们可以用小学时学的乘法运算竖式来计算,你是否还记得呢~不记得也没事,看下面的示意图你就懂了~

比如我们要算78*4567,我们需要将78的个位依次乘以4567的个位,十位,百位和千位,分别得到56,48,40,32。然后再将7依次乘以其个位,十位,百位和千位,注意需要向左一个位置,然后再将相应位置的数进行相加,该进位的进行进位,最后得到结果356226。

既然我们我们已经理清了解题思路,那你还需要了解一个数学知识,那就是m位数乘以n位数,结果最多为m+n位数。了解了这些,我们就可以按照这种思路来编程实现了~

代码实现

代码语言:javascript
复制
class Solution {
public:
    string multiply(string num1, string num2) {
        int allLen = num1.size() + num2.size();
        vector<int> tmpresult(allLen, 0);
        string result(allLen, '0');
        //模拟手算从最后一位开始处理
        for (int i = num1.size() - 1; i >= 0; i--)
            for (int j = num2.size() - 1; j >= 0; j--)
                tmpresult[i + j + 1] += (num1[i] - '0')*(num2[j] - '0');

        //进位
        for (int i = allLen - 1; i>0; i--)
        {
            if (tmpresult[i]>9)
            {
                tmpresult[i - 1] += tmpresult[i] / 10;
                tmpresult[i] %= 10;
            }
        }
        //转换成字符串
        for (int i = allLen - 1; i >= 0; i--)
            result[i] = tmpresult[i] + '0';

        if (result.find_first_not_of('0') == string::npos)
            return "0";//排除全0的情况
        return result.substr(result.find_first_not_of('0'), string::npos);
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-12-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档