「算法刷题」数组之大数相加专项汇总（力扣版）

本文记录作者刷题过程中与两数相加相关的题目。

1、数组中的两数相加

989. 数组形式的整数加法（简单难度）

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        vector<int> res;
        int i=num.size()-1;
        int sum=0;
        bool carry=false;
        while(i>=0||k){
            sum=0;
            if(i>=0)sum+=num[i--];
            if(k){
                sum+=k%10;
                k/=10;
            }
            if(carry) sum+=1;
            res.push_back(sum%10);
            carry=sum>=10?true:false;
        }
        if(carry) res.push_back(1);
        reverse(res.begin(),res.end());
        return res;
    }
};

2、字符串中的两数相加

415. 字符串相加（简单难度）

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res;
        // 从右向左同时遍历2个可能不等长的字符串
        int i=num1.length()-1;
        int j=num2.length()-1;
        bool carry=false;
        int sum=0;
        while(i>=0||j>=0){
            sum=0;
            if(i>=0) sum+=num1[i--]-'0';
            if(j>=0) sum+=num2[j--]-'0';
            if(carry) sum+=1;
            res =to_string(sum%10)+res;
            carry=sum>=10?true:false;
        }
        // 如果有多余的进位
        if(carry) res =to_string(1)+res;
        return res;
    }
};

3、二进制中的两数相加

67. 二进制求和（简单难度）

剑指 Offer II 002. 二进制加法（简单难度）

class Solution {
public:
    string addBinary(string a, string b) {
        int i=a.length()-1;
        int j=b.length()-1;
        string res;
        bool carry=false;
        int sum=0;
        // 从右向左同时遍历2个可能不等长的字符串
        while(i>=0||j>=0){
            sum=0;
            if(i>=0) sum+=a[i--]-'0';
            if(j>=0) sum+=b[j--]-'0';
            if(carry) sum+=1;
            res =to_string(sum%2)+res;
            carry=sum>=2?true:false;
        }
        if(carry) res =to_string(1)+res;
        return res;
    }
};

4、链表中的两数相加

剑指 Offer II 025. 链表中的两数相加（中等难度）

445. 两数相加 II（中等难度）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* slow=NULL;//慢指针
        ListNode* fast=head;//快指针
        while(fast!=NULL){
            //保存
            ListNode* temp = fast->next;
            //反转
            fast->next=slow;
            //更新
            slow=fast;
            fast=temp;
        }
        //更新头结点
        head=slow;
        return head;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(-1);//结果链表的虚拟头结点
        ListNode* cur=head;//遍历指针
        l1=reverseList(l1);
        l2=reverseList(l2);
        // 同时遍历2个链表
        int sum=0;
        bool carry=false;//是否需要进位
        while(l1||l2){
            sum=0;
            if(l1!=nullptr){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=nullptr){
                sum+=l2->val;
                l2=l2->next;
            }
            if(carry) sum++;
            // 为结果链表添加一个新的结果
            cur->next=new ListNode(sum%10);
            cur=cur->next;
            carry = sum >= 10 ? true: false;//发现需要进位
        }
        if(carry)   cur->next=new ListNode(1);
        head->next = reverseList(head->next);
        return head->next;
    }
};

###