草庐IT

javascript - Codility - 最小平均切片

coder 2025-01-01 原文

我正在尝试找到 a codility question on minimum slice of a subarray 的解决方案，并且我使用 Kadane 算法的修改版本设计了一个解决方案。我目前得到了 90/100 并且设法通过了 O(n) 中的几乎所有测试。但是，我似乎无法通过“medium_range，增加，减少(legth = ~100)和小功能，得到 5 expected 3”，我不知道为什么。这可能是 solution 的重复，但我使用了一种稍微不同的解决方法。

我的逻辑是这样的:

a) 如果我们有一个数组 MinA，其中 MinA[k] 表示从 k 开始的最小长度为 2 的子数组的最小平均切片

b) 然后如果我们遍历 MinA 并找到数组的最小值，那么这将是整个数组的最小平均切片(然后返回索引位置)

c) 要创建这个 MinA，我们从数组的倒数第二个元素开始，MinA[A.length -2] 是 A 的最后两个元素的平均值

d) 我们将计数器向左移动一个位置； MinA[counter] 必须是 A[counter] 和 A[counter + 1] 的平均值，或者是元素 counter 和 MinA[counter + 1] 中元素的平均值

e) 如果 d 不为真，则这意味着 MinA[counter + 1] 不是从 counter + 1 到从 counter + 2 到 N 的某个元素的最小平均切片

我想知道我是否遗漏了什么？

/*
 * Using modified version of Kadane's algorithm
 * The key logic is that for an array A of length N, 
 * if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
 * between k+2 to n, then M[k] is either the average of A[k] and A[k + 1], or
 * the average of the elements k and the elements in M[k + 1]
 */
function solution(A) {
    // you can use console.log for debugging purposes, i.e.
    // console.log('this is debug message');
    // write your code in JavaScript (ECMA-262, 5th edition)
    var minSliceArray = [],
        counter = A.length - 2,
        currMinSliceLength = 0,
        min = Number.POSITIVE_INFINITY,
        minIndex = -1;

    minSliceArray[counter] = (A[counter] + A[counter + 1]) / 2;
    currMinSliceLength = 2;
    counter--;

    while (counter >= 0) {
        var a = (A[counter] + A[counter + 1]) / 2,
            b = (A[counter] + minSliceArray[counter + 1] * currMinSliceLength) / (currMinSliceLength + 1) ;
        if (a < b) {
            minSliceArray[counter] = a;
            currMinSliceLength = 2;
        } else {
            minSliceArray[counter] = b;
            currMinSliceLength++;
        }
        counter--;
    }

    //loops through the minSliceArray and find the minimum slice
    for (var i = 0; i < minSliceArray.length; i++) {
        if (minSliceArray[i] < min) {
            min = minSliceArray[i];
            minIndex = i;
        }
    }
    return minIndex;
}

最佳答案

要解决您的问题，您可以替换代码

