​LeetCode刷题实战415:字符串相加

简介: 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 字符串相加,我们先来看题面:https://leetcode-cn.com/problems/add-strings/

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.


You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.


给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

示例

示例 1:
输入:num1 = "11", num2 = "123"
输出:"134"
示例 2:
输入:num1 = "456", num2 = "77"
输出:"533"
示例 3:
输入:num1 = "0", num2 = "0"
输出:"0"

解题

题目分析:设置两个变量i,j分别从num1和num2的后面开始遍历,取对应位置的数字、前面计算所得进位相加的carry,carry对10的余数放入到结果中,carry/=10。因为两个字符串长度可能不同,要记得处理剩余的字符。最后记得carry可能不等于0,要对其进行处理 .

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i=num1.size()-1,j=num2.size()-1,carry=0;
        string ans;
        while(i>=0&&j>=0){
            carry+=(num1[i]-'0')+(num2[j]-'0'); //从两个字符串的后面开始相加,记得加上进位
            ans.push_back(carry%10+'0'); //将本位的求和结果放到结果中
            carry/=10;
            --i;--j;
        }
        while(i>=0){ //和下面的while,这两个只会执行其中的一个
            carry+=(num1[i]-'0');
            ans.push_back(carry%10+'0');
            carry/=10;
            --i;
        }
        while(j>=0){
            carry+=(num2[j]-'0');
            ans.push_back(carry%10+'0');
            carry/=10;
            --j;
        }
        while(carry!=0){ //最后记得处理可能不为0的carry
            ans.push_back(carry%10+'0');
            carry/=10;
        }
        reverse(ans.begin(),ans.end()); //将结果字符串进行翻转
        return ans;
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

相关文章
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
2天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
2天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
2天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
2天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
2天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
2天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
2天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数