题目难度: 中等

原题链接[1]

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。

你的实现应该支持如下操作：

• Operations() 构造函数
• minus(a, b) 减法，返回 a - b
• multiply(a, b) 乘法，返回 a * b
• divide(a, b) 除法，返回 a / b

示例：

• Operations operations = new Operations();
• operations.minus(1, 2); //返回-1
• operations.multiply(3, 4); //返回 12
• operations.divide(5, -2); //返回-2

提示：

• 你可以假设函数输入一定是有效的，例如不会出现除法分母为 0 的情况
• 单个用例的函数调用次数不会超过 1000 次

题目思考

1. 可以从哪个运算入手?
2. 是否可以利用已经实现的操作?

解决方案

思路

• 这道题目乍一看无从下手, 如何做到只使用加法和逻辑运算符来实现减/乘/除呢?
• 首先来看减法, a-b 相当于 a+(-b), 如果我们能够实现取反操作, 则直接就能实现减法
• 要实现取反, 我们可以利用数字的二进制性质, 维护每一个 2 的幂和 -2 的幂, 然后如果当前数字的某一个二进制位为 1 的话, 直接加上与之对应的相反数即可, 具体过程可以参考下面代码
• 然后再说乘法, 我们可以利用因数分解来实现, 例如 123*15=123*(8+4+2+1), 我们可以维护当前的因子和乘积, 每次循环到因子最接近当前被乘数为止, 然后累加乘积并将被乘数减去因子, 继续循环直到被乘数变为 0
• 最后再看除法, 同样可以利用因数分解来实现, 例如 123/10=12=8+4, 维护当前的商和乘积, 每次循环到乘积最接近当前被除数为止, 然后累加商并将被除数减去乘积, 继续循环直到被除数小于除数
• 另外乘除法也要处理操作数的符号问题, 可以将操作数统一转成正数方便处理, 这里利用上面定义好的取反操作即可
• 下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(logN): 减/乘/除都需要遍历 32 位
• 空间复杂度 O(logN): 需要存储 2*32 个 2 的幂

代码

class Operations:
    def __init__(self):
        # ps存储[1,2,4,...], 即2的幂
        # ns存储[-1,-2,-4,...], 即-2的幂
        # 利用这两个数组来实现取反操作
        self.ps = []
        self.ns = []
        self.n = 32
        p, n = 1, -1
        for i in range(self.n):
            self.ps.append(p)
            self.ns.append(n)
            if i < 31:
                p = self.lShift(p)
                n = self.lShift(n)

    def neg(self, x: int) -> int:
        res = 0
        if x > 0:
            # x是正数, 从大到小遍历2的幂, 如果当前数字大于等于该幂时, 将该数字和最终结果都加上对应的相反数
            # 例如x=15=8+4+2+1, 其相反数-15=(-8)+(-4)+(-2)+(-1)
            for i in range(self.n)[::-1]:
                if x >= self.ps[i]:
                    res += self.ns[i]
                    x += self.ns[i]
                if x == 0:
                    # x已经达到0, 没有必要继续遍历, 直接break
                    break
        elif x < 0:
            # 类似上面的过程, 只是改变判断符号
            for i in range(self.n)[::-1]:
                if x <= self.ns[i]:
                    res += self.ps[i]
                    x += self.ps[i]
                if x == 0:
                    break
        return res

    def lShift(self, x: int) -> int:
        # 左移操作等价于x+x
        return x + x

    def minus(self, a: int, b: int) -> int:
        # a-b即为a+(-b), 直接利用上面定义的取反操作即可
        return a + self.neg(b)

    def multiply(self, a: int, b: int) -> int:
        if a == 0 or b == 0:
            # 乘数为0, 积也为0
            return 0
        if b < 0:
            # 将b取反转成正数, 方便处理, 注意最终结果也要取反
            return self.neg(self.multiply(a, self.neg(b)))
        # 因子分解实现乘法
        # 例如multiply(123,15), 123*15=123*(8+4+2+1)
        # 外层循环4次, 对应的cur和t分别是(123*8, 8), (123*4, 4), (123*2, 2), (123*1, 1), 累加cur即为最终乘积
        res = 0
        # 注意循环条件是b!=0, 因为最终因子一定能分解成多个2的幂的和, b一定能变成0
        while b:
            # cur表示当前部分的乘积
            cur = a
            # t表示当前不超过b的因子
            t = 1
            while self.lShift(t) <= b:
                cur = self.lShift(cur)
                t = self.lShift(t)
            # 更新最终乘积和b
            res += cur
            b = self.minus(b, t)
        return res

    def divide(self, a: int, b: int) -> int:
        if a == 0:
            # 被除数为0, 商也为0
            return 0
        # 将除数和被除数都转成正数, 并加上对应符号, 方便处理
        pos = True
        if a < 0:
            a = self.neg(a)
            pos = not pos
        if b < 0:
            b = self.neg(b)
            pos = not pos
        # 因子分解实现除法
        # 例如divide(123,10), 123/10=12=8+4
        # 外层循环2次, 对应的cur和t分别是(8, 10*8), (4, 10*4), 累加cur即为最终的商
        res = 0
        # 注意循环条件是a>=b, 因为a<b的时候对应的商是0
        while a >= b:
            # cur表示当前部分的商
            cur = 1
            # t表示当前不超过a的乘积
            t = b
            while self.lShift(t) <= a:
                cur = self.lShift(cur)
                t = self.lShift(t)
            # 更新最终商和a
            res += cur
            a = self.minus(a, t)
        if not pos:
            res = self.neg(res)
        return res

参考资料

[1]

原题链接: https://leetcode-cn.com/problems/operations-lcci/