LeetCode 面试题 16.09. 运算

一、题目

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

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

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

  点击此处跳转题目。

二、C# 题解

  使用常数数组 Poss 和 Negs 分别记录 2 次幂的正负值，便于后续使用。

P o s s : { 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 } N e g s : { − 2 0 − 2 1 − 2 2 − 2 3 − 2 4 − 2 5 − 2 6 − 2 7 } \begin{array}{l} \hspace{0.15em}Poss:\{\hspace{0.78em} 2^0 \hspace{2.2em} 2^1 \hspace{2.25em} 2^2 \hspace{2.4em} 2^3 \hspace{2.1em} 2^4 \hspace{2.25em} 2^5 \hspace{2.25em} 2^6 \hspace{2.1em} 2^7\} \\ Negs:\{-2^0 \hspace{1em} -2^1 \hspace{1em} -2^2 \hspace{1.2em} -2^3 \hspace{0.9em} -2^4 \hspace{1em} -2^5 \hspace{1em} -2^6 \hspace{0.9em} -2^7\} \\ \end{array} Poss:{2021222324252627}Negs:{−20−21−22−23−24−25−26−27}​

• Negative(int a)：
    如果 a 是正数，则遍历负数数组 Negs；如果 a 是负数，则遍历正数数组 Poss。每次遍历判断相加后是否溢出，如果不溢出，就相加，否则跳过。
    溢出判断条件：ans + nums[i] + a 与 a 异号，则溢出。

a : 13 ⟵ 方向 n u m s : { − 2 0 ‾ − 2 1 − 2 2 ‾ − 2 3 ‾ − 2 4 − 2 5 − 2 6 − 2 7 } ↑ ↑ ↑ a n s : ( − 1 ) + ( − 4 ) + ( − 8 ) = − 13 \begin{array}{l} \hspace{2em}a:13\\ \hspace{25.9em} \longleftarrow 方向\\ nums:\{\underline{\bold{-2^0}} \hspace{1em} -2^1 \hspace{1em} \underline{\bold{-2^2}} \hspace{1.2em} \underline{\bold{-2^3}} \hspace{0.9em} -2^4 \hspace{1em} -2^5 \hspace{1em} -2^6 \hspace{0.9em} -2^7\} \\ \hspace{4.5em} \uparrow \hspace{5.6em} \uparrow \hspace{2.6em} \uparrow \\ \hspace{0.9em}ans:\hspace{0.3em} (-1) \hspace{1.35em} + \hspace{1.35em} (-4) \hspace{0em} + \hspace{0em} (-8) \hspace{12.5em} = -13\ \end{array} a:13⟵方向nums:{−20​−21−22​−23​−24−25−26−27}↑↑↑ans:(−1)+(−4)+(−8)=−13 ​

• Minus(int a, int b)：
    即 a + Negative(b)。

• Multipy(int a, int b)：
    类似 Negative(int a) 的思想，Negative(int a) 可以看做是 Multipy(-1, int a)，因此将 nums 数组扩展为 a * 2ⁱ 即可求解 a * b。在求解 -b 时（记为 cnt），累加 a * 2ⁱ，即可得到答案。
    这里需要注意 a 的符号，如果 b < 0，需要将 a 异号。

