题目
剑指 Offer 64. 求1+2+…+n 求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例 1： 输入: n = 3 输出: 6 示例 2： 输入: n = 9 输出: 45 限制： 1 <= n <= 10000
想法1: 库函数
我的想法比较简单..就是调用库函数, 例如Python自带的sum()函数, 代码的话就是简单的一行:
class Solution:
def sumNums(self, n: int) -> int:
return sum(range(n+1))
但是这样的话算是取巧了, 面试时候用这个就是等着凉凉… …
想法2: 递归求和
这里借鉴了LeetCode官方题解的方法, 思路比较巧, 是使用递归, 判断的话使用&&, 算是中规中矩吧. 代码C++
class Solution {
public:
int sumNums(int n) {
n && (n += sumNums(n-1));
return n;
}
};
至于那个俄罗斯农民那个方法简直不想看, 就是把循环分开了..
想法3: 使用位运算和pow()函数
这个算是个擦边球吧, 要是人家pow也不让用呢..
class Solution:
def sumNums(self, n: int) -> int:
return (pow(n, 2) + n) >> 1
想法4: 利用异常处理
这里参考了评论老哥的方法, 也是个好办法, 就是用代码执行的异常处理结构, 作为递归中止的条件, 数组溢出则停止求和.
这里以Python的实现为例:
class Solution:
def sumNums(self, n: int) -> int:
try:
a = [0]
return a[n - 1] + n
except Exception:
return n + self.sumNums(n - 1)
可以说是一种很开阔思路的方法了. (但是速度很慢)
C++没法直接异常处理, 需要判断, 很无奈:
class Solution {
public:
int sumNums(int n) {
int a[1]{0};
try {
if (n - 1 >= 1) throw 1;
return a[n - 1] + n;
} catch (int) { return n + sumNums(n - 1); }
}
};
想法五：利用C/C++二维数组的内存计数
参考了评论的一位大佬, 惊呆我一整天..
话不多说, 上代码C++(Python没有这个特性):
class Solution {
public:
int sumNums(int n) {
// 初始化一个char类型的二维数组, 代替乘法
char a[n][n+1]; // 或者bool
// 计算内存并右移一位代替除以2的操作
return sizeof(a)>>1;
}
};
当然, 这里不用加号都是可以的:
class Solution {
public:
int sumNums(int n) {
return sizeof(char[n][-~n]) >> 1;
}
};
应该是最优解了..
想法六: 剑指offer解法1
我只能说: 太强了…
采用虚函数的动态多态调用, 父类虚成员函数作为调用的出口, 子类虚函数调用父类函数, 妙处就在于长度为2的数组, 通过两次取反完成映射, 然后完成调用.
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) {
// 实际运算: !!n将任何正整数映成1, 0映成0
return Array[!!n]->sum(n - 1) + n;
}
};
class Solution {
public:
int sumNums(int n) {
A a;
B b;
Array[0] = &a;
Array[1] = &b;
return Array[1]->sum(n);
}
};
当然, 使用C-style的函数指针也能做: (简洁一些)
typedef unsigned int (*fun)(unsigned int);
// 调用出口
unsigned int Fun1(unsigned int n) { return 0; }
unsigned int Fun2(unsigned int n) {
static fun f[2] = {Fun1, Fun2}; // 函数指针数组
return n + f[!!n](n - 1);
}
void t4(int n) {
// 函数指针
cout << Fun2(n) << endl; // 5050
}
想法七: 剑指offer2
动态数组+构造函数内加法
class Tmp {
public:
Tmp() {
++N;
sum += N;
}
static void Reset() {
N = 0;
sum = 0;
}
static unsigned int GetSum() { return sum; }
private:
static unsigned int N, sum;
};
unsigned int Tmp::N = 0, Tmp::sum = 0;
void t2(int n) {
// 本质是动态数组调用N次构造函数, 构造函数内完成加法
Tmp::Reset();
auto a = new Tmp[n];
delete[] a;
a = NULL;
cout << Tmp::GetSum() << endl; // 5050
}
想法八: 剑指offer3
模板元编程:
template <unsigned int n>
struct Tmp1 {
enum Value { N = Tmp1<n - 1>::N + n };
};
template <>
struct Tmp1<1> {
enum Value { N = 1 };
};
void t5(int n) {
// 模板递归, 缺点: 只能指定编译期常量
cout << Tmp1<100>::N << endl; // 5050
}