
网站救助计划
1.为阅读体验,本站无任何广告,也无任何盈利方法,站长一直在用爱发电,现濒临倒闭,希望有能力的同学能帮忙分担服务器成本
2.捐助10元及以上同学,可添加站长微信lurenzhang888,备注捐助,网站倒闭后可联系站长领取本站pdf内容
3.若网站能存活下来,后续将会持续更新内容
题目描述
求 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完整版