高精度运算组件

字数统计: 2.4k字 | 阅读时长: 11分

2020-10-14

摘要: 在字符串、数组、链表等数据结构上维护按位的加减乘除，力扣 8 八道题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在计算机中表示整数一般是通过 int、long long 等类型，这些类型能表示的数字都有大小限制。但有时在应用中我们需要处理更大的数字，这时就不能用内置的 int、double 来做了。

为了实现大整数的加减乘除等运算，高精度运算是一种解法，也就是用字符串、数组、链表等线性数据结构维护整数的各个位的数字。比如用字符串表示数字的话，一个字符代表一个整数，字符串中的每个字符代表整数的每个位，通过在字符串上实现按位的加减乘除，最终来实现大整数的加减乘除。

根据需要，高精度运算还可以实现大整数的比较、取模等运算。把加减乘除、取模、比较等操作全都实现的话，完整代码非常长。本文我们以力扣上的 8 道题来看看在字符串、数组、链表等数据结构上如何实现按位加减乘除。

$1 字符串表示数

1-1 加法

题目1：415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

代码 (C++)

class Solution {
public:
    string addStrings(string num1, string num2) {
        string result;
        int carry = 0, i = num1.size() - 1, j = num2.length() - 1;
        while(i >= 0 || j >= 0 || carry != 0){
            if(i >= 0) carry += num1[i--] - '0';
            if(j >= 0) carry += num2[j--] - '0';
            result = char(carry % 10 + '0') + result;
            carry /= 10;
        }
        return result;
    }
};

题目2：67. 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

代码 (C++)

class Solution {
public:
    string addBinary(string a, string b) {
        int m = a.size();
        int n = b.size();
        if(m > n) return addBinary(a, string(m - n, '0') + b);
        if(m < n) return addBinary(string(n - m, '0') + a, b);
        // a 和 b 的长度相等
        string result;
        char carry = '0';
        for(int i = m - 1; i >= 0; --i)
        {
            char iter_a = a[i], iter_b = b[i];
            pair<char, char> bit_result = bitadd(iter_a, iter_b, carry);
            result = bit_result.first + result;
            carry = bit_result.second;
        }
        if(carry == '1')
            result = '1' + result;
        return result;
    }

private:
    pair<char, char> bitadd(char a, char b, char carry)
    {
        int sum = (a - '0') + (b - '0') + (carry - '0');
        if(sum == 0) return pair<char, char>('0', '0');
        if(sum == 1) return pair<char, char>('1', '0');
        if(sum == 2) return pair<char, char>('0', '1');
        if(sum == 3) return pair<char, char>('1', '1');
        return pair<char, char>('0', '0');
    }
};

1-2 乘法

题目3：43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

代码 (C++)

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.empty()) return num2;
        if(num2.empty()) return num1;
        int n = num1.size(), m = num2.size();
        if(n < m) return multiply(num2, num1); // 保证 m < n

        string result(m + n, '0');
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                pair<char, char> result_1x1 = _multiply_1x1(num1[i], num2[j]);
                char carry = result_1x1.second;
                pair<char, char> tmp1 = _add_1x1(result_1x1.first, result[i + j + 1], '0');
                result[i + j + 1] = tmp1.first;
                pair<char, char> tmp2 = _add_1x1(tmp1.second, result[i + j], carry);
                result[i + j] = tmp2.first;
                carry = tmp2.second;
                int k = i + j - 1;
                while(carry != '0')
                {
                    pair<char, char> tmp = _add_1x1('0', result[k], carry);
                    result[k] = tmp.first;
                    carry = tmp.second;
                    --k;
                }
            }
        int i;
        for(i = 0; i < m + n; ++i)
            if(result[i] != '0') break;

        if(i == m + n) return "0";
        else
            return result.substr(i, m + n - i);
    }

private:
    pair<char, char> _add_1x1(const char& a, const char& b, const char& carry)
    {
        int result = (a - '0') + (b - '0') + (carry - '0');
        if(result < 10) return pair<char, char>('0' + result, '0');
        else return pair<char, char>('0' + (result % 10), '0' + (result / 10));
    }

    pair<char, char> _multiply_1x1(const char& a, const char& b)
    {
        int result = (a - '0') * (b - '0');
        if(result < 10) return pair<char, char>('0' + result, '0');
        else return pair<char, char>('0' + (result % 10), '0' + (result / 10));
    }
};

$2 链表

2-1 加法

题目4：369. 给单链表加一

用一个非空单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照高位在链表头部、低位在链表尾部的顺序排列。

代码 (C++)

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        head = reverse(head);
        ListNode *iter = head;
        int carry = 1;
        ListNode *pretail = nullptr;
        while(iter != nullptr || carry > 0)
        {
            int d = carry;
            if(iter)
            {
                d += iter -> val;
                pretail = iter;
                iter -> val = d % 10;
                iter = iter -> next;
            }
            else
            {
                ListNode *tmp = new ListNode(d % 10);
                pretail -> next = tmp;
                pretail = tmp;
            }
            carry = d / 10;
        }
        return reverse(head);
    }

