当前位置:网站首页>LeetCode43.字符串相乘 (大数相乘可用此方法)
LeetCode43.字符串相乘 (大数相乘可用此方法)
2022-08-11 05:16:00 【FussyCat】
leecode题链接: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)或直接将输入转换为整数来处理。
解题思路:
字符串相乘,竖乘式,边乘边加边转换成字符,题解如注释所示。
以下用C语言实现:
#define NUM(ch) ((ch) - '0')
#define CHAR(n) ((n) + '0')
char * multiply(char * num1, char * num2){
if (num1 == NULL || num2 == NULL) {
return NULL;
}
int size1 = strlen(num1);
int size2 = strlen(num2);
if ((size1 == 1 || size2 == 1) && (num1[0] == '0' || num2[0] == '0')) {
/* 两数中有其一为0,则乘积为0 */
return "0";
}
char *result = (char *)malloc(size1 + size2 + 1);
memset(result, '0', size1 + size2 + 1);
int i, j, tmp0, tmp1;
result[size1 + size2] = '\0';
for (i = size1 - 1; i >= 0; i--) {
/* 从个位数开始算 */
for (j = size2 - 1; j >= 0; j--) {
/* 从个位数开始算 */
tmp1 = NUM(result[i + j + 1]) + NUM(num1[i]) * NUM(num2[j]); /* 第i位的num1和第j位的num2相乘, tmp1最大为两位数 */
result[i + j + 1] = CHAR(tmp1 % 10); /* 两位数中的个位数 */
tmp0 = tmp1 / 10 + NUM(result[i + j]); /* 两位数中的十位数+当前已存的数,求和 */
result[i + j] = CHAR(tmp0 % 10); /* 和的个位数 */
if ( i + j - 1 >= 0) {
result[i + j - 1] = CHAR(tmp0 / 10 + NUM(result[i + j - 1])); /* 和的十位数+当前已存的数,求和 */
}
}
}
for (i = 0; i < size1 + size2; i++) {
if (result[i] != '0') {
/* 祛除前缀为0的情况,找到前缀中最后一个0的位置 */
break;
}
}
return (result + i);
}
边栏推荐
猜你喜欢
随机推荐
(3) How Redis performs stress testing
CentOS7静默安装Oracle11g_转载
Django--20实现Redis支持、上下文以及上下文和接口的交互
信息学奥赛
第6章 分支语句和逻辑运算符
pytorch基础之 pytorch 模型开发模板
【转载】如何理解数据集中【训练集】、【验证集】和【测试集】
QT QLabel控件(使用详解)
简单做份西红柿炒蛋778
第二篇 DS5 Armv8 样例工程报错之GCC编译
普林斯顿概率论读本读书笔记(阅读中......)
博客帮助文档
LeetCode刷题Top100之两数之和
redis连接idea
二、Jmeter 核心配置文件
基于 TF-IDF 文本匹配实战详细教程 数据+代码 可直接运行
原生态mongo连接查询代码
(2) Construction of a real-time performance monitoring platform (Grafana+Prometheus+Jmeter)
Redis - the solution to the failure of connecting to the redis server in linux using jedis
【分享】一个免费语料库