写在前面的话:
大家好,我是一名正在努力学习数据结构和算法的新手。这篇文章是我在学习python的各类数据结构以及基础算法过程中的一些笔记和心得,希望能和同样在学习该方面知识的朋友们分享。由于我的知识有限,文章中可能存在错误或不准确的地方,欢迎大家在评论区提出建议和指正。我非常期待大家的反馈,以便我能不断学习和进步。同时,我也会在文章中注明参考的资料,以示对原作者的尊重。
PS:本帖以记录学习心得和刷题记录解析为主,没有其他大博主那么专业,但是简单易懂^-^
本贴的其他相关学习笔记资料可以通过订阅专栏获取,喜欢的小伙伴可以多多点赞+关注呀!后续会 持续更新相关资源的~
今天是我们备战的第二天,我们将从最简单的连续求和公式开始学习,通过刷题来加深对枚举算法的理解。该题偏向于数学推导,大部分工作会在草稿纸上推演,推完之后代码反而非常简洁和简单。
题解资源参考指路:
链接:https://leetcode.cn/problems/consecutive-numbers-sum/solutions/1533041/-by-meteordream-sfib/
通过审题可知,题目需要列举所有满足连续数字之和=n的数据组数。
因此非常容易联想到等差数列求和公式,只不过这里是d=1的等差数列。
(首项+末项)*项数//2=总和n
在这里,为了进一步化简表达式,末项可以用包含首项和项数的式子来表达:
按理来说,我只需要利用循环,得到起始点a的值以及k的值不同时是否满足其式子==n就可知该组是否可行,此时就是枚举所有可能的a或k。
不难发现,a作为首项,其列举略微复杂,目前只知道最小的a就一定是1(不考虑是否满足式子要求的情况下)。但之后的a基本上是随机出现来满足式子要求,因此不好列举
而列举k,即一组数据里面的项数,最多也不可能超过总和n的大小,即k<n。k!=n因为此时连续数字就只能是1了,不满足连续数字的要求(如n=2,k=2 具体数据只能是1,1不满足要求)
因此,在先记录n本身为一组符合条件的组的前提下,我们可以在(2,n)开for循环列举k的所有可能情况,然后求出a对应的值,最后判断他们两个当前数据放入式子中是否等于n则可得知该组数据是否满足要求。
具体代码如下:
class Solution:def consecutiveNumbersSum(self, n: int) -> int:cnt = 1for k in range(2, n):a = (2 * n // k + 1 - k) // 2if a < 1:breakelif n == (2 * a + k - 1) * k // 2:cnt += 1return cnt
非常简洁,重点在于前面的数学推导。
这也告诉我们,拿到一个算法题时,第一步并非直接上手打代码,最重要的是要先在草稿纸上分析,推演,列举特殊情况,找到规律和思路再上手打代码,才是行之有效的方法论。
最后,感谢每一位阅读这篇文章的朋友,你们的反馈对我来说非常宝贵。如果有任何问题或建议,请随时告诉我。让我们一起学习和进步吧!如果您喜欢我的内容,别忘了点赞和关注哦,我会定期分享更多有价值的信息。