leetcode29.两数相除

Posted on | In |
Words count in article: 561 | Reading time ≈ 2

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

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

示例：

1
2
3
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

分析：

1
2
3
4
5
6
7
8
9
10
定义商为n,则n可以通过x与y的减法得到
while (x) {
	x -= y;
	n ++;
}
由于数据范围的影响，-2^31 <= dividend, divisor <= 2^31 - 1，最坏情况下需要2^31 - 1减法操作会超时
因此，需要优化
x 可以表示为x = 2 ^ 0 * y + 2 ^ 1 * y + …… + 2 ^ 31 - 1 * y;
因此只需要考虑每一位是否需要，常数时间复杂度
为了方便起见，可以从大到小考虑

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;
        vector<LL> exp;//指数项
        bool is_minus = false;//负号
        if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;//异号相除的结果为负
        //预处理2*b^i
        LL a = abs((LL)x), b = abs((LL)y);//先直接用正数算，到时候结果加上负号就可以
        for (LL i = b; i <= a; i = i + i) exp.push_back(i);//i从除数开始，只要i还小于被除数a，就倍增i，然后将指数项插入到exp数组里

        LL res = 0;//存答案
        for (int i = exp.size() - 1; i >= 0; i -- )//从大到小开始减
            if (a >= exp[i]) {//还可以做减法
                a -= exp[i];//减去对应的数
                res += 1ll << i;//左移一位，相当于乘以2，因为是基于倍增的思想，所以能减多少次，就左移多少次即可得到结果
            }

        if (is_minus) res = -res;//负号的话就直接取反

        if (res > INT_MAX || res < INT_MIN) res = INT_MAX;//处理溢出的情况

        return res;
    }
};

[原题链接](29. 两数相除 - 力扣（Leetcode）)

0%