问题标签 [lis]

给定一个向量

查找所有最长的递增子序列 (LIS)

解决方案应该看起来像

我什至可以使用元素的索引

我使用了JINJING XIE给出的代码，但它只返回一个序列

任何帮助，将不胜感激

问题：

我正在完成第 6 版的《Cracking the Coding Interview》，但遇到了 Circus Tower 问题（编号 17.8）。我有一个我认为在 O(N logN) 时间内运行的解决方案，但本书的解决方案（不同）说 O(N logN) 解决方案非常复杂，但我的代码不是。我需要一些帮助来确定我的解决方案是否正确，以及它是否真的在 O(N logN) 时间内运行。我想了解我为什么错（或对），所以任何细节都会有所帮助。

这是问题文本：

一个马戏团正在设计一个由站在彼此肩上的人组成的塔式程序。出于实用和审美的原因，每个人都必须比他或她下面的人更矮更轻。给定马戏团中每个人的身高和体重，编写一个方法来计算这样一个塔中可能存在的最大人数。

我的解决方案：

以下是一些示例输入以及我的代码返回的内容：

我想从用户那里获取一系列字符串并将其放入列表中，然后打印出来

我也想当我完成时关闭列表并打印它

如果字典列表中存在输入，我正在编写一个 python 代码来更新字典列表。如果字典列表中不存在输入，则应打印“整个列表中不存在值”或执行一些其他操作。下面是我写的代码

这里的问题是，如果输入是“红色”，“无值”会打印两次，而“匹配”会打印一次。

我的用例是如果字典列表中不存在输入，它应该只打印一次“无值”。如果输入存在代码应该用新值更新下一个键并打印一次“匹配”。

我在堆栈溢出中遇到过其他问题。我找不到这种情况的答案。

请帮忙

我正在解决一个关于LIS （最长增加子集）的问题，但我无法完全解决它。我在谷歌上搜索了一些解决方案，在 Rosettacode 上我找到了几个。我喜欢这个，因为它看起来很短很直接（很容易理解）。但是它的编写方式使我在重写它时遇到了严重的麻烦。

这是我难以理解的部分。这是我认为我理解的：

将解决方案数组中最长的数字组合附加到解决方案数组，低于我从输入数组中考虑的当前数字；加上您正在考虑的输入数组中的数字。（对不起我的英语不好）。

我觉得我没有完全理解代码在做什么。

在Jacobson 和 Vo的论文“Heaviest increasing/Common Subsequence Problems”中，我在理解用于计算完整最长递增子序列 (lis) 的节点结构时遇到了问题。

这是论文中的伪代码：

是什么意思

node 是一个辅助数组，对于 L 中的每个元素，它包含一个元素的记录，该元素在递增子序列中位于该元素之前。函数 newnode() 构造这些记录并将它们链接到有向图中。在算法结束时，我们可以从 L 的最大元素中搜索来恢复一个 sigma 的 LIS。

? 你将如何实现这个结构？

我是否必须构建一个以序列的所有元素作为顶点（加上一个零顶点）和边“\sigma_i -> s”的有向图，然后搜索从 L 的最大元素开始的最长路径（并结束为零）？难道没有更有效的方法来获取完整的 lis 吗？

我的第二个问题：这个算法和维基百科中描述的算法一样快吗？如果不是：我可以修改维基百科的算法来计算论文中描述的最重的公共子序列吗？

我们正在为 Mindray BC 3600 开发 LIS。当我们连接到分析仪时，它要求输入“coldfire login:”和密码。但是供应商和服务中心都不知道它是什么。有没有人遇到过这样的问题并解决了？如果有请帮助我们。

为什么我创建了一个重复的线程

在阅读了Longest increase subsequence with K exceptions allowed 之后，我创建了这个线程。我意识到提出这个问题的人并没有真正理解这个问题，因为他指的是一个解决“允许一次更改的最长增加子数组”问题的链接。所以他得到的答案实际上与LIS问题无关。

问题描述

假设给定一个长度为N的数组A。找到允许K个例外的最长递增子序列。

示例
1) N=9 , K=1

A=[3,9,4,5,8,6,1,3,7]

答案：7

解释：

最长递增子序列为：3,4,5,8(或6),1(异常),3,7 -> total=7

2) N=11 , K=2

A=[5,6,4,7,3,9,2,5,1,8,7]

答案：8

到目前为止我所做的...

如果 K=1，则只允许一个例外。如果使用已知的计算O(NlogN)中最长递增子序列的算法（点击这里查看该算法），那么我们可以计算数组每个元素从 A[0] 到 A[N-1] 的 LIS A. 我们将结果保存在一个大小为N的新数组L中。查看示例 n.1，L 数组将是： L=[1,2,2,3,4,4,4,4,5]。

使用逆向逻辑，我们计算数组R，其中每个元素都包含从 N-1 到 0 的当前最长递减序列。

除了一个例外，LIS 就是sol=max(sol,L[i]+R[i+1])， 其中sol被初始化为sol=L[N-1]。所以我们从 0 开始计算 LIS 直到索引i（异常），然后停止并开始一个新的 LIS 直到N-1。

->一步一步的解释：

复杂度： O(NlogN + NlogN + N) = O(NlogN)

因为数组R, L需要 NlogN 时间来计算，我们还需要 Θ(N) 才能找到sol。

k=1 问题的代码

泛化到 K 个异常

我提供了一个 K=1 的算法。我不知道如何更改上述算法以适用于 K 异常。如果有人可以帮助我，我会很高兴。

（PS。如果需要，我可以为 C++ 中的 K=1 算法提供代码。）

我在实现list类的代码中找到了以下代码段

现在我知道，如果我有一个将参数作为 的函数r-value，则该参数将l-value在函数的范围内（不是吗？）。

所以我可以用

第一个问题：我说的对吗？

第二个：考虑到r-value第一个片段中的l-value参数是第二个函数内部的参数，将std::move( x )cast xfrom l-valuetor-value和函数push_front()调用函数的r-value版本insert()还是什么？

编辑::

这是如何insert()实现的

的定义Node

我正在读取文件并在文件内容上使用正则表达式来执行一些操作。在读取文件时，我没有在其中找到任何特殊字符，但是在对文件内容使用正则表达式并将其保存到列表后，数字前有特殊字符，如 \t 和 \xa0。

示例文件内容：

应用正则表达式后变为：

如何在没有单独的字符串替换技术的情况下删除所有这些？

代码：

该newresult列表包含原始文件中不存在的所有这些特殊字符。