草庐IT

c++ - 递增序列 C++

coder 2024-02-22 原文

我尝试在 CodeFights 上解决这个挑战，但没有成功。我最好的解决方案得到了 25/26(上次测试超过了时间限制)但我删除了它，因为我昨天试过了(它是 O(n^2))。现在我在 O(n) 中尝试了一个新的。我很累，我今天很想完成这个，所以请帮助我。

声明如下: 给定一个整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。

例子

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

这是我到目前为止的代码...(糟糕的代码):

#include <iostream>
#include <vector>

#include <algorithm>

bool almostIncreasingSequence(std::vector<int> sequence) 
{
    int count = 0;


    for(int i = 0; i < sequence.size()-1; i++)
    {
        if(sequence[i] > sequence[i+1])
        {
            count++;
            sequence.erase(sequence.begin(), sequence.begin() + i);
            i--;
        }
        if(count == 2)
            return false;
    }
    return true;
}

int main()
{
    std::cout << std::endl;
    return 0;
}

最佳答案

这是一个运行时复杂度为 O(N) 的 C++11 解决方案:

constexpr auto Max = std::numeric_limits<std::size_t>::max();
bool is_sorted_but_skip(const std::vector<int>& vec, std::size_t index = Max){
    auto Start = index == 0 ? 1 : 0;
    auto prev = vec[Start];
    for(std::size_t i = Start + 1; i < vec.size(); i++){
        if(i == index) continue;
        if(prev >= vec[i]) return false;
        prev = vec[i];
    }
    return true;
}

bool almostIncreasingSequence(std::vector<int> v) 
{
    auto iter = std::adjacent_find(v.begin(), v.end(), [](int L, int R){ return L >= R; });
    if(is_sorted_but_skip(v, std::distance(v.begin(), iter)))
        return true;
    return is_sorted_but_skip(v, std::distance(v.begin(), std::next(iter)));
}

我们使用 std::adjacent_find查找第一个元素，iter 大于或等于它的下一个元素。然后我们在跳过 iter 的位置时检查序列是否严格排序。

否则，我们会在跳过 iter+1 的位置时检查序列是否严格排序

最坏情况复杂度:3 线性扫描

Demo

关于c++ - 递增序列 C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42635356/

amp43sequencecodesectionc++c++11

有关c++ - 递增序列 C++的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

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

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

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  6. 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

  7. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  8. 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命令使用我的“虚拟

  9. ruby - 如何用递增的值填充数组 Ruby - 2

    我正在尝试解决http://projecteuler.net/problem=1.我想创建一个方法，它接受一个整数，然后创建一个包含它前面的所有整数的数组，并将整数本身作为数组中的值。以下是我目前所拥有的。代码不起作用。defmake_array(num)numbers=Array.newnumcount=1numbers.eachdo|number|numbers 最佳答案 (1..num).to_a是您在Ruby中需要做的全部。1..num将创建一个Range对象，以1开始并以任意值num结束是。Range对象有to_a方法通过

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