【LeetCode】数学精选4题

目录

1. 二进制求和（简单）

2. 两数相加（中等）

3. 两数相除（中等）

4. 字符串相乘（中等）

1. 二进制求和（简单）

从字符串的右端出发向左做加法，逢二进一。

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        int i = a.size() - 1; // a的下标是从0到i
        int j = b.size() - 1; // b的下标是从0到j
        int carry = 0 ; // 进位
        while (i >= 0 || j >= 0)
        {
            int digitA = i >= 0 ? a[i--] - '0' : 0;
            int digitB = j >= 0 ? b[j--] - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            ans += sum + '0';
        }
        if (carry)
        {
            ans += '1';
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

2. 两数相加（中等）

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode; // 哨兵节点
        ListNode* tail = preHead;
        int carry = 0; // 进位
        while (l1 || l2)
        {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            tail->next = new ListNode(sum % 10);
            carry = sum / 10;
            tail = tail->next;
            if (l1)
            {
                l1 = l1->next;
            }
            if (l2)
            {
                l2 = l2->next;
            }
        }
        if (carry)
        {
            tail->next = new ListNode(carry);
        }
        return preHead->next;
    }
};

3. 两数相除（中等）

假设被除数是a，除数是b。

如果a、b都是正数，且a>=b

a最多大于b的2^k倍，将a减去b的2^k倍，剩下的被除数再重复这样的操作，直到a < b

以22除以3为例：

22最多大于3的4倍：22 - 3 * 4 = 10

10最多大于3的2倍：10 - 3 * 2 = 4

4最多大于3的1倍： 4 - 3 * 1 = 1

商是4 + 2 + 1 = 7，余数是1

如果a、b都是负数，且a <= b

a最多小于b的2^k倍，将a减去b的2^k倍，剩下的被除数再重复这样的操作，直到a > b

以-22除以-3为例：

-22最多小于-3的4倍：-22 - (-3) * 4 = -10

-10最多小于-3的2倍：-10 - (-3) * 2 = -4

-4最多小于-3的1倍： -4 - (-3) * 1 = -1

商是4 + 2 + 1 = 7，余数是-1

class Solution {
public:
    int divide(int dividend, int divisor) {
        // -2^31/-1=2^31 溢出
        if (dividend == INT_MIN)
        {
            if (divisor == -1)
            {
                return INT_MAX;
            }
            else if (divisor == 1)
            {
                return INT_MIN;
            }
        }
        // 全部转化为负数，如果全部转化为正数，-2^31转化为正数会溢出
        int negative = 2; // 表示被除数和除数有几个是负数
        if (dividend > 0)
        {
            dividend = -dividend;
            negative--;
        }
        if (divisor > 0)
        {
            divisor = -divisor;
            negative--;
        }

        int result = divideCore(dividend, divisor);
        return negative == 1 ? -result : result;
    }

private:
    int divideCore(int a, int b)
    {
        int result = 0;
        while (a <= b)
        {
            int k = 1;
            int val = b; // val表示b的2^k倍
            while (val >= INT_MIN / 2 && a <= val + val)
            {
                k += k;
                val += val;
            }
            result += k;
            a -= val;
        }
        return result;
    }
};

4. 字符串相乘（中等）

无进位相乘后相加，再处理进位。

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
            
        int n1 = num1.size();
        int n2 = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> sums(n1 + n2 -1);
        // 无进位相乘后相加
        for (int i = 0; i < n2; i++)
        {
            for (int j = 0; j < n1; j++)
            {
                sums[i + j] += (num2[i] - '0') * (num1[j] - '0');
            }
        }
        // 处理进位
        string ans;
        int i = 0;
        int carry = 0;
        while (i < n1 + n2 -1)
        {
            int sum = sums[i++] + carry;
            ans += sum % 10 + '0';
            carry = sum / 10;
        }
        if (carry)
        {
            ans += carry + '0';
        }
        // 反转
        reverse(ans.begin(), ans.end());
        return ans;
    }
};