[剑指Offer-64][中等] 求1+2+…+n

题目描述

剑指 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到n这些数字, 将它们逐个加在一起, 得到结果. 但for, while等循环方法都被禁用, 我们要想一个替代的方法.

替代循环的方法就是递归.

然后无论是循环还是递归, 都要有一个停止的条件, 使用条件, 就要使用if或者条件表达式, 但这些都被禁用了, 那么什么方法可以进行替代呢?

答案是逻辑运算符. Python中有and, or, not三种逻辑运算符, 其中and, or都接受两个变量(或表达式), 且都具有短路效应, 即对A and B来说, A如果成立, 为False, 就不会执行B了; 同样对A or B, A如果为True, 也不会执行B. 这种短路效应可以控制递归终止, 起到了代替if的作用

我们的终止条件就是当递归到当前数字num为0时停止, 0在单独进行判断时为False, 因此我们可以选用and逻辑运算符进行短路.

在Python中我们熟悉return A or B这种表达式, 当A为True的时候返回A, 否则返回B. 而其实也有return A and B这种形式, 当A为False的时候返回A, 否则返回B. 因此可以用如下的一行代码解决本题.

class Solution:
    def sumNums(self, n: int) -> int:
        return n and (n + self.sumNums(n-1))

可以总结为: Python的 and 操作如果最后结果为真, 返回最后一个表达式的值; or 操作如果结果为真, 返回第一个结果为真的表达式的值.