LCOF 64. 求1+2+…+n
1. 问题
求 1+2+...+n
,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
示例 1:
输入: n = 3
输出: 6
示例 2:
输入: n = 9
输出: 45
限制:
1 <= n <= 10000
2. 标签
位运算
递归
3. 解法
递归时一般都会使用条件判断语句来决定递归的出口,由于题目限制无法使用,我们可以使用逻辑运算符的短路性质来决定递归的出口。
3.1 Java
class Solution {
public int sumNums(int n) {
/**
* A && B
* A: n > 0
* B: n += sumNums(n - 1)
* 可以将判断是否为递归的出口看作 A 部分
* 将递归的主体函数看作 B 部分
* 1. 如果不是递归出口,也就是 n > 0,那么返回 True,继续执行 B 部分,进行递归
* 2. 如果是递归出口,也就是 n == 0,那么返回 False,短路,不再执行 B 部分,结束递归
*/
boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
return n;
}
}
3.2 Kotlin
?
3.3 复杂度分析
时间复杂度
O(n)
:递归函数总共递归了 n 次,每次递归中计算操作的时间复杂度为O(1)
,因此总时间复杂度为O(n)
。空间复杂度
O(n)
:递归函数的空间复杂度取决于递归调用栈的深度,这里深度为O(n)
。
4. 参考
最后更新于
这有帮助吗?