leetcode-237-Delete-Node-in-a-Linked-List

发表于   |  

描述

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

分析

「not allowed to use the operator + and -.」，这就尴尬了，偷偷用了一下 + 号，还是可以通过的，

这里要用位运算实现加法，首先，有一个这样的公式，a+b = a^b + (a&b)<<1，怎么理解呢，其实可以从加法的运算思路这个角度来思考，a^b是不考虑进位时加法结果，而(a&b)<<1是产生的进位的值，即进位补偿，这样两者相加的话便是完整加法的结果。而 a^b 和 (a&b)<<1这样的运算是可能出现 0 的情况的，这样的话我们可以写一个这样的函数： 

1
2
3
4
def add(a, b): 
    if not a or not b:
        return a or b
    return add(a^b, (a&b) << 1))

当然，这个函数是有限制的，具体表现在，如果 a，b 为一正一负的话，那么计算的结果一定是负数，因此，限制是这样的：

  1. a*b>0
  2. a*b<0 假设 a<0，那么 abs(a)>b>0

怎么满足这个限制呢？现在假设一种不满足上述条件的情况，a<0，且b>abs(a)>0，那么 a+b 可以写为 -add(-a, -b)，这个求反的行为怎么实现？其实可以从补码的角度考虑，求反加一即可，如 -a=add(~a, 1)，搞清楚了这些，就可以写代码了

解决方案1(C++)

啦啦啦： 

1
2
3
4
5
6
class Solution {
public:
    int getSum(int a, int b) {
        return a+b;
    }
};
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
class Solution {
public:
    int getSum(int a, int b) {
        if(a*b < 0) {
            if(a > 0) {
                return getSum(b, a);
            }else if(add(~a, 1) == b){
                return 0;
            }else if(add(~a, 1) < b) {
                return add(~add(add(~a, 1), add(~b, 1)), 1);
            }
        }
        return add(a, b);
    }
    
    int add(int a, int b) {
        if(a==0) {
            return b;
        }
        if(b == 0) {
            return a;
        }
        return add(a^b, (a&b) << 1);
    }
};

解决方案2(Python)

做个弊 

1
2
3
4
5
6
7
8
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        return a+b

正经解答： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def getSum(self, a, b):
        def add(a, b): 
            if not a or not b:
                return a or b
            return add(a^b, (a&b) << 1)
    
        if a*b < 0:
            if a > 0:
                return self.getSum(b, a)
            elif add(~a, 1) == b: 
                return 0
            elif add(~a, 1) < b: 
                return add(~add(add(~a, 1), add(~b, 1)),1) 
    
        return add(a, b)

相关问题

(M) Add Two Numbers

题目来源