【C++】415.字符串相加

这篇具有很好参考价值的文章主要介绍了【C++】415.字符串相加。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述:

给定两个字符串形式的非负整数 num1num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger),也不能直接将输入的字符串转换为整数形式。

示例1:

输入:num1 = "11", num2 = "123"
输出:"134"

示例 2:

输入:num1 = "456", num2 = "77"
输出:"533"

示例 3:

输入:num1 = "0", num2 = "0"
输出:"0"

提示:

  • 1 <= num1.length, num2.length <= 104
  • num1num2 都只包含数字 0-9
  • num1num2 都不包含任何前导零

思路分析

我们先假设给定的不是字符串形式的数字,而是正常的非负整数,那么两数相加就遵循正常的加法运算,即个位数与个位数相加,十位数与十位数相加,依此类推。如果该位计算结果大于9,则向前进位。那么对于字符串形式的数字,我们就需要先将字符数字转换为数值数字,而在转换之前,我们首先要做到能对字符串进行遍历,遍历字符串的方式有很多,这里我们选择比较简单的下标+方括号的形式来进行访问。由于数字相加是由末尾开始,所以在这里我们也一样先拿到字符串最后一个元素的下标:

int end1 = num1.size() - 1;
int end2 = num2.size() - 1;

拿到最后一个元素的下标后,就可以开始进行运算了。而在运算前,我们需要先将字符数字转换为数值数字。除此之外,在转换前,我们还需要先判断下标是否为0,如果为0则说明该字符串已经遍历完了,直接置零即可。所以我们可以这样写:

int val1 = 0;//默认给0
if (end1 >= 0)//如果字符串还没有遍历完,则进行转换
	val1 = num1[end1] - '0';
int val2 = 0;
if (end2 >= 0)
	val2 = num2[end2] - '0';

如果觉得这个地方写得有点啰嗦,那么我们也可以用三目运算符进行修改:

int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
int val2 = end2 >= 0 ? num2[end2] - '0' : 0;

得到当前字符所代表的数值后,下面我们就可以对两个值进行相加。相加的时候,需要注意的是上一位的进位也要加进来,我们可以将进位初始化为0,这样末位相加的时候虽然没有进位但也可以用同一个表达式计算:

int next = 0;//进位
int ret = val1 + val2 + next;

加完之后,我们就需要对ret进行判断,如果ret大于9,则说明需要进位,注意这里不要忘记对ret小于9的情况进行处理,因为如果ret小于9的话next就需要置零,如果这里不进行处理,那么之前的进位就会一直得到保留并继续和高位相加导致运算结果出错:

if (ret > 9)//ret大于9的话next进位
{
	ret -= 10;
	next = 1;
}
else//否则next置零
{
	next = 0;
}

实际上,这个地方我们也可以进行简化:

next = ret / 10;//超过10的值除就是1,进位
ret = ret % 10;//模10留下余数

运算结束后,我们就可以将得到的值放回一个新的字符串中作为结果。这里需要注意的是,由于我们是从末位开始计算,因此每得到一位的值应该插入在上一个值的前面:

string strret;
strret.insert(0, 1, '0' + ret);//表示在字符串strret的首位插入1个'0' + ret所表示的字符

到这里,我们一位相加的过程就算结束了,继续往下进应该是高一位相加,直到字符串遍历完毕,因此,刚才的代码我们可以放在一个循环中:

while (end1 >= 0 || end2 >= 0)//end1和end2只要有一个不为0则说明字符串还没有遍历完,继续循环
{	
	int val1 = end1 >= 1 ? num1[end1] - '0' : 0;
	int val2 = end2 >= 1 ? num2[end2] - '0' : 0;
	int ret = val1 + val2 + next;
		
	next = ret / 10;
	ret = ret % 10;
	strret.insert(0, 1, '0' + ret);
	strret += ('0' + ret);
	--end1;
	--end2;
}

当循环结束时,我们可能会觉得这个时候strret中存放的字符串代表的就是相加后的值了,但是实际上,如果刚才的循环中最高位相加还产生了进位,由于此时字符串已经遍历到最高位,循环将不再进行,所以出了循环之后我们还需要再进行一次判断,如果有进位,就需要把进位插在首字符的位置:

if (next == 1)
		strret.insert(0, 1, '1');
return strret;

完整代码

string addStrings(string num1, string num2) 
{
	int end1 = num1.size() - 1;
	int end2 = num2.size() - 1;
	int next = 0;
	string strret;
	while (end1 >= 0 || end2 >= 0)
	{
		int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
		int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
		int ret = val1 + val2 + next;
		
		next = ret / 10;
		ret = ret % 10;
		strret.insert(0, 1, '0' + ret);
		--end1;
		--end2;
	}
	if (next == 1)
		strret.insert(0, 1, '1');
	return strret;
}

运行结果:

【C++】415.字符串相加,Leetcode/牛客网,c++,数据结构,leetcode

从运行结果可以看到,当前我们的代码效率还是比较低的,那么有哪些地方可以优化呢?

后续优化

在刚才的代码中,最影响效率的其实是下面这段代码:

strret.insert(0, 1, '0' + ret);

其原因在于,每插入一个字符,都要将原来的字符向后移动一位,也就是说插入第一个值时会挪一下,插入第二个值会挪两下,依此类推,插入第n个值时会挪n下,可以看到挪动的次数会以一个等差数列的形式呈现,而由等差数列的求和公式可知这是一个n2的数量级,也就是说它的时间复杂度为n2

