运算
运算

运算

Date
Sep 1, 2023
Created
Oct 15, 2023 04:37 PM
Tags
LeetCode
Algorithm
Java

基本思路

由于程序中只允许出现加法运算符,而减法、除法或乘法运算中都可能出现取反操作,故首先应当实现数的取反功能。
设取反函数的输入值为 。只利用加法实现取反,最简单的解法就是一直对 ) 或 )直至 ,此时有 。该过程可以利用倍增法进行加速,即从 开始,每次与 相加的数增大一倍, 异号(回退一个操作,继续从 开始加起)或 (结束运算)。
在实现取反函数后,减法运算便可以很方便地实现。
考虑乘法运算:对于 ,实际上就是 相加,故可以同样利用倍增法进行加速。
考虑除法运算:对于 ,实际上是计算 最多能被 减多少次,同样可用倍增法进行加速。

代码

Java
class Operations { public Operations() { } public int minus(int a, int b) { return a + negate(b); } public int multiply(int a, int b) { int mul = 0; int initialDelta = b > 0 ? -1 : 1; int initialMultiplyDelta = b < 0 ? negate(a) : a; int multiplyDelta = initialMultiplyDelta, delta = initialDelta; while (b != 0) { if (isOverflow(b, b + delta)) { delta = initialDelta; multiplyDelta = initialMultiplyDelta; } b += delta; mul += multiplyDelta; delta += delta; multiplyDelta += multiplyDelta; } return mul; } public int divide(int a, int b) { int div = 0; int initialDelta = a > 0 == b > 0 ? 1 : -1; int initialDivideDelta = a > 0 == b > 0 ? negate(b) : b; int delta = initialDelta, divideDelta = initialDivideDelta; while (a != 0) { if (isOverflow(divideDelta, initialDivideDelta) || isOverflow(a, a + divideDelta)) { if (isOverflow(a, a + initialDivideDelta)) { break; } delta = initialDelta; divideDelta = initialDivideDelta; } div += delta; a += divideDelta; delta += delta; divideDelta += divideDelta; } return div; } private int negate(int x) { int negation = 0; int initialDelta = x > 0 ? 1 : -1; int delta = initialDelta; while (x != 0) { if (isOverflow(x, x + delta)) { delta = initialDelta; } x += delta; negation += delta; delta += delta; } return negation; } private boolean isOverflow(int source, int target) { return target != 0 && target > 0 != source > 0; } }

复杂度分析

  • 空间复杂度:Operations 构造函数的时间复杂度为 minus 函数的时间复杂度为 multiply 函数的时间复杂度为 divide 函数的时间复杂度为
  • 时间复杂度:,只需要常数级的变量空间。

进一步优化

对于给定的  范围,此处倍增过程的所有值实际上可以实现利用数组提前保存下来,并从大值向小值方向进行匹配,将时间复杂度优化到 ,其中  为给定整数的最大范围。