求 1 + 2 + 3 + … + n,要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句(A ? B : C)。
思路
我们手里现在可以使用(按优先级高低):
- 单目运算符:++ 和 —
- 双目运算符:+ 和 -
- 移位运算符:<< 和 >>
- 关系运算符:>、< 等
- 逻辑运算符:&&、||、&、|、^
- 赋值运算符:=
单目和双目的作用是一样的。移位显然没有规律性,因为一个二进制位并不能区分某个数和其他数,这也就排除了&、| 和 ^,因为不需要做位运算了。关系运算符要和 if 匹配,但这是不行的,这时看看剩下的运算符只能选 && 和 || 了。如果做过 Java 或者 JS 笔试题,会对这两个运算符非常敏感,他们有短路特性,前面的条件判真(或者假)了,就不会再执行后面的条件了,这时就能联想到 —n,直到等于0就能返回值。
一般编程语言代码实现
这里使用 JS 来完成这道题目。因为 && 运算符具有短路的特性,运算符左边部分为 false(或者 0)的话,则不计算右边的部分,因此这就形成了天然的递归出口:
function Sum_Solution(n) {
// write code here
let ans = n
ans && (ans += Sum_Solution(n - 1))
return ans
}
Python 的代码实现
在 Python 中是没有 && 及 || 这两个运算符的,取而代之的是英文 and 和 or。要注意 Python 中逻辑运算符的用法,例如 a and b 的情况:a 为 False,返回 a;a 为 True,就返回 b。并且 and 的左右两边是不能执行赋值运算操作的,所以需要对上述形式的代码进行改动。但其实恰恰由于上述的特性,反而使得这道题目使用 Python 来实现的话会变得更加简单:
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
return (n and n + self.Sum_Solution(n - 1))