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

英文原文

Write methods to implement the multiply, subtract, and divide operations for integers. The results of all of these are integers. Use only the add operator.

You should implement following methods:

• Operations()  constructor
• minus(a, b)  Subtraction, returns a - b
• multiply(a, b)  Multiplication, returns a * b
• divide(a, b)  Division, returns a / b

Example:

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

Note:

• You can assume inputs are always valid, that is, e.g., denominator will not be 0 in division.
• The number of calls will not exceed 1000.

中文题目

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

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

• 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次

通过代码

高赞题解

这道题实在是任务量太大了，中间好几度想要放弃。其实只是量大而已，就把它当成三道题来做，按部就班一个一个运算来写，总是能写出来的👍🏻

基本思路

其实最难的是取反运算，这里参考了@sskbskdrin大神的java代码。
有了取反运算以后，减法自然就实现了。乘除法主要是二分的思想（快速乘），再加上一些边界测试用例防止溢出的语句。

给想要真正不抖机灵写下来这道题的同学们一点步骤的建议：

1. 实现取反，测试通过减法
2. 实现快速乘除，测试通过乘除法
3. 根据测试用例，添加防溢出判断

这样把一个庞大的任务分解成几个步骤来实现，就不会那么想要放弃了👍🏻

代码

class Operations {
private:
    vector<int> negs, poss; // 存的是[-1, -2, -4...]、[1, 2, 4...]，取反和判断溢出时用
    
    int neg(int a) {
        if(!a) return 0;
        
        int result = 0;
        
        if(a > 0) {
            // 从绝对值最大的部分开始填充
            for(auto p = negs.rbegin(); p != negs.rend(); p++) {   
                if(*p + a < 0) continue;
                
                a += *p;
                result += *p;
            }
        } else {
            for(auto p = poss.rbegin(); p != poss.rend(); p++) {
                if(*p + a > 0) continue;
                
                a += *p;
                result += *p;
            }
        }
        return result;
    }
public:
    Operations() {
        // 构造poss和negs
        int p = 1, n = -1;
        poss.push_back(p);
        negs.push_back(n);
        
        for(int i = 0; i < 30; i++) {
            p += p;
            n += n;
            
            poss.push_back(p);
            negs.push_back(n);
        }
    }
    
    int minus(int a, int b) {
        return a + neg(b);
    }
    
    int multiply(int a, int b) {
        if(!a || !b) return 0;
        if(a == 1) return b;        // 这一步是针对b = INT_MIN的情况，防止下一步取neg时溢出
        if(b < 0) return neg(multiply(a, neg(b))); 
        
        int result = a;
        int times = 1;              // times表示当前结果里已经累加了几个a了
        
        // times < poss[30]是为了防止溢出
        while(times < poss[30] && times + times <= b) {   
            result += result;
            times += times;
        }
        result += multiply(a, minus(b, times));
        
        return result;
    }
    
    int divide(int a, int b) {
        if(!a) return 0;
        
        int result = 1;
        // 只写同号的情况，非同号时用neg转化成同号，但是要注意溢出
        if(a > 0) {
            if(b == INT_MIN) return 0;          // 防止下一句取neg的时候溢出
            if(b < 0) return neg(divide(a, neg(b)));
            if(a < b) return 0;
            
            int acc = b;                        // 不断往acc里填充b，直到acc达到a
            while(acc < poss[30] && a >= acc + acc) {
                result += result;               // result表示已经填充了几个b了
                acc += acc;
            }
            result += divide(minus(a, acc), b);
        } else {
            if(b == 1) return a;                // 防止若a=INT_MIN造成下一句运算时溢出
            if(b > 0) return neg(divide(a, neg(b)));
            if(a > b) return 0;
            
            int acc = b;
            while(acc >= negs[30] && a <= acc + acc) {
                result += result;
                acc += acc;
            }
            result += divide(minus(a, acc), b);
        }
        return result;
    }
};

/**
 * 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);
 */

统计信息

通过次数	提交次数	AC比率
2318	4227	54.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言