Add Two Numbers 题型总结

Add two numbers题型一般以字符串/链表/数组/二进制形式,输入两个数字,以相应形式输出两数之和。非整型数的形式,会产生溢出问题,因此一般采用加法原理进行逐位相加运算。注意不同题目corner case的单独处理。

这道题有6个同类题。

  1. Add Two Numbers

原题: https://leetcode.com/problems/add-two-numbers/

以链表形式输入两个非负整数,每个节点包含一个数字,数字以倒序存储(Most Significant Digit在表尾)。以链表形式输出两数之和。

示例:
输入:(2 - > 4 - > 3)+(5 - > 6 - > 4)

输出:7 - > 0 - > 8
说明:342 + 465 = 807。
思路:
输入的表头是Least Significant Digit,正好符合运算规则,因此可以直接逐位相加。输出是链表表头,以倒序存储数字,所以每位运算往链表后延申。

算法:

1.i从表头开始,第一个数第i位与第二个数第i位相加,结果存入输出的第i位和第i+1位,即sum%10存在本位,sum/10(进位)存入下一位数

2.i向表尾移动,重复上一步。一个数字移动到表尾后,只存另一个数字,直到所有位数存完,包括进位
3.输出结果的表头

989. Add to Array-Form of Integer

原题:https://leetcode.com/problems/add-to-array-form-of-integer/
输入非负整数的数组形式,即从左到右顺序的数字数组,以数组形式输出该数与一整数之和。

示例:

输入:A = [2,1,5],K = 806
输出:[1,0,2,1]
说明:215 + 806 = 1021

思路
输入数字的Most Significant Digit在数组尾,要从后往前逐位相加,对于整型数,可以把每一位取出来相加。输出链表数组,从左到右顺序,因此每位运算往链表数组头添加。

算法:

1.i从数组尾开始,取数组第i位,整型数最后一位(num%10),相加的结果存在输出的第i位和第i-1位,即sum%10存在本位,sum/10(进位)存入下一位数
2.i向数组头移动,整型数最后一位前移1位(值/10),重复上一步,数组移到头或者整型数位计算完,只取另一个数,直到所有数位存完,包括进位
3.输出结果数组链表

415. Add Strings

原题:https://leetcode.com/problems/add-strings/
输入字符串形式的非负整数,输出字符串形式的两数之和。

思路:

字符串形式的整数Least Significant Digit在串尾,直接从串尾往前逐位相加。输出是字符串形式整数,可以把每位相加结果append在串尾后,用StringBuilder的reverse反转输出(String没有这个方法)。空串做corner case处理。

算法:

1.i从串尾开始,第一个数的第i位和第二个数的第i位相加,结果存在输出的第i位和第i+1位,即sum%10存在本位,sum/10(进位)存入下一位数

2.i向字符串头移动,重复上一步,一个数移动到串头时,只计算另一个数的该位,直到所有位数存入输出,包括
3.输出反转的字符串

67. Add Binary

原题:https://leetcode.com/problems/add-binary/
输入两个字符串形式的二进制数(只包含字符0或1),输出二进制字符串形式的两数之和。

示例:

    输入:a =“11”,b =“1”

输出:“100”

思路:

字符串形式的数字从串尾,以二进制的加法规则逐位计算。输出是字符串,可以每位计算结果append,输出时反转字符串。

算法:

1.i从串尾开始,第一个数的第i位和第二个数的第i位相加,结果存在输出的第i位和第i+1位,即sum%2存在本位,sum/2(进位)存入下一位数
2.i往字符串头移动,重复上一步,一个数移动到串头时,只计算另一个数的该位,直到所有数位存入输出,包括进位
3.输出反转的字符串

445. Add Two Numbers II

原题:https://leetcode.com/problems/add-two-numbers-ii/
输入链表形式的两个整型数,Most Significant Digit在表头,输出相同链表形式的两数之和。

示例:

输入:(7 - > 2 - > 4 - > 3)+(5 - > 6 - > 4)
输出:7 - > 8 - > 0 - > 7

思路:

此题输入链表形式与之前都不同,在不修改链表的前提下,实现先访问的数字后运算,可以联想到先进后出的栈结构。因此使用栈将链表的数字反向存储起来,再依次取出,以加法规则进行计算。输出是相同形式的链表头,所以每位计算结果往表头添加。

算法:

1.将两个链表的每个节点的数字,分别存入两个栈
2.取每个栈的数,相加结果的sum%10存在本位,加入结果的链表头,sum/10存入下一位
3.重复上一步,一个栈取空时,只计算另一个栈取出的数,直到所有数位存入输出,包括进位
4.输出结果的表头

371. Sum of Two Integers

原题:https://leetcode.com/problems/sum-of-two-integers/
输入两个整型数,输出两数之和,要求不使用+、-运算。

示例:
输入:a = -2,b = 3
输出:1

思路:

这道题可以考虑数位运算,两数相加的本位是两数的异或(1^0=1, 1^1=0, 0^0=0与加法本位结果一致),进位是上一位两数的与(1&1=0, 1&0=0, 0&0=0与下一位进位结果一致)。输出是最终运算结果。(Java可以用二元位运算符^和&等,直接转为二进制进行位运算)

算法:

1.对每一位进行异或位运算(相加)

2.对每一位进行与位运算(算出下一位的进位)
3.若进位不为0,重复1.2.步,对进位和上一步的和进行加法操作,直到进位为0
4.输出加法结果

43. Multiply Strings

原题:https://leetcode.com/problems/multiply-strings/

输入两个字符串形式的整型数,以字符串形式输出两数之积。

示例:
输入:num1 =“123”,num2 =“456”

输出:“56088”

思路:

观察竖式乘法,可以发现第一个数第i位与第二个数第j位相乘的结果,会存入输出的第i+j位和第i+j+1位。以此规则从串尾逐位计算,输出字符串,因此可以先将结果存入数组(两数相乘长度不大于两数长度和),再转为字符串输出。

算法:

1.i,j从串尾开始,第一个数的第i尾与第二个数的第j尾相乘,结果存入输出的第i+j位和第i+j+1位,即sum%10存入本位,sum/10存入下一位

2.循环向字符串头移动i,j,重复上一步,使每个数的每一位都和另一个数的每一位相乘,直到两个字符串遍历完毕 3.将得到的数组转化为字符串输出
原创: Amy