- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
本文关键词:Leetcode, 力扣,字符串相加,两数相加,两数之和,求加法,代码模板,Python, C++, Java
题目地址:https://leetcode-cn.com/problems/add-stringsopen in new window
给定两个字符串形式的非负整数 num1
和 num2
,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 BigInteger
), 也不能直接将输入的字符串转换为整数形式。
示例1:
输入:num1 = "11", num2 = "123"
输出:"134"
示例2:
输入:num1 = "456", num2 = "77"
输出:"533"
示例3:
输入:num1 = "0", num2 = "0"
输出:"0"
提示:
1、 1<=num1.length,num2.length<=10^4
;
2、 num1
和num2
都只包含数字0-9
;
3、 num1
和num2
都不包含任何前导零;
不使用大整数的情况下,计算两个字符串表示的数字的和。
加法是我们上小学的时候开始学习的第一种数学运算。
在算法题中,「求加法」问题大多考察「列竖式」求和。
题目中,「两数之和」通常与其他形式表示的数字结合起来:
做法都是非常类似的,本质是在考察各种数据表示形式:字符串,链表,数组,二进制。
我们只要掌握了用「列竖式」求「两数之和」的方法,这类题目全都可以秒杀。
我们先回顾一下十进制加法的计算过程:
使用「竖式」计算十进制的加法的方式:
1、 两个「加数」的右端对齐;
2、 从最右侧开始,从右向左依次计算对应的两位数字的和,如果有进位需要加上进位如果和大于等于10,则把和的个位数字计入结果,并向前面进位;
3、 重复步骤2;
4、 当两个「加数」的每个位置都计算完成,如果最后仍有进位,需要把进位数字保留到计算结果中;
1、 不可以把字符串表示的「加数」先转化成int
型数字再求和,因为可能溢出;
2、 两个「加数」的字符串长度可能不同;
3、 在最后,如果进位carry不为0,那么最后需要计算进位;
4、 注意结果数字是否为低位结果在前,根据题目要求判断最后是否要反转结果;
题目要我们求两个字符串形式表示的数字相加,按照「列竖式」的方法进行求解即可。
1、 while(p1>=0||p2>=0||carry!=0)
含义:
1、 字符串num1
和num2
只要有一个没遍历完,那么就继续遍历;
2、 如果字符串num1
和num2
都遍历完了,但是最后留下的进位carry!=0
,那么需要把进位也保留到结果中;
2、 取digit
的时候,如果字符串num1
和num2
中有一个已经遍历完了(即p1<0或者p2<0),则认为num1
和num2
的对应位置是0;
该代码可以作为「求加法」的模板。
Java 语言代码如下:
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder(); // 返回结果
int p1 = num1.length() - 1; // 标记遍历到 num1 的位置
int p2 = num2.length() - 1; // 标记遍历到 num2 的位置
int carry = 0; // 进位
while (p1 >= 0 || p2 >= 0 || carry != 0) { // num1 没遍历完,或 num2 没遍历完,或进位不为 0
int digit1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0; // 当前 num1 的取值
int digit2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0; // 当前 num2 的取值
int add = digit1 + digit2 + carry; // 当前位置相加的结果
carry = add >= 10 ? 1 : 0; // 是否有进位
add = add >= 10 ? add - 10 : add; // 去除进位后留下的数字
res.append(add); // 把去除进位后留下的数字拼接到结果中
p1 --; // 遍历到 num1 的位置向左移动
p2 --; // 遍历到 num2 的位置向左移动
}
return res.reverse().toString(); // 把结果反转并返回
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C++代码如下:
class Solution {
public:
string addStrings(string num1, string num2) {
const int M = num1.size();
const int N = num2.size();
string res;
int p1 = M - 1;
int p2 = N - 1;
int carry = 0;
while (p1 >= 0 || p2 >= 0 || carry > 0) {
int cur1 = p1 >= 0 ? num1[p1] - '0' : 0;
int cur2 = p2 >= 0 ? num2[p2] - '0' : 0;
int sum = cur1 + cur2 + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
res += to_string(sum);
p1 --;
p2 --;
}
reverse(res.begin(), res.end());
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Python 代码如下:
class Solution(object):
def addStrings(self, num1, num2):
p1 = len(num1) - 1
p2 = len(num2) - 1
res = ""
carry = 0
while p1 >= 0 or p2 >= 0 or carry > 0:
digit1 = int(num1[p1]) if p1 >= 0 else 0
digit2 = int(num2[p2]) if p2 >= 0 else 0
sum = digit1 + digit2 + carry
carry = 1 if sum >= 10 else 0
sum = sum - 10 if sum >= 10 else sum
res += str(sum)
p1 -= 1
p2 -= 1
return res[::-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
看完本文,你可以解决以下题目:
1、 「求加法」系列题目都不难,其实就是「列竖式」计算;
2、 需要注意的是:
1、 while循环结束条件;
2、 遍历两个「加数」不要越界;
3、 进位;
4、 最后的结果需要翻转;
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
如何使用 SPListCollection.Add(String, String, String, String, Int32, String, SPListTemplate.QuickLaunchO
我刚刚开始使用 C++ 并且对 C# 有一些经验,所以我有一些一般的编程经验。然而,似乎我马上就被击落了。我试过在谷歌上寻找,以免浪费任何人的时间,但没有结果。 int main(int argc,
这个问题已经有答案了: In Java 8 how do I transform a Map to another Map using a lambda? (8 个回答) Convert a Map>
我正在使用 node + typescript 和集成的 swagger 进行 API 调用。我 Swagger 提出以下要求 http://localhost:3033/employees/sear
我是 C++ 容器模板的新手。我收集了一些记录。每条记录都有一个唯一的名称,以及一个字段/值对列表。将按名称访问记录。字段/值对的顺序很重要。因此我设计如下: typedef string
我需要这两种方法,但j2me没有,我找到了一个replaceall();但这是 replaceall(string,string,string); 第二个方法是SringBuffer但在j2me中它没
If string is an alias of String in the .net framework为什么会发生这种情况,我应该如何解释它: type JustAString = string
我有两个列表(或字符串):一个大,另一个小。 我想检查较大的(A)是否包含小的(B)。 我的期望如下: 案例 1. B 是 A 的子集 A = [1,2,3] B = [1,2] contains(A
我有一个似乎无法解决的小问题。 这里...我有一个像这样创建的输入... var input = $(''); 如果我这样做......一切都很好 $(this).append(input); 如果我
我有以下代码片段 string[] lines = objects.Split(new string[] { "\r\n", "\n" }, StringSplitOptions.No
这可能真的很简单,但我已经坚持了一段时间了。 我正在尝试输出一个字符串,然后输出一个带有两位小数的 double ,后跟另一个字符串,这是我的代码。 System.out.printf("成本:%.2
以下是 Cloud Firestore 列表查询中的示例之一 citiesRef.where("state", ">=", "CA").where("state", "= 字符串,我们在Stack O
我正在尝试检查一个字符串是否包含在另一个字符串中。后面的代码非常简单。我怎样才能在 jquery 中做到这一点? function deleteRow(locName, locID) { if
这个问题在这里已经有了答案: How to implement big int in C++ (14 个答案) 关闭 9 年前。 我有 2 个字符串,都只包含数字。这些数字大于 uint64_t 的
我有一个带有自定义转换器的 Dozer 映射: com.xyz.Customer com.xyz.CustomerDAO customerName
这个问题在这里已经有了答案: How do I compare strings in Java? (23 个回答) 关闭 6 年前。 我想了解字符串池的工作原理以及一个字符串等于另一个字符串的规则是
我已阅读 this问题和其他一些问题。但它们与我的问题有些无关 对于 UILabel 如果你不指定 ? 或 ! 你会得到这样的错误: @IBOutlet property has non-option
这两种方法中哪一种在理论上更快,为什么? (指向字符串的指针必须是常量。) destination[count] 和 *destination++ 之间的确切区别是什么? destination[co
This question already has answers here: Closed 11 years ago. Possible Duplicates: Is String.Format a
我有一个Stream一个文件的,现在我想将相同的单词组合成 Map这很重要,这个词在 Stream 中出现的频率. 我知道我必须使用 collect(Collectors.groupingBy(..)
我是一名优秀的程序员,十分优秀!