运算(Leetcode 程序员面试金典16.09)

发表于 | 分类于 ， ， | | 本文总阅读数 次
| 字数统计: 2.2k | 阅读时长 ≈ 9
Leetcode 程序员面试金典16.09

1

题目分析

   最头痛的题目来了，实现减法，乘法，除法操作，其中不能使用位运算操作。这个题目简直是折磨，但是也挺锻炼人对于计算机数据存储的知识。

数学

这个问题太复杂了，我们先要实现取负数运算，因为减去一个数相当于加上这个数的相反数。这不仅在减法中用得到，在乘除法也可以用到，乘除一个负数等于乘这个数的相反数再取相反数。

其中难点不仅仅是正负的问题，还有INT32_MAX和INT32_MIN不相等的问题，因为负数是可以取到-2147483648，而正数只能取到2147483647。我看题解中很多人的方法都不周全，对于-1 - (-2147483648)这个例子，很多方法都不能通过。可能是官方的测试样例不够充分，所以都能够提交成功。

其中有一个人减法的方法是a + neg(b)。但是对于b=-2147483648这个情况，是不能直接取负数的。因此要进行特判。

下面我分成四个部分叙述我的方法。

neg取相反数

对于一个数217来说，我们如何得到-217呢？我们不可能每次都从0加(-1)，先尝试-1，然后再尝试-2，直到-217为止。题目中说我们可以使用常数，可以模拟计算机二进制的存储方式。我们先看217 + (-512)是否小于0，如果小于0，说明加上负数太大了，我们换-256，看217 + (-256)是否小于0，还是小于0，我们继续看217 + (-128)是否小于0，发现大于0，说明负数小了，我们就保留-128，此时仍然剩余89，继续寻找-64，发现-64也可以，保留-64，此时剩余25，继续寻找-32，-16，-8，-4，-2，-1。最后的结果是(-128) + (-64) + (-16) + (-8) + (-1) = -217。

对于负数取相反数同理，对于-217取相反数，那就判断-217 + 512是否大于0，如果大于0，说明加上正数太大了，就换256。最后也能得到217。

因此我们要提前记录下-1，-2，-4，-8…常数，和1，2，4，8…常数，这样不用每次都推导。

至于-2147483648取相反数，我们只用在对应的操作中进行特判即可。如减法，我们在减法函数中进行特判，因此不会出现传入-2147483648数的情况。

minus减法

**对于b = INT32_MIN，我们可以返回a + INT32_MAX + 1即可。其他情况下返回a + neg(b)**。

multiply乘法

当b == 0时，return 0。当b == INT32_MIN，为了保证题目有意义，a一定是0或者1，a = 0时返回0，a = 1时返回b即可。当b < 0 时，return neg(multiply(a, neg(b)))。这用到了数学中的交换律。a x b = -1 x (a x (-1 x b))。因此我们只用考虑b是正数的情况即可。

如13 x 14，我们13相加14次，虽然可以，但是一定会TLE，因此我们仍然要用到二进制的知识。14的二进制最后四位是1110。(1110 = 8 + 4 + 2+ 0)，因此我们可以使用乘法结合律，13 x 14 = 13 x (8 + 4 + 2 + 0) = 13 x 8 + 13 x 4 + 13 x 2 + 13 x 0。我们需要直到b的二进制表示，用一个bit数组和getBin函数，获取正数b的二进制表达，因为是正数，只需要31位。然后得到了二进制位以后，tmp = a，在这个例子中tmp = 13，每次移动一个tmp += tmp，等价于tmp翻倍。如果该位是1，则加上，该位是0继续下一位。

模拟计算的过程：最低为是0，因此res += 0，此时tmp = 26，第二位是1，因此res += 26，tmp = 52，第三位是1，因此res += 52，tmp = 104，第四位是1，因此res += 104。最后res = 0 + 26 + 52 + 104 = 182。当a为负数，计算过程是一样的。

其中注意tmp要用long long类型接收，否则可能会超出表达范围。

divide除法

除法是最复杂的过程。但原理都是类似的。当a == 0时，return 0。当b == INT32_MIN时，如果a == b时，return 1，其余情况都return 0。当b == 1时，return a。当b < 0 时，我们也和乘法做类似处理，这样b就一定为正数。

下面要分类讨论a的情况。如果a为正数
如180 / 13，和乘法一样，我们也要计算13的倍数表示，13， 26， 52， 104， 208…。因为180小于208，那么说明13的16倍是不够的，但是108大于104，说明13的8倍是超过的。这时要计算-13的倍数表示，-13，-26，-52，-104，-208。为什么还需要负数表示呢？因为要用180 + (-104)，表示当前还剩余的数字。

