题目描述

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

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

解题思路与代码

  • 这道题属实是一道中等难度的题。需要你有一定的思考量,才可以做出来。

  • 题目的要求是,不允许我们使用位运算符,除了 + 法以外的算术运算符,去实现两个数之间的减法,乘法,除法函数。

  • 也就是说,我们可以使用 + 法运算符,关系运算符(==, <= , >=, < , >)还有逻辑运算符 ( ! , && , ||)去实现这些函数。

  • 这道题建议大家不要抖机灵,使用各种没有意义的库函数来简便运算。还有这道题也不要去使用vector这种数据结构。因为,vector的模板类在实现时涉及到位运算符和减法运算符的

接下来,其实我们就要思考一个问题。乘法,除法的本质是什么?

  • 那其实是不是就是加法(乘法的本质是加法)与减法(除法的本质是减法)呢?
  • 那也就是说,要实现除法函数,首先得实现减法函数。

那我们,在来思考一个问题,减法的本质是什么?

  • 那是不是加上一个相反数呢?
  • 所以要实现减法函数,首先我们还需要去实现一个取反函数。

其实这道题还有一个隐藏的条件,那就是提示:单个用例的函数调用次数不会超过1000次

  • 也就是说,这道题,出题人不想你太容易去解决这个问题。问你如何优化流程,也就是缩短时间复杂度。
  • 假如说我们要用累加去实现取反过程,你想想时间复杂度是不是O(n),那有没有一种办法可以优化累加的时间复杂度呢?
  • 当然有。我们可以通过事先创建两个数组,分别去存储正负2的多少次方的值是多少。到时候,我们可以用循环的方式,去累加预定值,这样是不是就将时间复杂度O(n)缩短到O(logn)了呢?

OK,这道题讲到这里,大家应该心里很有谱了才对。做这道题,首先,我们要创建两个内置数组,去存储可能出现的2的次方值。然后先实现取反函数。再实现减法函数,再实现乘法函数,最后实现除法函数。

实现的过程中,需要大家注意溢出问题。因为虽然题目给的值的范围不会超过int的最大最小范围。但是两个数相减,相乘,相除的过程中,如果处理不好,是会发生溢出问题的。

具体的实现请看代码:

class Operations {
    int posN[31]; // 放正数2的n次方
    int negN[31]; // 放负数2的n次方
    //取相反数函数
    int oppN(int num){
        if(!num) return 0;
        int res = 0;
        if(num > 0){ // 从2^30次方开始检查
            for(int i = 30; i >= 0; i += (-1)){
                if(num + negN[i] < 0) continue;
                num += negN[i];
                res += negN[i];
            }
        }else{ // 从 - 2^30次方开始检查
            for(int i = 30; i >= 0; i += (-1)){
                if(num + posN[i] > 0) continue;
                num += posN[i];
                res += posN[i];
            }
        }
        return res;
    }
public:
    Operations() {
        int p = 1;
        int n = -1;
        posN[0] = p;
        negN[0] = n;
        // 初始化次方数组
        for(int i = 1; i < 31; ++i){
            p += p;
            posN[i] = p;
            n += n;
            negN[i] = n;
        }
    }

    
    int minus(int a, int b) {
        return a + oppN(b);
    }
    
    int multiply(int a, int b) {
        if(!a || !b) return 0;
        if(a == 1) return b;
        if(b == 1) return a;
        if(b < 0) return oppN(multiply(a,oppN(b))); // 统一b的正负
        int res = a;
        int count = 1;
        while(count < posN[30] && count + count <= b ){
            res += res;
            count += count;
        }
        res += multiply(a,minus(b,count));
        return res;
    }


    
    int divide(int a, int b) {
        if(!a) return 0;
        int res = 1;
        if(a > 0){
            if(b == INT_MIN) return 0;
            if(b < 0) return oppN(divide(a,oppN(b))); // 统一a,b的正负
            if(a < b) return 0;
            int count = b;
            while(count < posN[30] && a >= count + count){
                res += res;
                count += count;
            }
            res += divide(minus(a,count),b);
        }else{
            if(b == 1) return a;
            if(b > 0) return oppN(divide(a,oppN(b)));
            if(a > b) return 0;
            int count = b;
            while(count >= negN[30] && a <= count + count){
                res += res;
                count += count;
            }
            res += divide(minus(a,count),b);
        }
        return res;
    }    
};

《程序员面试金典(第6版)面试题 16.09. 运算-LMLPHP

复杂度分析

  • oppN(int num):时间复杂度为 O(log(num)),因为它在最坏情况下需要遍历数组 posN 或 negN 中的所有元素(共 31 个),这与输入数字的二进制表示长度成正比。空间复杂度为 O(1),因为它使用了固定数量的额外存储空间。

  • Operations() 构造函数:时间复杂度为 O(1),因为它只需要遍历 31 个元素并执行一定数量的操作。空间复杂度为 O(1),因为它只使用了固定大小的 posN 和 negN 数组。

  • minus(int a, int b):时间复杂度为 O(log(b)),因为它调用了 oppN 函数。空间复杂度为 O(1),因为它没有使用额外的存储空间。

  • multiply(int a, int b):时间复杂度为 O(log(a) * log(b)),因为它使用递归实现,每次递归调用都会减小 b 的值,递归深度为 O(log(b)),而每次递归调用都会调用 minus 函数,时间复杂度为 O(log(a))。空间复杂度为 O(log(b)),因为递归深度与空间复杂度成正比。

  • divide(int a, int b):时间复杂度为 O(log(a) * log(b)),因为它也是使用递归实现,每次递归调用都会减小 a 的值,递归深度为 O(log(a)),而每次递归调用都会调用 minus 函数,时间复杂度为 O(log(b))。空间复杂度为 O(log(a)),因为递归深度与空间复杂度成正比。

总的来说,这个实现的时间复杂度主要取决于输入数字的二进制表示长度,而空间复杂度主要取决于递归深度。

总结

  • 这道题的意义在于考察编程能力、逻辑思维和对基本运算的理解。

  • 它要求我们在限制条件下(仅使用加法运算符和逻辑运算符)实现整数数字的减法、乘法和除法运算。这种问题有助于锻炼思考能力,强化对计算机基本原理的理解,以及提高解决问题的灵活性。

  • 同时,这种问题也有助于理解计算机是如何处理基本的算术运算的,以及为什么某些优化方法(例如位运算)是有效的。通过解决这种问题,你可以加深对计算机科学和编程原理的理解。

  • 最后的最后,如果你觉得我的这篇文章写的不错的话,请给我一个赞与收藏,关注我,我会继续给大家带来更多更优质的干货内容

05-02 17:14