python剑指offer系列和为S的连续正数序列

news/2024/7/10 3:30:44 标签: 数据结构, 优化

题目:

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?


思路:

连续正数序列为等差数列,和为cur =(low + high)*(high - low +1)/2,定义两个指针,low=1,high=2,当和>cur时low+=1,反之high+=1


代码:

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        ###定义两个指针
        low = 1
        high = 2
        all_result = []
        while low < high:
            cur = (low + high)*(high - low +1)/2
            if cur < tsum:
                high += 1
            elif cur == tsum:
                all_result.append(list(range(low,high+1)))
                low +=1
            else:
                low +=1
        return all_result


http://www.niftyadmin.cn/n/1870350.html

相关文章

python剑指offer系列和为S的两个数字

题目&#xff1a; 输入一个递增排序的数组和一个数字S&#xff0c;在数组中查找两个数&#xff0c;是的他们的和正好是S&#xff0c;如果有多对数字的和等于S&#xff0c;输出两个数的乘积最小的思路&#xff1a;数列满足递增&#xff0c;设两个头尾两个指针i和j&#xff0c; 若…

python剑指offer 链表中环的入口节点

题目&#xff1a; 一个链表中包含环&#xff0c;请找出该链表的环的入口结点。思路&#xff1a;//先说个定理&#xff1a;两个指针一个fast、一个slow同时从一个链表的头部出发//fast一次走2步&#xff0c;slow一次走一步&#xff0c;如果该链表有环&#xff0c;两个指针必然在…

python剑指offer系列二叉搜索树的第k个结点

题目&#xff1a; 给定一颗二叉搜索树&#xff0c;请找出其中的第k大的结点。例如&#xff0c; 5 / \ 3 7 /\ /\ 24 6 8 中&#xff0c;按结点数值大小顺序第三个结点的值为4。思路&#xff1a;中序遍历的二叉搜索树就是排序的代码&#xff1a; # -*- coding:utf-8 -*- # class…

Spring MVC FreeMarker模板引擎与动态页面静态化全解

目录 一、FreeMarker简介二、第一个FreeMark示例 2.1、新建一个Maven项目2.2、添加依赖2.3、添加存放模板的文件夹 2.4、添加模板2.5、解析模板2.6、运行结果三、动态页面静态化 3.1、动态页面静态化的优点3.2、动态页面静态化的问题3.3、实现动态页面静态化 3.3.1、新建一个基…

python剑指offer字符串的排列

题目&#xff1a; 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。思路&#xff1a;回溯法代码&#xff1a;class Solution:def __init__(self):self.result[]def Permutat…

python剑指offer连续子数组的最大和

题目&#xff1a;HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢…

一张图帮你弄懂text-cnn

1、何为textcnn 利用卷积神经网络对文本进行分类的算法,那如何用卷积神经网络对文本进行分类呢。这里就tensorflow版本的textcnn源码分析一波。要知道&#xff0c;对文本向量化之后一般是一个一维向量来代表这个文本&#xff0c;但是卷积神经网络一般是对图像进行处理的&#x…

全面探索 FreeMarker 模版引擎的扩展性

FreeMarker 模版引擎简介 FreeMarker 是一个采用 Java 开发的模版引擎&#xff0c;是一个基于模版生成文本的通用工具。 FreeMarker 被设计用来生成 HTML Web 页面&#xff0c;特别是基于 MVC 模式的应用程序。虽然 FreeMarker 具有一些编程的能力&#xff0c;但通常由 Java 程…