a : 5 b : − 13 c n t : ( − 1 ) + ( − 4 ) + ( − 8 ) = − 13 ↓ ↓ ↓ c n t s : { 2 0 ‾ 2 1 2 2 ‾ 2 3 ‾ 2 4 2 5 2 6 2 7 } ⟵ 方向 n u m s : { − 5 ∗ 2 0 ‾ − 5 ∗ 2 1 − 5 ∗ 2 2 ‾ − 5 ∗ 2 3 ‾ − 5 ∗ 2 4 − 5 ∗ 2 5 − 5 ∗ 2 6 − 5 ∗ 2 7 } ↑ ↑ ↑ a n s : ( − 5 ∗ 1 ) + ( − 5 ∗ 4 ) + ( − 5 ∗ 8 ) = − 5 ∗ 13 \begin{array}{l} \hspace{2em}a:5 \hspace{2em} b:-13\\\\ \hspace{1.1em} cnt: \hspace{1.1em} (-1) \hspace{2.9em} + \hspace{2.9em} (-4) \hspace{0.8em} + \hspace{0.8em} (-8) \hspace{19em} = -13\\ \hspace{5.2em} \downarrow \hspace{8.7em} \downarrow \hspace{4.2em} \downarrow \\ \hspace{0.6em} cnts: \{ \hspace{1.2em} \underline{\bold{2^0}} \hspace{3.6em} 2^1 \hspace{3.6em} \underline{\bold{2^2}} \hspace{3.6em} \underline{\bold{2^3}} \hspace{3.6em} 2^4 \hspace{3.6em} 2^5 \hspace{3.6em} 2^6 \hspace{3.6em} 2^7 \hspace{0.9em} \}\\\\ \hspace{38em} \longleftarrow 方向\\\\ nums:\{\underline{\bold{-5*2^0}} \hspace{1em} -5*2^1 \hspace{1em} \underline{\bold{-5*2^2}} \hspace{1.2em} \underline{\bold{-5*2^3}} \hspace{0.9em} -5*2^4 \hspace{1em} -5*2^5 \hspace{1em} -5*2^6 \hspace{0.9em} -5*2^7\} \\ \hspace{5.2em} \uparrow \hspace{8.7em} \uparrow \hspace{4.2em} \uparrow \\ \hspace{0.9em}ans:\hspace{0.3em} (-5*1) \hspace{2.2em} + \hspace{2.2em} (-5*4) \hspace{0em} + \hspace{0em} (-5*8) \hspace{18.5em} = -5*13\\ \end{array} a:5b:−13cnt:(−1)+(−4)+(−8)=−13↓↓↓cnts:{20​2122​23​24252627}⟵方向nums:{−5∗20​−5∗21−5∗22​−5∗23​−5∗24−5∗25−5∗26−5∗27}↑↑↑ans:(−5∗1)+(−5∗4)+(−5∗8)=−5∗13​

• Divide(int a, int b)：
    对 b 进行扩展为 nums，即 nums = b * Poss（若 a、b 异号，则 b 取反，目的是使 nums 符号与 a 相同），让 a 尝试依次减去 nums[i]，能减则减，减去后 ans 加上对应的 cnts[i]（若 a、b 异号，则 cnts 数组为负值；反之，cnts 数组为正值）。是否选取第 i 个元素的条件：
    1. a > 0，则 sum + nums[i] <= a。
    2. a < 0，则 sum + nums[i] >= a。

a : − 67 b : 5 a n s : ( − 1 ) + ( − 4 ) + ( − 8 ) = − 13 ↓ ↓ ↓ c n t s : { − 2 0 ‾ − 2 1 − 2 2 ‾ − 2 3 ‾ − 2 4 − 2 5 − 2 6 − 2 7 } ⟵ 方向 n u m s : { − 5 ∗ 2 0 ‾ − 5 ∗ 2 1 − 5 ∗ 2 2 ‾ − 5 ∗ 2 3 ‾ − 5 ∗ 2 4 − 5 ∗ 2 5 − 5 ∗ 2 6 − 5 ∗ 2 7 } ↑ ↑ ↑ s u m : ( − 65 ) ← ( − 60 ) ← ( − 40 ) = − 5 ∗ 13 \begin{array}{l} \hspace{2em}a:-67 \hspace{2em} b:5\\\\ \hspace{0.9em} ans: \hspace{1.1em} (-1) \hspace{2.9em} + \hspace{2.9em} (-4) \hspace{0.8em} + \hspace{0.8em} (-8) \hspace{19em} = -13\\ \hspace{5.2em} \downarrow \hspace{8.7em} \downarrow \hspace{4.2em} \downarrow \\ \hspace{0.6em} cnts: \{ \hspace{0.8em} \underline{\bold{-2^0}} \hspace{2.6em} -2^1 \hspace{2.6em} \underline{\bold{-2^2}} \hspace{2.6em} \underline{\bold{-2^3}} \hspace{2.6em} -2^4 \hspace{2.5em} -2^5 \hspace{2.4em} -2^6 \hspace{2.4em} -2^7 \hspace{0.4em} \}\\\\ \hspace{38em} \longleftarrow 方向\\\\ nums:\{\underline{\bold{-5*2^0}} \hspace{1em} -5*2^1 \hspace{1em} \underline{\bold{-5*2^2}} \hspace{1.2em} \underline{\bold{-5*2^3}} \hspace{0.9em} -5*2^4 \hspace{1em} -5*2^5 \hspace{1em} -5*2^6 \hspace{0.9em} -5*2^7\} \\ \hspace{5.2em} \uparrow \hspace{8.7em} \uparrow \hspace{4.2em} \uparrow \\ \hspace{0.6em}sum:\hspace{0.9em} (-65) \hspace{2.5em} \leftarrow \hspace{2.5em} (-60) \hspace{0.3em} \leftarrow \hspace{0.3em} (-40) \hspace{18.8em} = -5*13\\ \end{array} a:−67b:5ans:(−1)+(−4)+(−8)=−13↓↓↓cnts:{−20​−21−22​−23​−24−25−26−27}⟵方向nums:{−5∗20​−5∗21−5∗22​−5∗23​−5∗24−5∗25−5∗26−5∗27}↑↑↑sum:(−65)←(−60)←(−40)=−5∗13​

