题解 | #求1+2+3+...+n#

这是一题考虑思维广度的题目:
1、不能使用判断语句，可以从逻辑运算符考虑
2、利用类型强转，函数指针
3、模板元编程
4、放在C++类中考虑
6、将1+2+3+...+n的结果开辟为动态内存，内存计算
题解一：递归+逻辑运算符
前置知识：
位运算|、&与逻辑运算符&&、||的区别。
1、&、|是按位运算，符号两端为两个数；&&、||是两个逻辑表达式；
2、&&、||运算具有短路功能，示例：(A)&&(B)当A部分不成立，则B部分不会执行，(A)||(B)当A部分成立，则B部分不会执行。

复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n),递归深度;

如图所示:
图片说明

采用递归实现1+……n的代码

class Solution {
public:
    int Sum_Solution(int n) {
        if(n==1)return 1;//结束条件；
        return n+Sum_Solution(n-1);
    }
};

上述代码出现了if判断语句，我们可以采用逻辑运算符&&的短路特性代替这一语句，具体修改如下：

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

题解二:函数指针数组+类型强制
主要思路:
1、声明一个函数指针；
2、定义两个函数，一个是循环终止函数，一个是递归调用函数；
3、并定义一个函数指针数组，指向上述定义的两个函数；
4、重点步骤:利用类型强转，当n==0执行循环终止函数，否则类型强转成bool，则n==1，执行递归调用。在C++中可以利用bool类型，而在纯C环境下可以使用(!!n)两次取反操作将n的取值范围限定在{0，1}中。

复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n),递归深度;

图片说明

实现如下:

typedef int (*p)(int);
int func(int n){//终止循环函数
        return 0;
}
int func1(int n){//递归调用函数
    p oo[2]={func,func1};
    return n+oo[(bool)n](n-1);//C++环境下可以这样写；
    //return n+oo[!!n](n-1);//纯C环境下可以这样写；
}
class Solution {
public:
    int Sum_Solution(int n) {
        return func1(n);
    }
};

题解三:虚函数
主要思路:拓展题解二的函数指针思路，在C++中，虚函数的底层实现类似于函数指针，所以我们可以采用虚函数实现。
1、定义一个父类与一个虚函数；
2、定义一个子类继承父类，重写虚函数；
3、定义一个父类数组
4、操作同题解二第4步操作；

复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n),递归深度;

class A;//声明类A
A* Arr[2];
class A{
    public:
    virtual int Sum(int n){
        return 0;
    }
};
class B:public A{
    public:
    virtual int Sum(int n){
        return Arr[(bool)n]->Sum(n-1)+n;//bool类型转换;
        //return Arr[!!n]->Sum(n-1)+n;也可以使用两次取反操作；
    }
};
class Solution {
public:
    int Sum_Solution(int n) {
        A a;
        B b;
        Arr[0]=&a;
        Arr[1]=&b;
        return Arr[1]->Sum(n);
    }
};

题解四:模板元编程(不能满足多组测试样例)
主要思路：
借用模板元编程在编译时期展开完成类似递归操作;
缺点：
在编译期间完成计算，则意味着n必须是常量，不能动态输入，且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大

实现如下:

template<int n> struct Sum{
    enum value{N=Sum<n-1>::N+n};
};
template<> struct Sum<1>{
    enum value{N=1};
};
template<> struct Sum<0>{
    enum value{N=0};
};

题解五:利用构造函数求解
主要思路:
1、利用静态成员变量N;
2、调用n次构造函数，N递增n次，并且累加n次变量N到sum中求和;
时间复杂度:O(n),调用n次构造函数
空间复杂度:O(n),开辟n的类的空间;

class A{
    public:
    A(){++N;sum+=N;}
    static void Reset(){N=0;sum=0;}
    static int N;
    static int sum;
};
int A::N=0;
int A::sum=0;
class Solution {
public:
    int Sum_Solution(int n) {
       A::Reset();
       A *a=new A[n];
        delete []a;//防止内存泄漏
        a=nullptr;//防止悬空指针
       return A::sum;
    }
};

题解六:利用求和公式+申请内存(OJ能过，但是语法是错误的)
利用求和公式 $图片说明$ ,我们可以申请 $图片说明$ 的内存空间，计算出内存除以2得出结果;
但是n必须是常量
假设n为3，如图所示，每一个块内存大小为1字节：

可以在编译器得到数组大小为12，根据求和公式，最终结果为6；
复杂度
时间复杂度:O(1)
空间复杂度:O(n^2)

class Solution {
public:
    int Sum_Solution(int n) {
       bool a[n][n+1];//也可以使用char,表示类型只占用1个字节；
       return sizeof(a)>>1;
    }
};