LeetCode43. 字符串相乘(大数相乘)

2024-04-28 20:18

本文主要是介绍LeetCode43. 字符串相乘(大数相乘),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

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

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

说明:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/multiply-strings

乘法计算

首先我们得先了解一下竖式的计算过程:

​ 我们应该从后往前计算,一个数的第i位乘上另一个数的第j位,就应加在积的第i+j-1位上,“过了10 ”则要向上面进位就行了,该数只需保留该数mod10后的一位数字,如:

在这里插入图片描述

​ 如上图中的738是由数字123乘以数字456 的最后一位数6得来,3 * 6 = 18,所以保留8,进位1;2 * 6 = 12,加上前一位的进位1,最终等于13,所以应该保留3,进位1; 最后的1 * 6 = 6,加上上一位的进位1后,最终等于7,座椅最终结果为738。其他位上的数也是进行一样的计算,最后相同位数上的数字相加得出最终的结果。

​ 由上图可以看到,123 * 6 的结果 738 的最后一位应与 6 对其,123 * 5 的结果 615 的最后一位应与 5 对齐,同理 492 的最后一位应与 4 对齐,下面代码中使用变量 ind 来记录当前数字对齐的位数。

代码实现

/*** @param {string} num1* @param {string} num2* @return {string}*/
var multiply = function(num1, num2) {//其中一个数字为零时,乘积为0,直接返回0if(num1 == '0' || num2 == '0') return '0';var res = [],   // res->保存结果flag = 0,	//flag->保存进位ind = 0;	//ind->当前数字对齐的位数//遍历第一个数的每一位for(let i = num1.length - 1; i >= 0; i--){//遍历第二个数的每一位for(let j = num2.length - 1; j >= 0; j--){//保存计算结果let temp = parseInt(num1[i]) * parseInt(num2[j]) + flag;//注意加上flag(进位)flag = Math.floor(temp / 10);//更新进位数//如果当前计算位置大于res的长度,直接将结果push(接到最后一位),注意应该mod 10//因为乘法是倒序计算的,所以位置应该为 num2.length - 1 - j + indif((num2.length - 1 - j + ind) >= res.length) res.push(parseInt(temp) % 10);else{//计算结果应该加上该位置上的数if((res[num2.length - 1 - j + ind] + (parseInt(temp) % 10)) > 9) flag++;res[num2.length - 1 - j + ind] = (res[num2.length - 1 - j + ind] + (parseInt(temp) % 10)) % 10;}}if(flag) res[ind + num2.length] = flag;flag = 0;//更新初始位ind++;}//reverse()将列表反置,join('')将列表转换成字符串return res.reverse().join('');
};

这篇关于LeetCode43. 字符串相乘(大数相乘)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/944158

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep