【刷题记录】43. 字符串相乘

简介: 【刷题记录】43. 字符串相乘


一、题目描述


来源:力扣(LeetCode)


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


注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。


示例 1:


输入: num1 = "2", num2 = "3"

输出: "6"


示例 2:


输入: num1 = "123", num2 = "456"

输出: "56088"


提示:


  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零,除了数字0本身。


二丶思路分析


模拟
这道题目不能直接将输入转化为整数,然后计算,那我们可以根据小时候学的数字相乘的竖式计算方法进行模拟。
例如123 * 545

网络异常,图片无法展示
|


从右往左遍历乘数,将乘数的每一位与被乘数相乘得到对应的结果,再将每次得到的结果累加


注意补0 并且 两个长度分别为 nm 的数相乘,长度不会超过 n + m


三、代码实现

```

class Solution {

   public String multiply(String n1, String n2) {

       int n = n1.length(), m = n2.length();

       int[] res = new int[n + m];

       for (int i = n - 1; i >= 0; i--) {

           for (int j = m - 1; j >= 0; j--) {

               int a = n1.charAt(i) - '0';

               int b = n2.charAt(j) - '0';

               int r = a * b;

               r += res[i + j + 1];

               res[i + j + 1] = r % 10;

               res[i + j] += r / 10;

           }

       }

       StringBuilder sb = new StringBuilder();

       for (int i = 0; i < n + m; i++) {

           if (sb.length() == 0 && res[i] == 0) continue;

           sb.append(res[i]);

       }

       return sb.length() == 0 ? "0" : sb.toString();

   }

}

```

复杂度分析


  • 时间复杂度:
    网络异常,图片无法展示
    |
    ,其中 mn分别是num1num2的长度
  • 空间复杂度:O*(m+n)


运行结果


网络异常,图片无法展示
|


总结


这个题目其实带我们重温了一下我们小时候学乘法时候学习的乘法计算过程。只要理解了这个计算的过程。这道题目就比较简单了。

目录
打赏
0
0
0
0
3
分享
相关文章
在Ubuntu 22.04上配置和安装MySQL
以上就是在Ubuntu 22.04上配置和安装MySQL的步骤。这个过程可能看起来有点复杂,但只要按照步骤一步步来,你会发现其实并不难。记住,任何时候都不要急于求成,耐心是解决问题的关键。
336 30
阿里云爸爸发福利!DeepSeek-R1满血版深度体验,4种部署攻略+隐藏羊毛大公开💎
本文介绍了四种部署DeepSeek-R1模型的方式:基于百炼调用满血版API、基于PAI部署、基于函数计算部署和基于GPU云服务器部署。每种方式各有优劣,适合不同需求的用户。其中,基于百炼调用满血版API无需部署,提供满血版模型和100万免费Token,适合快速体验;基于PAI部署适合需要微调模型的用户;基于函数计算部署提供WEB交互界面;基于GPU云服务器部署则适合技术能力强、有硬件资源的用户。方案还提供了免费试用入口和实践体验总结,帮助开发者更好地理解和使用DeepSeek-R1模型。
331 62
EchoMimicV2:阿里推出的开源数字人项目,能生成完整数字人半身动画
EchoMimicV2是阿里蚂蚁集团推出的开源数字人项目,能够生成完整的数字人半身动画。该项目基于参考图片、音频剪辑和手部姿势序列,通过音频-姿势动态协调策略生成高质量动画视频,确保音频内容与半身动作的一致性。EchoMimicV2不仅支持中文和英文驱动,还简化了动画生成过程中的复杂条件,适用于虚拟主播、在线教育、娱乐和游戏等多个应用场景。
2838 5
EchoMimicV2:阿里推出的开源数字人项目,能生成完整数字人半身动画
【优秀python大屏案例】基于python flask的前程无忧大数据岗位分析可视化大屏设计与实现
本文介绍了一个基于Python Flask框架的前程无忧大数据岗位分析可视化大屏系统,该系统通过爬虫技术采集招聘数据,利用机器学习算法进行分析,并以可视化大屏展示,旨在提高招聘市场数据分析的效率和准确性,为企业提供招聘决策支持和求职者职业规划参考。
401 2
整合 200 多项相关研究,大模型终生学习最新综述来了
【9月更文挑战第26天】近年来,大型语言模型(LLMs)在自然语言处理、智能问答及内容生成等领域广泛应用。面对不断变化的数据、任务和用户偏好,LLMs需具备适应能力。传统静态数据集训练方式难以满足需求,因此提出了“终身学习”方法,使模型持续学习新知识并避免遗忘旧知识。最新综述文章整合200多项研究,将终身学习分为内部知识(连续预训练和微调)与外部知识(基于检索和工具)两大类,涵盖12种应用场景,探讨了模型扩展和数据选择等新兴技术。然而,终身学习也面临计算资源、知识冲突及数据安全等挑战。
273 6
JS【详解】Symbol (含Symbol 作为属性名,静态方法for 和 keyFor,11 个内置的 Symbol 值)
JS【详解】Symbol (含Symbol 作为属性名,静态方法for 和 keyFor,11 个内置的 Symbol 值)
174 1
uni-app 64聊天类chat.js封装(一)
`uni-app` 是一个使用 Vue.js 开发所有前端应用的框架,可以编译到iOS、Android、H5以及各种小程序等多个平台。当你提到“64聊天类`chat.js`封装”时,我假设你希望了解如
PolarDB操作报错合集之遇到报错“com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure”,该怎么办
在使用阿里云的PolarDB(包括PolarDB-X)时,用户可能会遇到各种操作报错。下面汇总了一些常见的报错情况及其可能的原因和解决办法:1.安装PolarDB-X报错、2.PolarDB安装后无法连接、3.PolarDB-X 使用rpm安装启动卡顿、4.PolarDB执行UPDATE/INSERT报错、5.DDL操作提示“Lock conflict”、6.数据集成时联通PolarDB报错、7.编译DN报错(RockyLinux)、8.CheckStorage报错(源数据库实例被删除)、9.嵌套事务错误(TDDL-4604)。
885 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问