【todo】【特例】剑指offer——面试题46：求1+2+...+n

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
个人感觉这个题听创新的，现在把集中有代表性的解法总结在这里。
力扣

java答案，迭代

class Solution {
    public int mechanicalAccumulator(int target) {
        boolean x = target > 1 && (target += mechanicalAccumulator(target - 1)) > 0;
        return target;
    }
}

##Solution1:(重点)
利用变长数组.
C99标准引入了变长数组，它允许使用变量定义数组各维，关于变长数组详见《C Primer Plus（第五版）》P273.
这是我知道的代码最简洁的方法。
参考网址：https://www.nowcoder.com/profile/5104574/codeBookDetail?submissionId=15519030

class Solution {
public:
    int Sum_Solution(int n) {
        bool a[n][n+1];
        return sizeof(a)>>1;
    }
};

##Solution2:
利用构造函数，树上的思路（理解的不是很透彻。。）
循环只是让相同的代码重复执行n遍而已。先定义一个类型，接着创建n个该类型的实例，那么这个类型的构造函数将确定会被调用n次。我们可以将与累加相关的代码放到构造函数里。

class Temp {
public:
    Temp() { ++N; Sum += N; }
    static void Reset() { N = 0; Sum = 0; }
    static unsigned int GetSum() { return Sum; }
private:
    static unsigned int N;
    static unsigned int Sum;
};

unsigned int Temp::N = 0;
unsigned int Temp::Sum = 0;

class Solution {
public:
    int Sum_Solution(int n) {
        Temp::Reset();
        
        Temp *a = new Temp[n];
        delete []a;
        a = NULL;
        
        return Temp::GetSum();
    }
};

##Solution3:
利用虚函数，具体看书中解释（同样理解的不是很透彻。。。->_<-）

class A;
A* Array[2];

class A {
public:
    virtual unsigned int Sum (unsigned int n){
        return 0;
    }
};

class B: public A {
public:
    virtual unsigned int Sum (unsigned int n) {
        return Array[!!n]->Sum(n-1) + n;
    }
};

class Solution {
public:
    int Sum_Solution(int n) {
        A a;
        B b;
        Array[0] = &a;
        Array[1] = &b;
        
        int value = Array[1]->Sum(n);
        
        return value;
    }
};

##Solution4:
利用函数指针求解（同样理解的不是很透彻。。。->_<-）

typedef int (*func)( int );
class Solution {
public:
    static int Solution1(int n )
        { return 0;}
    
    static int Sum_Solution(int n) {
        static func f[2] = {Solution1,Sum_Solution};
        return n+f[!!n](n-1);
    }
};

##Solution5
利用模板求解

//缺点多&&难理解==》算了吧

##Solution6:(重点)
这个递归写的真是666~~
参考网址：https://www.nowcoder.com/profile/5104574/codeBookDetail?submissionId=15519030
解题思路：
1.需利用逻辑与的短路特性实现递归终止。 2.当ans == 0时，(ans > 0) && (ans += Sum_Solution(ans - 1))只执行前面的判断，为false，然后直接返回0;
3.当n > 0时，执行ans += Sum_Solution(ans - 1)，实现递归计算Sum_Solution(n)。
真是666啊！

class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
}