private:
    ListNode* reverse(ListNode* head)
    {
        if(!head) return head;
        ListNode *iter = head;
        ListNode *pretail = nullptr;
        while(iter)
        {
            ListNode *tmp = iter -> next;
            iter -> next = pretail;
            pretail = iter;
            iter = tmp;
        }
        return pretail;
    }
};

题目5：2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

代码 (C++)

表头是低位。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *tmp1 = l1;
        ListNode *tmp2 = l2;
        int carry = 0;
        ListNode *tmp = new ListNode((tmp1 -> val + tmp2 -> val) % 10);
        carry = (tmp1 -> val + tmp2 -> val) / 10;
        ListNode *result = tmp;
        while(tmp1 -> next != nullptr && tmp2 -> next != nullptr)
        {
            tmp1 = tmp1->next;
            tmp2 = tmp2->next;
            ListNode *tmp3 = new ListNode((tmp1 -> val + tmp2 -> val + carry) % 10);
            carry = (tmp1 -> val + tmp2 -> val + carry) / 10;
            tmp -> next = tmp3;
            tmp = tmp -> next;
        }
        if(tmp2 -> next == nullptr)
        {
            while(tmp1 -> next != nullptr)
            {
                tmp1 = tmp1 -> next;
                ListNode *tmp3 = new ListNode((tmp1->val + carry) % 10);
                carry = (tmp1 -> val + carry) / 10;
                tmp -> next = tmp3;
                tmp = tmp -> next;
            }
        }
        else
        {
            while(tmp2 -> next != nullptr)
            {
                tmp2 = tmp2 -> next;
                ListNode *tmp3 = new ListNode((tmp2 -> val + carry) % 10);
                carry = (tmp2 -> val + carry) / 10;
                tmp -> next = tmp3;
                tmp = tmp -> next;
            }
        }
        if(carry == 1)
        {
            tmp -> next = new ListNode(1);
        }
        return result;
    }
};

题目6：445. 两数相加 II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

代码 (C++)

表头是高位。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr || l1 -> val == 0) return l2;
        if(l2 == nullptr || l2 -> val == 0) return l1;
        // 两个链表均非空且大于 0
        ListNode *iter = l1;
        int count1 = 0;
        while(iter != nullptr)
        {
            ++count1;
            iter = iter -> next;
        }
        iter = l2;
        int count2 = 0;
        while(iter != nullptr)
        {
            ++count2;
            iter = iter -> next;
        }
        ListNode *l2_head = l2;
        ListNode *l1_head = l1;
        if(count1 > count2)
        {
            for(int i = 0; i < count1 - count2; ++i)
            {
                ListNode *tmp = new ListNode(0);
                tmp -> next = l2_head;
                l2_head = tmp;
            }
        }
        if(count1 < count2)
        {
            for(int i = 0; i < count2 - count1; ++i)
            {
                ListNode *tmp = new ListNode(0);
                tmp -> next = l1_head;
                l1_head = tmp;
            }
        }
        ListNode *dummy = new ListNode(0);
        int carry = 0;
        dummy -> next = _addTwoNumbers(l1_head, l2_head, carry);
        if(carry > 0)
        {
            ListNode *tmp = new ListNode(carry);
            tmp -> next = dummy -> next;
            dummy -> next = tmp;
        }
        return dummy -> next;
    }

private:
    ListNode* _addTwoNumbers(ListNode* l1, ListNode* l2, int &carry)
    {
        if(l1 == nullptr)
            return nullptr;

        ListNode *iter = _addTwoNumbers(l1 -> next, l2 -> next , carry);
        int sum = l1 -> val + l2 -> val + carry;
        carry = sum / 10;
        sum %= 10;
        ListNode *tmp = new ListNode(sum);
        tmp -> next = iter;
        iter = tmp;
        return iter;
    }
};

$3 数组

3-1 加法

题目7：66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

代码 (C++)

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        vector<int> result = digits;
        reverse(result.begin(), result.end());
        int sum = 1 + result[0];
        result[0] = sum % 10;
        int carry = sum / 10;
        for(int i = 1; i < n; ++i)
        {
            sum = result[i] + carry;
            result[i] = sum % 10;
            carry = sum / 10;
        }
        if(carry) result.push_back(1);
        reverse(result.begin(), result.end());
        return result;
    }
};

题目8：989. 数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

代码 (C++)

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        int carry = 0;
        reverse(A.begin(), A.end());
        vector<int> result;
        int n = A.size();
        int i = 0;
        while(i < n || K > 0 || carry > 0)
        {
            int d = carry;
            if(K > 0)
            {
                d += K % 10;
                K /= 10;
            }
            if(i < n)
            {
                d += A[i];
                ++i;
            }
            carry = d / 10;
            result.push_back(d % 10);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法算术

高精度运算组件

$1 字符串表示数

1-1 加法

题目1：415. 字符串相加

代码 (C++)

题目2：67. 二进制求和

代码 (C++)

1-2 乘法

题目3：43. 字符串相乘

代码 (C++)

$2 链表

2-1 加法

题目4：369. 给单链表加一

代码 (C++)

题目5：2. 两数相加

代码 (C++)

题目6：445. 两数相加 II

代码 (C++)

$3 数组

3-1 加法

题目7：66. 加一

代码 (C++)

题目8：989. 数组形式的整数加法

代码 (C++)