最高位是$b \times 2^{30}$，因为b不能为0，b = 1时前面已经特判，b最小是2，因此最高位已经远远超过了所有的整型范围。因此要用long long类型保存。如果使用vector容器保存，当这个值大于a就可以停止了，为了小伙伴理解方便，就用数组保存。如本例中，我们只用保存到104和-104即可，要使用数组来保存，就需要设置一个停止位，或者用long long保存。这里为了简单，就使用long long类型。在104后面的数组都大于180，因此都是不够的，都会跳过比较。我们直接从104开始模拟。

模拟计算的过程：180大于等于104，说明180大于等于13的8倍，我们让res += 8，然后180 + (-104) = 76。继续比较，76大于等于52，说明76大于等于13的4倍，我们让res += 4，然后76 + (-52) = 24。继续比较，24小于26，说明24不够13的2倍，不做操作。继续比较，24 大于等于13，说明24大于等于13的1倍，我们让res += 1。比较完成，res = 8 + 4 + 1 = 13。

上面是a为正数的情况，a为负数类似
如-180 / 13，-180小于等于-104，说明-180小于等于13的-8倍，res += -8，然后-180 + 104 = -76。继续比较，后面的过程就不重复了，最后res = (-8) + (-4) + (-1) = 13。

有的小伙伴们就会问了，为什么a为负数时不能也利用交换律返回neg(divide(neg(a), b))呢？这个我是想过的，因为a可能等于-2147483648，那么取负数就会出现问题。因此还是分类讨论稳妥一些。

这就是上面所有的分析过程，小伙伴们也可以简单一些，全部转换为long long类型，然后都改成只看前32位。最后计算完再强制转换为int返回即可。但是核心思想全部都是一样的。

算法的**时间复杂度为$O(nlog(m))$，空间复杂度为$O(log(m))$**，其中n为操作次数，m为数据的范围，这里为int的数据大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<iostream>

using namespace std;

class Operations {
    int positive[31];
    int negative[32];
public:
    Operations() {
        int pos = 1, neg = -1;
        for (int i = 0; i < 31; i++) {
            positive[i] = pos;
            negative[i] = neg;
            neg += neg;
            if (i == 30) { break; }
            pos += pos;
        }
        negative[31] = neg;
    }

    int neg(int a) {
        int res = 0;
        if (a > 0) {
            for (int i = 31; i >= 0; i--) {
                if (res + negative[i] + a >= 0) {
                    res += negative[i];
                    if (res + a == 0) { break; }
                }
            }
        }
        else if (a < 0) {
            for (int i = 30; i >= 0; i--) {
                if (res + positive[i] + a <= 0) {
                    res += positive[i];
                    if (res + a == 0) { break; }
                }
            }
        }
        return res;
    }

    void getBin(int a, int* bit) {
        for (int i = 30; i >= 0; i--) { 
            if (a >= positive[i]) {
                bit[i] = 1;
                a += negative[i];
            }
            else {
                bit[i] = 0;
            }
        }
    }

    int minus(int a, int b) {
        return b == INT32_MIN ? a + INT32_MAX + 1 : a + neg(b);
    }

    int multiply(int a, int b) {
        if (b == 0) { return 0;  }
        if (b == INT32_MIN) { return a ? 0 : b; }
        if (b < 0) { return neg(multiply(a, neg(b))); }
        int bit[31];
        getBin(b, bit);
        int res = 0;
        long long tmp = a;
        for (int i = 0; i < 31; i++) {
            if (bit[i]) { res += tmp; }
            tmp += tmp;
            if (tmp > INT32_MAX || tmp < INT32_MIN) { break; }
        }
        return res;
    }

    int divide(int a, int b) {
        if (a == 0) { return 0; }
        if (b == INT32_MIN) { return a == b ? 1 : 0; }
        if (b == 1) { return a; }
        return b < 0 ? neg(divide(a, neg(b), b)) : divide(a, b, neg(b));
    }

    int divide(int a, int positiveB, int negativeB) {
        long long Ptimes[31], Ntimes[31];
        long long Ptmp = positiveB, Ntmp = negativeB;
        int res = 0;
        for (int i = 0; i < 31; i++) {
            Ptimes[i] = Ptmp;
            Ptmp += Ptmp;
            Ntimes[i] = Ntmp;
            Ntmp += Ntmp;
        }
        if (a > 0) {
            for (int i = 30; i >= 0; i--) {
                if (a >= Ptimes[i]) {
                    res += positive[i];
                    a += Ntimes[i];
                }
            }
        }
        else {
            for (int i = 30; i >= 0; i--) {
                if (a <= Ntimes[i]) {
                    res += negative[i];
                    a += Ptimes[i];
                }
            }
        }
        return res;
    }
};

刷题总结

  这个题目真的是太复杂了，但是其中蕴含着二进制的奥秘，这个知识点是需要小伙伴们掌握的。

-------------本文结束感谢您的阅读-------------
0%