public class Operations {private static long[] Negs, Poss;private const  int    NEG_ONE = -1;private const  int    ARR_LEN = 32;static Operations() {long p = 1, n = -1;Poss = new long[ARR_LEN];Negs = new long[ARR_LEN];for (int i = 0; i < ARR_LEN; i++) { // 初始化正、负数组Poss[i] = p;p += p;Negs[i] = n;n += n;}}public int Minus(int a, int b) {return (int)(a + Negative(b));}public int Multiply(int a, int b) {if (a == 0 || b == 0) return 0;long   p    = b > 0 ? a : Negative(a), ans  = 0, cnt = 0;long[] cnts = b > 0 ? Negs : Poss,     nums = new long[ARR_LEN];for (int i = 0; i < ARR_LEN; i++) { // 初始化记录数组nums[i] = p;p += p;}// 计算 -b 的过程中，同比例计算 ansfor (int i = ARR_LEN + NEG_ONE; i >= 0; i += NEG_ONE) {if (SameSignal(cnt + cnts[i] + b, b)) {cnt += cnts[i];ans += nums[i];}if (cnt + b == 0) return (int)ans;}return (int)ans;}public int Divide(int a, int b) {if (a == 0) return 0;long   p    = SameSignal(a, b) ? b : Negative(b), sum  = 0, ans = 0;long[] cnts = SameSignal(a, b) ? Poss : Negs,     nums = new long[ARR_LEN];for (int i = 0; i < ARR_LEN; i++) { // 初始化记录数组nums[i] = p;p += p;}for (int i = ARR_LEN + NEG_ONE; i >= 0; i += NEG_ONE) {// a > 0，则用 <= 判断溢出，a < 0，则用 >= 判断溢出if (a > 0 && sum + nums[i] <= a || a < 0 && sum + nums[i] >= a) {sum += nums[i];ans += cnts[i];}}return (int)ans;}// 求 -apublic long Negative(long a) {if (a == 0) return 0;long[] nums = a > 0 ? Negs : Poss; // 寻找与 a 异号的数组long   ans  = 0;for (int i = ARR_LEN + NEG_ONE; i >= 0; i += NEG_ONE) { // 绝对值大 -> 小遍历if (SameSignal(ans + nums[i] + a, a))               // ans + nums[i] 未溢出，则加上 nums[i]ans += nums[i];if (ans + a == 0) return ans; // 提前返回}return ans;}// 判断 a、b 符号是否相同// 0 既看作正数也看作负数public bool SameSignal(long a, long b) {return a <= 0 && b <= 0 || a >= 0 && b >= 0;}
}/*** 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);*/

• 时间：104 ms，击败 80.00% 使用 C# 的用户
• 内存：48.40 MB，击败 0.00% 使用 C# 的用户