专栏首页李智的专栏leetcode(43)Multiply Strings

leetcode(43)Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题意:给定两个数字(string型),返回二者之积(string型)


解题思路:模拟乘法,分别计算两个数字各位乘积,存在向量tmp中,然后进行进位处理,最后返回结果。 两个m位和n位数字相乘,结果最大不超过m+n位。


AC代码:

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        if (n1 == 0 || n2 == 0)
            return "";//空的话返回空
        if (num1[0] == '0' || num2[0] == '0')
            return "0";//如果有0的话返回"0"
        string res;
        vector<int> tmp(n1 + n2, 0);//tmp长度为m+n,初始化为0
        int k = n1 + n2 - 2;
        for (int i = 0; i<n1; i++)
        {
            for (int j = 0; j<n2; j++)
            {
                tmp[k - i - j] += (num1[i] - '0')*(num2[j] - '0');//这里顺序不要弄错,数字高位在前,保存到tmp向量末尾
            }
        }
        int c = 0;
        for (int i = 0; i<n1 + n2; i++)//处理进位
        {
            tmp[i] += c;
            c = tmp[i] / 10;
            tmp[i] %= 10;
        }
        int i = k + 1;
        //从不是0的最高位算起(因为结果可能小于m+n位)
        while (tmp[i] == 0)
            i--;
        for (; i >= 0; i--)
            res.push_back(tmp[i] + '0');
        return res;
    }
};

void main(void)
{
    string a = "1", b = "1";
    Solution p;
    string res;
    res = p.multiply(a, b);
    cout << res.c_str();
    system("pause");
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode(1)Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    李智
  • 机器学习&数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理)

      找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类...

    李智
  • 常用的机器学习算法比较

    机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开...

    李智
  • LeetCode Weekly Contest 45解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 961. 重复 N 次的元素

    在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。

    Michael阿明
  • 校招试题 n个数里最小的k个 stringstream运用

    Kindear
  • LeetCode 1255. 得分最高的单词集合(回溯)

    你将会得到一份单词表 words,一个字母表 letters (可能会有重复字母),以及每个字母对应的得分情况表 score。

    Michael阿明
  • 11-散列1 电话聊天狂人 (25分)

    输入首先给出正整数NN(\le 10^5≤10 ​5 ​​ ),为通话记录条数。随后NN行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的1...

    AI那点小事
  • 中文分词实践(基于R语言)

    背景:分析用户在世界杯期间讨论最多的话题。 思路:把用户关于世界杯的帖子拉下来,然后做中文分词+词频统计,最后将统计结果简单做个标签云. 后续:中文分词是中文...

    机器学习AI算法工程
  • BZOJ3073: [Pa2011]Journeys(线段树优化建图 Dijkstra)

    attack

扫码关注云+社区

领取腾讯云代金券