微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 64. 求1+2+...+n
本文链接:https://www.mianshi.online/2812.html

题目描述

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

示例 1:

输入: n = 3
输出: 6

示例 2:

输入: n = 9
输出: 45

限制:

  • 1 <= n <= 10000

题解

(递归) O(n)

递归求解替换 for 循环 1 + 2 + … + n 只不过需要将 if 替换掉,依据 A && B 的性质,如果 A 为 false,B 就不执行,如果 A 是 true,B 还要进行判断。同样的对于 A || B 依然有类似的性质,如果 A 是 true,B 就不执行,如果 A 是 false,B 还要进行判断。

因此我们可以用逻辑与 &&​ 运算符将 if 完美替换 if (n > 0) res += getSum(n - 1) -> n > 0 && (res += getSum(n - 1))

时间复杂度

递归 n 次,时间复杂度为 O(n)

时间复杂度

递归系统调用栈的空间为 O(n)

C++ 代码

class Solution {
public:
    int sumNums(int n) {
        int res = n;
        n > 0 && (res += sumNums(n - 1));
        return res;
    }
};

Java 代码

class Solution {
    public int sumNums(int n) {
        int res = n;
        if (n > 0) {
            res += sumNums(n - 1);
        }
        return res;
    }
}

Python 代码

class Solution:
    def sumNums(self, n: int) -> int:
        res = n
        if n > 0:
            res += self.sumNums(n - 1)
        return res

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版