剑指Offer 64. 求1 + 2 + ... + n
2021/7/15 23:38:59
本文主要是介绍剑指Offer 64. 求1 + 2 + ... + n,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
示例1:
输入:5 返回值:15
方法一:不使用if的递归
求解
1
+
2
+
⋯
+
n
1+2+\cdots+n
1+2+⋯+n,有以下几种方法:(1)使用高斯公式
s
u
m
=
n
(
1
+
n
)
/
2
sum=n(1+n)/2
sum=n(1+n)/2,但是题目中明确限制使用乘除法,所以此方法不可行。(2)使用循环求解,但是题目中又限制使用for、while,所以此方法也不可行。(3)递归方法,代码如下:
public int sum(int n) { if (n == 1) return 1; return n + sum(n - 1); }
但是此方法中使用了if语句,所以表面上看,递归方法也是不行。进一步考虑,if是用于递归结束,如果n == 1
,递归结束,如果n > 1
,继续递归,这可以通过短路与&&来实现,即(n > 1) && ((n + sum (n - 1)) > 0)
,因为n == 1
时,第一个判断为false,短路与就不进行第一个判断,递归结束;当n > 1
时,第一个判断为true,短路与还需要进行第二个判断,即继续递归,和上面的代码逻辑一致。
public class Solution { public int Sum_Solution(int n) { boolean b = (n > 1) && ((n += Sum_Solution(n - 1)) > 0); return n; } }
时间复杂度:依次需要计算每一个整数的和, O ( n ) O(n) O(n);空间复杂度:每次计算都需要开辟栈, O ( n ) O(n) O(n)。
结束语:如果本篇博客对您有帮助,请点赞、收藏或关注,您的鼓励是博主进步的动力,感谢支持,共同进步。
这篇关于剑指Offer 64. 求1 + 2 + ... + n的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求