程序员面试金典面试题16。09。运算

　　题目难度: 中等
　　原题链接  [1]
　　今天继续更新程序员面试金典系列, 大家在公众号   算法精选   里回复  面试金典   就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
　　请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。
　　你的实现应该支持如下操作： Operations() 构造函数 minus(a, b) 减法，返回 a - b multiply(a, b) 乘法，返回 a * b pide(a, b) 除法，返回 a / b 示例：Operations operations = new Operations(); operations.minus(1, 2); //返回-1 operations.multiply(3, 4); //返回 12 operations.pide(5, -2); //返回-2 提示：你可以假设函数输入一定是有效的，例如不会出现除法分母为 0 的情况 单个用例的函数调用次数不会超过 1000 次 题目思考可以从哪个运算入手? 是否可以利用已经实现的操作? 解决方案思路这道题目乍一看无从下手, 如何做到只使用加法和逻辑运算符来实现减/乘/除呢? 首先来看减法, 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 pide(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         # 因子分解实现除法         # 例如pide(123,10), 123/10=12=8+4         # 外层循环2次, 对应的cur和t分别是(8, 10*8), (4, 10*4), 累加cur即为最终的商         res = 0         # 注意循环条件是a>=b, 因为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/