0%

CodingInterview-求1+2+3+...+n

这道题本身很简单,但是因为加了很多限制条件,所以实际上主要是在考虑对 C++ 的掌握程度。

但是我对 C++ 的掌握并不好,所以只能参考书中的方法进行学习。

使用构造函数

第一种方法是使用类的构造函数和类的静态成员变量。这个方法看懂了其实很简单,但是在编码的时候我遇到了好几个关于类的静态成员的问题。第一个是需要在类声明后就进行初始化(不能在其他函数中),第二个是调用类的静态成员需要使用::访问符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Temp{
public:
Temp(){Sum+=++N;}
static void Init(){N=0;Sum=0;}
static int GetSum(){return Sum;}
static int N;
static int Sum;
};

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

class Solution {
public:
int Sum_Solution(int n) {
if(n<0) return 0;
Temp::Init();
Temp *t=new Temp[n];
delete []t;
t=NULL;
return Temp::GetSum();
}
};

使用虚函数

这个思路也很有意思,使用 !!n 将 n 转换成了 0 和 1,即 false 和 true。然后使用类的多态性对良好总不同的函数进行选择,其中类 A 中的 Sum 函数表示递归结束,类 B 中的 Sum 函数表示不断的递归,而判断是否结束就使用了 !!n 的转换,思路非常巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class A;
A* Array[2];

class A{
public:
virtual int Sum(int n){
return 0;
}
};
class B:public A{
public:
virtual int Sum(int n){
return n+Array[!!n]->Sum(n-1);
}
};
class Solution {
public:
int Sum_Solution(int n) {
Array[0]=new A();
Array[1]=new B();
return Array[1]->Sum(n);
}
};

使用函数指针

这种方法的思路和上一种很像,利用两个相同类型的函数进行递归,而利用 !!n 进行递归条件的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int (*fun)(int);

int sum_end(int n){return 0;}
int sum(int n){
fun f[2]={sum_end,sum};
return n+f[!!n](n-1);
}
class Solution {
public:
int Sum_Solution(int n) {
return sum(n);
}
};

使用模板

使用模板虽然可以解决部分问题,但是 n 并不能是一个输入的变量,必须是一个编译时确定的常量,而且 n 也不能太大,所以并不是很实用。

1
2
3
4
5
6
7
8
9
10
11
12
template <int n> struct sum{
enum Value {N=sum<n-1>::N+n};
};
template <> struct sum<1>{
enum Value {N=1};
};
class Solution {
public:
int Sum_Solution(int n) {
//return sum<n>::N;
}
};