【leetcode刷题】T74-字符串相加
【题目】
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
num1和num2的长度都小于 5100.num1和num2都只包含数字0-9.num1和num2都不包含任何前导零。- 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
【思路】
设置进位符flag，从字符串最后一位开始累加，注意flag也要加入到累加过程中。
由于num1和num2长度不一样，在累加前，还需要判断是否越界。
为了避免这种情况，我们保持num1长度较大（如果num2长度较大，则和num1互换），前一个过程的累加a+b+flag，累加次数为num2.size()这么多次；后一过程的累加a+flag，累加次数为num1.size()-num2.size()这么多次。
本题需要特别注意数组越界问题。
【代码】
python版本
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
flag = False
# 保证num1更长
if len(num1) < len(num2):
num1, num2 = num2, num1
# 从最后一个元素相加
res = ""
length1 = len(num1)
length2 = len(num2)
for i in range(length2):
tmp =
# 有进位
if flag:
flag = False
tmp =
tmp += int(num1[length1-1-i]) + int(num2[length2-1-i])
if tmp >= :
tmp -=
flag = True
res = str(tmp) + res
# 长度相等
if length1 == length2:
if flag == True:
res = '1' + res
# num1更长，只有num1前部分未计算
else:
if flag == False:
res = num1[:length1-length2] + res
else:
for i in range(length1-length2):
tmp =
# 有进位
if flag:
flag = False
tmp =
tmp += int(num1[length1-length2-1-i])
if tmp >= :
tmp -=
flag = True
res = str(tmp) + res
if flag == True:
res = '1' + res
return res
C++版本
class Solution {
public:
string addStrings(string num1, string num2) {
// 保证num1更长
if(num1.size() < num2.size()){
string num = num1;
num1 = num2;
num2 = num;
}
int len1 = num1.size();
int len2 = num2.size();
string res="";
int tmp;
bool flag=false;
for(int i=; i < len2; i++){
tmp = ;
// 有进位
if(flag){
flag = false;
tmp++;
}
tmp += (num1[len1-1-i] - '0') + (num2[len2-1-i] - '0');
// 大于10，进位
if(tmp >= ){
tmp -= ;
flag = true;
}
res = to_string(tmp) + res;
}
if(flag){
// 有进位，对num1剩余部分进行计算
for(int i=; i < len1-len2; i++){
tmp = ;
// 有进位
if(flag){
flag = false;
tmp++;
}
tmp += (num1[len1-len2-1-i] - '0');
// 大于10，进位
if(tmp >= ){
tmp -= ;
flag = true;
}
res = to_string(tmp) + res;
}
}else{
// 没有进位，将num1剩余部分拼接在res前
res = num1.substr(, len1-len2) + res;
}
if(flag){
res = "1" + res;
}
return res;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读