面试题 16.09. 运算
请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。
你的实现应该支持如下操作：
Operations() 构造函数minus(a, b) 减法，返回a - bmultiply(a, b) 乘法，返回a * bdivide(a, b) 除法，返回a / b示例：
Operations operations = new Operations(); operations.minus(1, 2); //返回-1 operations.multiply(3, 4); //返回12 operations.divide(5, -2); //返回-2
提示：
原站题解
python3 解法, 执行用时: 128 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-29 16:31:07
class Operations:
def __init__(self):
self.negs = [-1]
self.pos = [1]
for i in range(31):
self.negs.append(self.negs[-1] + self.negs[-1])
self.pos.append(self.pos[-1] + self.pos[-1])
def negative(self, n):
if n == 0: return 0
res = 0
bits = self.negs if n > 0 else self.pos
neg = n < 0
for i in range(31, -1, -1):
if (n + bits[i] < 0 and not neg) or (n + bits[i] > 0 and neg): continue
n += bits[i]
res += bits[i]
return res
def minus(self, a: int, b: int) -> int:
return a + self.negative(b)
def multiply(self, a: int, b: int) -> int:
if a == 0 or b == 0: return 0
if b == 1: return a
if b < 0: return self.negative(self.multiply(a, self.negative(b)))
bits = self.pos
res = a
time = 1
while time + time <= b:
res += res
time += time
res += self.multiply(a, self.minus(b, time))
return res
def divide(self, a: int, b: int) -> int:
if a == 0: return 0
if b == 1: return a
neg = (a ^ b) < 0
if a < 0: a = self.negative(a)
if b < 0: b = self.negative(b)
if a < b: return 0
time = 1
res = b
while res + res <= a:
res += res
time += time
time += self.divide(self.minus(a, res), b)
return self.negative(time) if neg else time
# Your Operations object will be instantiated and called as such:
# obj = Operations()
# param_1 = obj.minus(a,b)
# param_2 = obj.multiply(a,b)
# param_3 = obj.divide(a,b)
golang 解法, 执行用时: 12 ms, 内存消耗: 6.4 MB, 提交时间: 2022-11-29 16:30:18
import "math"
type Operations struct {
negatives, positives [31]int
}
func Constructor() Operations {
negatives, positives := [31]int{}, [31]int{}
neg, pos := -1, 1
for i := 0; i < 31; i++ {
negatives[i] = neg
neg += neg
positives[i] = pos
pos += pos
}
return Operations{negatives, positives}
}
// 取相反数
func (this *Operations) opposite(a int) int {
if a == 0 {
return 0
}
result := 0
if a > 0 {
for i := 30; i >= 0; i-- {
if a+this.negatives[i] < 0 {
continue
}
a += this.negatives[i]
result += this.negatives[i]
}
} else {
for i := 30; i >= 0; i-- {
if a+this.positives[i] > 0 {
continue
}
a += this.positives[i]
result += this.positives[i]
}
}
return result
}
func (this *Operations) Minus(a int, b int) int {
return a + this.opposite(b)
}
func (this *Operations) Multiply(a int, b int) int {
if a == 0 || b == 0 {
return 0
}
if a < 0 {
a, b = this.opposite(a), this.opposite(b)
}
result, times := b, 1
// 防止溢出
for times+times > 0 && times+times < a {
result += result
times += times
}
return result + this.Multiply(this.Minus(a, times), b)
}
func (this *Operations) Divide(a int, b int) int {
if a == 0 {
return 0
}
if a == b {
return 1
}
if b == 1 {
return a
}
if b == -1 {
return this.opposite(a)
}
// 只处理同号的情况，异号时转化为同号处理
if a > 0 {
if b == math.MinInt32 {
return 0
}
if b < 0 {
return this.opposite(this.Divide(a, this.opposite(b)))
}
if a < b {
return 0
}
result, sum := 1, b
for sum+sum > 0 && sum+sum < a {
result += result
sum += sum
}
return result + this.Divide(this.Minus(a, sum), b)
} else {
if b > 0 {
return this.opposite(this.Divide(a, this.opposite(b)))
}
if b < a {
return 0
}
result, sum := 1, b
for sum+sum < 0 && sum+sum > a {
result += result
sum += sum
}
return result + this.Divide(this.Minus(a, sum), b)
}
}
/**
* Your Operations object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Minus(a,b);
* param_2 := obj.Multiply(a,b);
* param_3 := obj.Divide(a,b);
*/
java 解法, 执行用时: 15 ms, 内存消耗: 41.6 MB, 提交时间: 2022-11-29 16:27:47
class Operations {
// 用来获取-1
int ne = Integer.MAX_VALUE + Integer.MAX_VALUE + 1;
long[] neCache = new long[32];// 放置 -1,-2,-4,-8...
long[] poCache = new long[32];// 放置 1,2,4,8...
long[] cache = new long[32];// 存放乘数或除数的倍数，1*a,2*a,4*a,8*a...主要用于快速计算，不然容易超时
long[] cache1 = new long[32];// 存放乘数或除数的倍数 负数-1*a,-2*a,-4*a,-8*a
public Operations() {
neCache[0] = ne;
poCache[0] = 1;
for (int i = 1; i < 32; ++i) {
neCache[i] = neCache[i + ne] + neCache[i + ne];
poCache[i] = poCache[i + ne] + poCache[i + ne];
}
}
public int minus(int a, int b) {
if (a == b) return 0;
int index = 31;// 从最大值开始比较
while (b != 0) {
if (b > 0) {
if (b >= poCache[index]) { // 如果b大于2的index次方，
b += neCache[index];// a与b同时减
a += neCache[index];
} else {
index += ne;
}
} else { // b小于0时同理
if (b <= neCache[index]) {
b += poCache[index];
a += poCache[index];
} else {
index += ne;
}
}
}
return a;
}
public int multiply(int a, int b) {
if (a == 0 || b == 0) return 0;
if (a == 1) return b;
if (b == 1) return a;
if (a == ne) return minus(0, b);
if (b == ne) return minus(0, a);
int sign = (a > 0 && b > 0) || (a < 0 && b < 0) ? 1 : ne;
// 把b变成正数
if (b < 0) {
b = minus(0, b);
}
cache[0] = a;
for (int i = 1; i < 32; i++) {
cache[i] = cache[i + ne] + cache[i + ne];
}
int index = 30; // 从31开始应该也是可以的
int ret = 0;
int retSign = a > 0 ? 1 : ne; // 记录返回值的符号
while (b > 0) {
if (b >= poCache[index]) {
b += neCache[index];
ret += cache[index];
retSign = ret > 0 ? 1 : ne;// 记录返回值的符号
} else {
index += ne;
}
}
// 根据初始值改变返回值的符号
if ((sign < 0 && ret > 0) || (sign > 0 && ret < 0)) {
ret = minus(0, ret);
}
// 结果溢出，返回值的符号会变成相反的
if (retSign != (a > 0 ? 1 : ne)) {
ret = minus(0, ret);
}
return ret;
}
public int divide(int a, int b) {
if (a == 0) return 0;
if (b == 1) return a;
if (b == ne) return minus(0, a);
int ret = 0;
int sign = (a > 0 && b > 0) || (a < 0 && b < 0) ? 1 : ne;
long nb = b;
long pb = b;
if (b < 0) {
b = minus(0, b);
} else {
nb = minus(0, b);
}
if (a < 0) {
a = minus(0, a);
}
cache[0] = b;
cache1[0] = nb;
int index = 1;
for (; index < 32; ++index) {
cache[index] = cache[index + ne] + cache[index + ne];
cache1[index] = cache1[index + ne] + cache1[index + ne];
if (cache1[index] >= a) {
break; // 找到最大值就可以返回了，不用计算完
}
}
if (index >= 32) index = 31;
while (a >= b) {
if (a >= cache[index]) {
ret += poCache[index];// 注意这里是2的index次方的值
a += cache1[index];
} else {
index += ne;
}
}
if (sign < 0) {
ret = minus(0, ret);
}
return ret;
}
}
/**
* Your Operations object will be instantiated and called as such:
* Operations obj = new Operations();
* int param_1 = obj.minus(a,b);
* int param_2 = obj.multiply(a,b);
* int param_3 = obj.divide(a,b);
*/