- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
谁能告诉我为什么这段代码不产生每个递增的子序列?我使用动态编程来解决这个问题,但我不明白为什么这段代码会失败。参数 A
是一个整数序列。
def LIS(A):
# make a list of lists
L = list()
for i in range(0, len(A)):
L.append(list())
#the first increasing subsequence is the first element in A
L[0].append(A[0])
for i in range(1, len(A)):
for j in (0, i):
# a new larger increasing subsequence found
if (A[j] < A[i]) and ( len(L[i]) < len(L[j]) ):
L[i] = L[j]
L[i].append(A[i])
# print an increasing subsequence
print L[i]
此算法为 A = [3, 5, 10, 0, 1, 100, 2, 4, 7] 生成的示例输出:
[3, 5]
[3, 5, 10]
[0]
[1]
[3, 5, 10, 100]
[2]
[3, 5, 10, 100, 4]
[3, 5, 10, 100, 4, 7]
None
正确的输出:
[3]
[3, 5]
[3, 5, 10]
[0]
[0, 1]
[3, 5, 10, 100]
[0, 1, 2]
[0, 1, 2, 4]
[0, 1, 2, 4, 7]
最佳答案
我在你的代码中发现了两个错误
1.你假设列表是不可变的,但它们不在 python 中
L[i] = L[j] this is going to make L[i] point to the same list pointed by L[j]
2.for j in (0, i):
这不会将 j 从 0 迭代到 i-1,而是将 j 从 0 迭代到 i。
这是您的代码的固定版本。
def LIS(A):
# make a list of lists
L = list()
for i in range(0, len(A)):
L.append(list())
# the first increasing subsequence is the first element in A
L[0].append(A[0])
for i in range(1, len(A)):
for j in range(0, i):
# a new larger increasing subsequence found
if (A[j] < A[i]) and (len(L[i]) < len(L[j])):
'throw the previous list'
L[i] = []
'add all elements of L[j] to L[i]'
L[i].extend(L[j])
L[i].append(A[i])
for i in range(len(A)):
# print an increasing subsequence
print (L[i])
A = [3, 5, 10, 0, 1, 100, 2, 4, 7]
LIS(A)
关于python - 在Python中获取最长的递增子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27324717/
我正在尝试编写一个名为 map-longest 的 Clojure 实用函数(感谢备用名称建议)。该函数将具有以下“签名”: (map-longest fun missing-value-seq c1
为什么我创建了一个重复的线程 我在阅读后创建了这个线程 Longest increasing subsequence with K exceptions allowed .我意识到提出问题的人并没有真
我正在编写一个 Sub 来识别 1 到 1000 之间最长的 Collatzs 序列。由于我刚刚开始学习 VBA,我想知道如何添加过程来计算每个序列的长度。 Sub Collatz() Dim i
我正在编写一个 Sub 来识别 1 到 1000 之间最长的 Collatzs 序列。由于我刚刚开始学习 VBA,我想知道如何添加过程来计算每个序列的长度。 Sub Collatz() Dim i
我正在尝试减去 CSV 中的两列以创建第三列“持续时间”结束时间 - 开始时间 每一行也对应一个用户 ID。 我可以创建一个仅包含“持续时间”列的 csv 文件,但我宁愿将其重定向回原始 csv。 例
我在 2018.04 玩这个最长的 token 匹配,但我认为最长的 token 不匹配: say 'aaaaaaaaa' ~~ m/ | a+? | a+ /; # 「a」
因此,按照规范规定最终用户/应用程序提供的给定变量(200 字节)的字节长度。 使用 python 字符串,字符串的最大字符长度是多少,满足 200 字节,因此我可以指定我的数据库字段的 max_le
我需要针对我们的Jenkins构建集群生成每周报告。报告之一是显示具有最长构建时间的作业列表。 我能想到的解决方案是解析每个从属服务器(也是主服务器)上的“构建历史”页面,对于作业的每个构建,都解析该
我正在构建一个 iOS 应用程序,它将流式传输最长为 15 秒的视频。我阅读了有关 HLS 的好文章,因此我一直在对片段大小为 5 秒的视频进行转码。如果视频的第一部分加载时间太长,那么我们可以在接下
docs for Perl 6 longest alternation in regexes punt to Synopsis 5记录 longest token matching 的规则.如果不同的
我是一名优秀的程序员,十分优秀!