jjzjj

php - 解密系列 - 找到连续整数序列的数量，使得它们的总和为零

coder 2024-04-27 原文

下面是一个编程任务。

给定一个由 N 个整数组成的序列。任务是找到连续整数序列的数量，使得它们的总和为零。

例如，如果序列是: 2, -2, 6, -6, 8 有 3 个这样的序列:

  • '2, -2'
  • '6, -6'
  • '2, -2, 6, -6'

我已经有以下用 PHP 编写的程序，它从 STDIN 读取输入(第一行包含后面的整数个数。)

<?php

$n = fgets(STDIN) * 1;
$seq = array();

for ($i = 0; $i < $n; $i++) {
    $seq[] = fgets( STDIN ) * 1;
}

$count = 0;
for( $i = 0; $i < $n; $i++)
{
    $number = 0;
    for( $j = $i; $j < $n; $j++)
    {
        $number += $seq[$j];
        if( $number == 0 )
            $count++;
    }
}

echo 'count: ' . $count . PHP_EOL;

输入示例

5
2
-2
6
-6
8

这适用于较小的序列，但其效率为 O(n^2)。

对于包含 100.000 个整数的序列，哪种算法是合适的 - 效率可能为 O(n)？

最佳答案

假设您的数据存储在一个数组中，让它成为 arr . 创建数组 sum ，这样:

sum[i] = arr[0] + arr[1] + ... + arr[i]

此外，还有一个以 0 开头的条目(用于处理从开头开始且总和为零的子数组)

现在，很容易看出对于每两个索引 i,j这样 i<j和 sum[i]=sum[j] , 连续序列 arr[i+1]+arr[i+2]+...+arr[j] = 0 .

通过创建这个数组 sum ，您只需要找出那里有多少重复项。这不能在 O(n) 中完成1 (这是 element distinctness problem )，但可以在 O(nlogn) 中解决使用排序然后迭代和计数，这对于 100,000 个条目仍然非常快。

请注意，如果有例如 n重复的数字 k在数组中 sum , 有 Choose(n,2) = n(n-1)/2为这些重复生成的连续子序列。

示例:

arr = [1,2,-2,5,6,-6,-5,8]
sum = [0,1,3,1,6,12,6,1,9]
sorted(sum) = [0,1,1,1,3,6,6,9,12]

1 有 3 个重复，6 有 2 个重复，所以你总共有:

Choose(3,2) + Choose(2,2) = 3*2/2 + 2/2 = 3+1 = 4

确实匹配了4个子序列:

2,-2
2,-2,5,6,-6,-5
6,-6
5,6,-6,-5

(1) 没有散列，然后你会衰减到 O(n^2) 最坏的情况，但会受益于 O(n)平均情况，成本为 O(n)额外的空间。

关于php - 解密系列 - 找到连续整数序列的数量，使得它们的总和为零，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24010804/

使得phpcodesectionprealgorithmperformancesequences

有关php - 解密系列 - 找到连续整数序列的数量，使得它们的总和为零的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  3. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，

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

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

  5. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

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

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

  7. 【鸿蒙应用开发系列】- 获取系统设备信息以及版本API兼容调用方式 - 2

    在应用开发中，有时候我们需要获取系统的设备信息，用于数据上报和行为分析。那在鸿蒙系统中，我们应该怎么去获取设备的系统信息呢，比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况，一种是设备信息的获取，一种是系统信息的获取。1.1、获取设备信息获取设备信息，鸿蒙的SDK包为我们提供了DeviceInfo类，通过该类的一些静态方法，可以获取设备信息，DeviceInfo类的包路径为：ohos.system.DeviceInfo.具体的方法如下：ModifierandTypeMethodDescriptionstatic StringgetAbiList​()Obt

  8. ruby - Ruby 中的单 block AES 解密 - 2

    我需要尝试一些AES片段。我有一些密文c和一个keyk。密文已使用AES-CBC加密，并在前面加上IV。不存在填充，纯文本的长度是16的倍数。所以我这样做:aes=OpenSSL::Cipher::Cipher.new("AES-128-CCB")aes.decryptaes.key=kaes.iv=c[0..15]aes.update(c[16..63])+aes.final它工作得很好。现在我需要手动执行CBC模式，所以我需要单个block的“普通”AES解密。我正在尝试这个:aes=OpenSSL::Cipher::Cipher.new("AES-128-ECB")aes.dec

  9. ruby-on-rails - 在 heroku 的 .fonts 文件夹中包含自定义字体，似乎无法识别它们 - 2

    Heroku支持人员告诉我，为了在我的Web应用程序中使用自定义字体(未安装在系统中，您可以在bash控制台中使用fc-list查看已安装的字体)我必须部署一个包含所有字体的.fonts文件夹里面的字体。问题是我不知道该怎么做。我的意思是，我不知道文件名是否必须遵循heroku的任何特殊模式，或者我必须在我的代码中做一些事情来考虑这种字体，或者如果我将它包含在文件夹中它是自动的......事实是，我尝试以不同的方式更改字体的文件名，但根本没有使用该字体。为了提供更多详细信息，我们使用字体的过程是将PDF转换为图像，更具体地说，使用rghostgem。并且最终图像根本不使用自定义字体。在

  10. 阿里云RDS——产品系列概述 - 2

    基础版云数据库RDS的产品系列包括基础版、高可用版、集群版、三节点企业版，本文介绍基础版实例的相关信息。RDS基础版实例也称为单机版实例，只有单个数据库节点，计算与存储分离，性价比超高。说明RDS基础版实例只有一个数据库节点，没有备节点作为热备份，因此当该节点意外宕机或者执行重启实例、变更配置、版本升级等任务时，会出现较长时间的不可用。如果业务对数据库的可用性要求较高，不建议使用基础版实例，可选择其他系列（如高可用版），部分基础版实例也支持升级为高可用版。基础版与高可用版的对比拓扑图如下所示。优势 性能由于不提供备节点，主节点不会因为实时的数据库复制而产生额外的性能开销，因此基础版的性能相对于

随机推荐