JZ64 求1+2+3+...+n

发表于 分类于 本文字数： 196 阅读时长 ≈ 1 分钟

JZ64 求1+2+3+…+n

描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

数据范围： $0<n≤200$
进阶： 空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

1
2
输入：5
返回值：15

示例2

1
2
输入：1
返回值：1

题解

我冥思苦想想不到有什么trick，想到的办法都很麻烦，然后看了讨论才知道，原来牛魔的且运算也算位运算啊。回到这题，使用与运算的短路来递归计算即可(短路：$aandb$在确定a不成立的情况下不会计算b)。

代码

1
2
3
4
5
6
7
# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        ans = n
        temp = ans and self.Sum_Solution(n-1)
        ans += temp
        return ans