数学题：加减乘除

0029. 两数相除 (opens new window)

题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

解析

用加法替代除法的整体思路是记录除数需要累加多少次才能达到被除数。

其中加法过程可以使用快速幂的思想进行优化，可以参考 算法模板：快速幂 的解析。

注意

• 符号：使用单独的变量记录结果的正负。
• 越界：将数字转换为负数后再计算，因为负数表示的范围更大。

代码

class Solution {
public:
    int divide(int x, int y) {
        bool sign = (x > 0 && y < 0) || (x < 0 && y > 0);
        if (x > 0) x = -x;
        if (y > 0) y = -y;

        vector<pair<int, int>> exp;
        for (int i = y, j = -1; i >= x; i += i, j += j) {
            exp.push_back({i, j});
            if (i < INT_MIN / 2) break;
        }

        int ans = 0;
        for (int i = exp.size() - 1; i >= 0; i--) {
            if (exp[i].first >= x) {
                ans += exp[i].second;
                x -= exp[i].first;
            }
        }

        if (sign) return ans;
        if (ans == INT_MIN) return INT_MAX;
        return -ans;
    }
};

0043. 字符串相乘 (opens new window)

题目

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

解析

整个计算过程为：两个指针 i，j 在 num1 和 num2 上游走，计算乘积，同时将乘积叠加到数组的正确位置。

通过观察可知，num1[i] 和 num2[j] 的乘积对应的就是 v[i + j] 这个位置（下标为逆序），这样就可以模拟出整个乘法的过程。

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.length(), m = num2.length();
        vector<int> v(n + m);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int a = num1[n - i - 1] - '0';
                int b = num2[m - j - 1] - '0';
                v[i + j] += a * b;
            }
        }
        for (int i = 0, carry = 0; i < v.size(); i++) {
            v[i] += carry;
            carry = v[i] / 10;
            v[i] %= 10;
        }

        string ans;
        for (int i = v.size() - 1; i >= 0; i--) {
            if (ans.empty() && v[i] == 0) continue;
            ans += v[i] + '0';
        }
        return ans.empty() ? "0" : ans;
    }
};

0066. 加一 (opens new window)

题目

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

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

解析

从后向前遍历数字，根据每一位和 9 的大小关系，确定是加一还是置零。

代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                break;
            } else {
                digits[i] = 0;
                if (i == 0) {
                    digits.insert(digits.begin(), 1);
                }
            }
        }
        return digits;
    }
};

0067. 二进制求和 (opens new window)

题目

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

解析

二进制下列竖式计算，从后向前遍历两个字符串，使用 carry 保存进位情况，按位相加即可。

代码

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans = to_string(carry % 2) + ans;
            carry /= 2;
        }
        return ans;
    }
};

0258. 各位相加 (opens new window)

题目

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

解析

按位相加，当结果为 1 位数时直接返回，否则递归进行下一轮求和。

代码

class Solution {
public:
    int addDigits(int num) {
        int sum = 0;
        while (num) {
            sum += num % 10;
            num /= 10;
        }
        return sum > 9 ? addDigits(sum) : sum;
    }
};

0415. 字符串相加 (opens new window)

题目

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

解析

本题与 0067. 二进制求和 解法完全一致，可作为模板记忆。

代码

class Solution {
public:
    string addStrings(string num1, string num2) {
        string ans = "";
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int n1 = i >= 0 ? num1[i--] - '0' : 0;
            int n2 = j >= 0 ? num2[j--] - '0' : 0;
            int sum = n1 + n2 + carry;
            ans += sum % 10 + '0';
            carry = sum / 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};