if (a < b) {

与

if (a <= b) {

例如A = [-3, 3, -3, 3, -3]，首先我们考虑的是A[3:5]，平均值为0。然后，我们来到位置2，A [2:5]/3 = -1，A[2:4]/2 = 0。所以我们选择前者。对于位置1，A[1:3]/2 == A[1:5]/4 == 0。在OLD答案中，我们应该继续选择A[1:5]。最后对于位置 0，我们有 A[0:2]/2 = 0，并且 A[0:5]/5 = -0.6 我们选择后者。毕竟，总体最小平均值位于位置 3，因为 A[3:5]/3=-1。 但是实际上是 A[0:3]/3 == -1 == A[3:5]/3。

因为这样的陷阱，我在博客中没有使用Kadane算法的修改版本。但它应该运作良好。

关于javascript - Codility - 最小平均切片，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22137951/

javascriptCodilitycounterminSliceArraycurrMinSliceLengthalgorithmdynamic-programmingkadanes-algorithm

有关javascript - Codility - 最小平均切片的更多相关文章

  1. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  2. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  3. ruby-on-rails - Ruby on Rails 将列表拆分或切片为列 - 2

    @locations=Location.all#currentlistingall@locations=Location.slice(5)orLocation.split(5)使用Ruby，我试图将我的列表分成4列，每列限制为5个；然而，切片或拆分似乎都不起作用。知道我可能做错了什么吗？任何帮助是极大的赞赏。 最佳答案 您可能想使用in_groups_of:http://railscasts.com/episodes/28-in-groups-of这是RyanBates在railscast中的示例用法:

  4. ruby - 在 Mechanize 中使用 JavaScript 单击链接 - 2

    我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan

  5. javascript - jQuery 的 jquery-1.10.2.min.map 正在触发 404(未找到) - 2

    我看到有关未找到文件min.map的错误消息:GETjQuery'sjquery-1.10.2.min.mapistriggeringa404(NotFound)截图这是从哪里来的？ 最佳答案 如果ChromeDevTools报告.map文件的404(可能是jquery-1.10.2.min.map、jquery.min.map或jquery-2.0.3.min.map，但任何事情都可能发生)首先要知道的是，这仅在使用DevTools时才会请求。您的用户不会遇到此404。现在您可以修复此问题或禁用sourcemap功能。修复:获取文

  6. ruby - 返回空白页的最小 Capybara/Poltergeist 测试 - 2

    看来我正在回顾SO帖子中采取的步骤:Capybara,PoltergeistandPhantomjsandgivinganemptyresponseinbody.(如果你愿意，可以将其标记为重复，但我包含了一个最小的独立测试用例和版本号。)问题我做错了什么吗？我可以运行另一个可能有助于隔离问题的最小测试吗？文件:pgtest.rbrequire'rubygems'require'capybara'require'capybara/dsl'require'capybara/poltergeist'modulePGTestincludeCapybara::DSLextendselfdeft

  7. ruby-on-rails - 我将 Rails3 与 tinymce 一起使用。如何呈现用户关闭浏览器javascript然后输入xss？ - 2

    我有一个用Rails3编写的站点。我的帖子模型有一个名为“内容”的文本列。在帖子面板中，html表单使用tinymce将“content”列设置为textarea字段。在首页，因为使用了tinymce，post.html.erb的代码需要用这样的原始方法来实现。.好的，现在如果我关闭浏览器javascript，这个文本区域可以在没有tinymce的情况下输入，也许用户会输入任何xss，比如alert('xss');.我的前台会显示那个警告框。我尝试sanitize(@post.content)在posts_controller中，但sanitize方法将相互过滤tinymce样式。例如

  8. ruby - 使用 Selenium WebDriver 启用/禁用 javascript - 2

    出于某种原因，我必须为Firefox禁用javascript(手动，我们按照提到的步骤执行http://support.mozilla.org/en-US/kb/javascript-settings-for-interactive-web-pages#w_enabling-and-disabling-javascript)。使用Ruby的SeleniumWebDriver如何实现这一点？ 最佳答案 是的，这是可能的。而是另一种方式。您首先需要查看链接Selenium::WebDriver::Firefox::Profile#[]=

  9. ruby - Watir-Webdriver 是否支持点击目标为 javascript 的链接？ - 2

    我是Ruby和Watir-Webdriver的新手。我有一套用VBScript编写的站点自动化程序，我想将其转换为Ruby/Watir，因为我现在必须支持Firefox。我发现我真的很喜欢Ruby，而且我正在研究Watir，但我已经花了一周时间试图让Webdriver显示我的登录屏幕。该站点以带有“我同意”区域的“警告屏幕”开头。用户点击我同意并显示登录屏幕。我需要单击该区域以显示登录屏幕(这是同一页面，实际上是一个表单，只是隐藏了)。我整天都在用VBScript这样做:objExplorer.Document.GetElementsByTagName("area")(0).click

  10. 网页设计期末作业，基于HTML+CSS+JavaScript超酷超炫的汽车类企业网站(6页) - 2

    🎉精彩专栏推荐💭文末获取联系✍️作者简介:一个热爱把逻辑思维转变为代码的技术博主💂作者主页:【主页——🚀获取更多优质源码】🎓web前端期末大作业：【📚毕设项目精品实战案例(1000套)】🧡程序员有趣的告白方式：【💌HTML七夕情人节表白网页制作(110套)】🌎超炫酷的Echarts大屏可视化源码：【🔰Echarts大屏展示大数据平台可视化(150套)】🔖HTML+CSS+JS实例代码：【🗂️5000套HTML+CSS+JS实例代码(炫酷代码)继续更新中…】🎁免费且实用的WEB前端学习指南：【📂web前端零基础到高级学习视频教程120G干货分享】🥇关于作者:💬历任研发工程师，技术组长，教学总监；

随机推荐