草庐IT

每日算法之和为S的连续正数序列

loongnuts 2023-04-16 原文

JZ74 和为S的连续正数序列

题目

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

方法1 枚举法

思路

算法实现

从数字1开始枚举连续的数字，将其累加判断其是否等于目标，
如果小于目标数则继续往后累加，
如果大于目标数说明会超过，跳出，
继续枚举下一个数字开始的情况（比如2，比如3），
这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。

具体做法：
    step 1：从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
    step 2：从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
    step 3：如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。

代码

package mid.JZ74和为S的连续正数序列;

import java.util.ArrayList;

public class Solution {
    /**
     * 枚举法
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (sum == 0) return new ArrayList<>();
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int sum1 = 0;
        int mid = (sum - 1) / 2;
        for (int i = 1; i <= mid; i++) {
            for (int j = i; ; j++) {
                sum1 += j;
                if (sum1 > sum) {
                    sum1 = 0;
                    break;
                } else if (sum1 == sum) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    for (int k = i; k <= j; k++)
                        temp.add(k);
                    res.add(temp);
                    sum1 = 0;
                    break;
                }
            }
        }
        return res;
    }
}

方法2 滑动窗口（推荐使用）

思路

算法实现

从某一个数字开始的连续序列和等于目标数如果有，只能有一个，于是我们可以用这个性质来使区间滑动。

两个指针l、r指向区间首和区间尾，公式(l+r)∗(r−l+1)/2计算区间内部的序列和，
如果这个和刚好等于目标数，说明以该区间首开始的序列找到了，记录下区间内的序列，同时以左边开始的起点就没有序列了，于是左区间收缩；
如果区间和大于目标数，说明该区间过长需要收缩，只能收缩左边；
如果该区间和小于目标数，说明该区间过短需要扩大，只能向右扩大，移动区间尾。

具体做法：
    step 1：从区间[1,2][1,2][1,2]开始找连续子序列。
    step 2：每次用公式计算区间内的和，若是等于目标数，则记录下该区间的所有数字，为一种序列，同时左区间指针向右。
    step 3：若是区间内的序列和小于目标数，只能右区间扩展，若是区间内的序列和大于目标数，只能左区间收缩。

代码

package mid.JZ74和为S的连续正数序列;

import java.util.ArrayList;

public class Solution {
    /**
     * 滑动窗口（推荐使用）
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int l = 1, r = 2; l < r; ) {
            int sum1 = (l + r) * (r - l + 1) / 2;
            if (sum1 == sum) {
                ArrayList<Integer> temp = new ArrayList<>();
                for (int i = l; i <= r; i++) {
                    temp.add(i);
                }
                res.add(temp);
                l++;
            } else if(sum1 < sum) {
                r++;
            } else {
                l++;
            }
        }
        return res;
    }
}
之和每日ArrayListsum该区Java

有关每日算法之和为S的连续正数序列的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. ruby - 在 Ruby 中比较序列 - 2

    假设我必须(小型到中型)阵列:tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]如何确定tokens是否以相同的顺序包含template的所有条目？(请注意，在上面的示例中，应忽略第一个“ccc”，从而由于最后一个“ccc”而导致匹配。) 最佳答案 这适用于您的示例数据。tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]po

  5. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  6. ruby - 如何用 Nokogiri 解析连续的标签？ - 2

    我有这样的HTML代码:Label1Value1Label2Value2...我的代码不起作用。doc.css("first").eachdo|item|label=item.css("dt")value=item.css("dd")end显示所有首先标记，然后标记标签，我需要“标签:值” 最佳答案 首先，您的HTML应该有和中的元素:Label1Value1Label2Value2...但这不会改变您解析它的方式。你想找到s并遍历它们，然后在每个你可以使用next_element得到;像这样:doc=Nokogiri::HTML(

  7. ruby - 我可以从 Ruby 中的系统调用中获得连续输出吗？ - 2

    当您在Ruby脚本中使用系统调用时，您可以像这样获得该命令的输出:output=`ls`putsoutput这就是thisquestion是关于。但是有没有办法显示系统调用的连续输出？例如，如果您运行此安全复制命令，以通过SSH从服务器获取文件:scpuser@someserver:remoteFile/some/local/folder/...它显示随着下载进度的连续输出。但是这个:output=`scpuser@someserver:remoteFile/some/local/folder/`putsoutput...不捕获该输出。如何从我的Ruby脚本中显示正在进行的下载进度？

  8. ruby - 获取数组中值的最大连续出现次数 - 2

    下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案 类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max

  9. arrays - 检查连续数字 - 2

    我有一个整数数组m。我正在寻找一种方法来检查m的元素是否连续。有没有办法测试连续数字？我想出了这段代码，旨在在数组长度为四时工作:m.count==4&&(m.max-m.min)==3对于[1,1,1,4]或[0,0,0,3]错误地返回true。 最佳答案 Enumerable有一个非常方便的方法叫做each_cons是这样工作的:[1,2,3,4].each_cons(2).to_a#=>[[1,2],[2,3],[3,4]]也就是说，它会生成每组连续的n元素。在我们的例子中，n是2。当然，顾名思义，它返回一个Enumerato

  10. 机器学习——时间序列ARIMA模型(四)：自相关函数ACF和偏自相关函数PACF用于判断ARIMA模型中p、q参数取值 - 2

    文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk​=Var(yt​)Cov(yt​,yt−k​)​其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞

随机推荐