而如果我们采用尾部插入的形式,每次插入就不需要对原来的数据进行移动,只需要在插入完成后将字符串倒置一下即可;除此之外,由于每次插入都需要扩容,所以为了进一步提高效率,我们可以事先把需要的空间开辟出来,而这个空间刚好就是长的字符串加1。那么根据前面的分析,尾插我们可以用+=实现,而在标准库函数中,可以实现逆置的函数为reversestring类中有用来开辟空间的reserve,那么我们就可以对代码进行如下修改:

string addStrings(string num1, string num2)
{
	int end1 = num1.size() - 1;
	int end2 = num2.size() - 1;
	int next = 0;
	string strret;
	strret.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);//提前开辟空间
	while (end1 >= 0 || end2 >= 0)
	{
		int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
		int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
		int ret = val1 + val2 + next;

		next = ret / 10;
		ret = ret % 10;
		strret += ('0' + ret);//尾插
		--end1;
		--end2;
	}
	if (next == 1)
		strret += '1';
	reverse(strret.begin(), strret.end());//倒置
	return strret;
}

运行结果:

【C++】415.字符串相加,Leetcode/牛客网,c++,数据结构,leetcode

可以看到,优化过后的代码运行起来效率就很高了。文章来源地址https://www.toymoban.com/news/detail-716816.html

到了这里,关于【C++】415.字符串相加的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++初阶】String在OJ中的使用(一):仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加

    前言: 🎯个人博客:Dream_Chaser 🎈博客专栏:C++ 📚本篇内容:仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加 目录 917.仅仅反转字母  题目描述: 387.字符串中的第一个唯一字符 题目描述: HJ1 字符串最后一个单词的长度

    2024年04月09日
    浏览(108)
  • 【每日挠头算法(4)】字符串相加|字符串相乘

    点我直达~ 1.将两个字符串从右往左开始进行相加,使用一个变量 ans 表示进位,如果两个字符串的个位加法和大于10,那么让进位+1,个位和再%10,然后将结果存入到新的字符串 strRet 中 2.两个字符串的十位和十位继续相加,并且需要加上个位的进位 ans ,步骤同1 3.这样不断相

    2024年02月09日
    浏览(57)
  • leetcode刷题(字符串相加、包含每个查询的最小区间、模拟行走机器人、环形子数组的最大和、满足不等式的最大值、四数之和、树中距离之和)

    目录 1、字符串相加 2、包含每个查询的最小区间 3、模拟行走机器人 4、环形子数组的最大和 5、满足不等式的最大值 6、四数之和 7、 树中距离之和

    2024年02月10日
    浏览(47)
  • 字符串相加(力扣)

    Problem: 415. 字符串相加 创建一个StringBuilder对象使用append方法追加每位数字相加,使用双指针的方式,指针i,j分别指向num1和num2的每位数字,从后往前,进位用carry存储着。 得到答案后,然后反转StringBUilder再转化为String即可。 时间复杂度: O(max) max表示两个字符串中最长的一个

    2024年02月16日
    浏览(41)
  • 面试热题(字符串相加)

    给定两个字符串形式的非负整数  num1  和 num2  ,计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库(比如  BigInteger ), 也不能直接将输入的字符串转换为整数形式。       字符串相加这道题其实对于很多人来说是有挑战性的,因为有进

    2024年02月14日
    浏览(41)
  • 【力扣每日一题】2023.7.17 字符串相加

    题面很简单,就是要将两个字符串看作是数字然后相加,将最后结果转为字符串返回即可. 看到这题我的第一反应是直接转成数字再相加再转成字符串,像是这样: 但这样就不符合题目要求了( 这不是主要原因 ) ,并且遇到大数就无法转成整型也无法计算了. 所以需要像是我们列竖式

    2024年02月16日
    浏览(30)
  • Leetcode 75——1768.交替合并字符串 解题思路与具体代码【C++】

    1768. 交替合并字符串 - 力扣(LeetCode) 给你两个字符串  word1  和  word2  。请你从  word1  开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。 返回  合并后的字符串  。 1 = word1.length, word2.length = 100

    2024年02月07日
    浏览(79)
  • Leetcode每日一题:2337. 移动片段得到字符串(2023.8.21 C++)

    目录 2337. 移动片段得到字符串 题目描述: 实现代码与解析: 双指针 原理思路:         给你两个字符串  start  和  target  ,长度均为  n  。每个字符串  仅  由字符  \\\'L\\\' 、 \\\'R\\\'  和  \\\'_\\\'  组成,其中: 字符  \\\'L\\\'  和  \\\'R\\\'  表示片段,其中片段  \\\'L\\\'  只有在其左侧直接

    2024年02月11日
    浏览(38)
  • LeetCode | C++ 动态规划——583. 两个字符串的删除操作、72. 编辑距离

    583题目链接 做法一: 本题和1143.最长公共子序列基本相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。 做法二: 本题和115.不同的子

    2024年02月16日
    浏览(53)
  • Java 编程实例:相加数字、计算单词数、字符串反转、元素求和、矩形面积及奇偶判断

    示例 输出 解释 首先,声明两个 int 类型的变量 x 和 y ,并分别赋值为 5 和 6。 然后,使用 + 运算符将 x 和 y 相加,并将结果赋给变量 sum 。 最后,使用 System.out.println() 方法打印 sum 的值。 示例 输出 解释 首先,导入 Scanner 类,用于读取用户输入。 然后,声明三个 int 类型的

    2024年03月19日
    浏览(89)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包