求A的奇偶最长子序列。使用python

Question

给定一个大小为N的整数数组A。求A的奇偶最长子序列

在下列情况下，子序列称为奇偶：

子序列的第一个元素是奇数，第二个元素是偶数，第三个元素是奇数，依此类推。例如：[5,10,5,2,1,4]，[1,2,3,4,5]

子序列的第一个元素是偶数，第二个元素是奇数，第三个元素是偶数，依此类推。例如：[10,5,2,1,4,7]，[10,1,2,3,4]

返回奇偶子序列的最大可能长度

注意：如果可以通过删除几个（可能是零个或全部）元素从a中获得B，则数组B是数组a的子序列

代码如下

def solve(A):
    n = len(A)
    sln =[]
    for i in range(n):
        for j in range(i):
            if A[i]%2 == 0:
                if A[j]%2==1 and A[j] < A[i]:
                    sln[i] = max(sln[i],sln[j]+1 )

            else:
                if A[j]%2==1 and A[j] < A[i]:
                    max(sln[i],sln[j]+1 )
    return sln
A = [1, 2, 2, 5, 6]
solve(A)

我得到了索引错误----> sln[i] = max(sln[i],sln[j]+1 )为什么索引错误会出现j每次都比我小

Answer 1

您正在为尚未有值的列表的索引赋值：

    sln =[]
# ...
                    sln[i] = max(sln[i],sln[j]+1 )

您可以在找到新的匹配项时附加到解决方案

不过，这里有一个更简单的解决方案：

def solve(a):
    if not a:
        return []
    sln = [a[0]]
    for x in a[1:]:
        if x % 2 != sln[-1] % 2:
            sln.append(x)
    return sln


example = [1, 2, 2, 5, 6]
print(solve(example))

第一位确保传递空列表时没有错误。解决方案始终包含第一个元素。如果mod 2的值与解决方案中到目前为止的最后一个元素不同，则将包括所有其他元素

基于同样的想法，一个更简单的解决方案（事实上是一行代码）是这样的，但它有点难读，所以如果简洁本身就是一个目标，那就更好了：

def solve_short(a):
    return [x for n, x in enumerate(a) if not n or x % 2 != a[n-1] % 2]

我没有测量时间，但我希望solve_short()的运行速度也比solve()快——如果考虑到这一点的话

请注意，简短的解决方案利用了这样一个事实，即在原始列表中包含任何与其前一个不具有相同奇偶校验的数字，就可以获得正确的解决方案，即使这没有较长解决方案中的逻辑那么明确

我很好奇，运行了一个测试-长的解决方案实际上比短的解决方案性能更好，但这里有一个在大多数情况下性能更好：

def solve_fast(a):
    return [] if not a else [a[0]] + [x for x, y in zip(a[1:], a) if x % 2 != y % 2]

Answer 2

还有两种方法和基准：

# inspired by Grismar
def solve(a):
    return [x for x, y in zip(a, [.5] + a) if (x + y) % 2]

from itertools import groupby

def solve(a):
    return [next(g) for _, g in groupby(a, 1 .__and__)]

a = random.choices(range(100), k=10**6)的基准时间：

124 ms  124 ms  128 ms  125 ms  127 ms  Grismar1
172 ms  228 ms  291 ms  178 ms  180 ms  Grismar2
102 ms  105 ms  106 ms  102 ms  106 ms  Grismar3
 96 ms   86 ms   89 ms   85 ms   85 ms  dont_talk1
162 ms  179 ms  165 ms  166 ms  165 ms  dont_talk2

基准代码（Try it online!）：

from random import choices
from timeit import repeat
from itertools import groupby

def Grismar1(a):
    if not a:
        return []
    sln = [a[0]]
    for x in a[1:]:
        if x % 2 != sln[-1] % 2:
            sln.append(x)
    return sln

def Grismar2(a):
    return [x for n, x in enumerate(a) if not n or x % 2 != a[n-1] % 2]

def Grismar3(a):
    return [] if not a else [a[0]] + [x for x, y in zip(a[1:], a) if x % 2 != y % 2]

def dont_talk1(a):
    return [x for x, y in zip(a, [.5] + a) if (x + y) % 2]

def dont_talk2(a):
    return [next(g) for _, g in groupby(a, 1 .__and__)]

solvers = Grismar1, Grismar2, Grismar3, dont_talk1, dont_talk2

# correctness (somewhat... only checks lengths)
for length in range(20):
    for _ in range(10):
        a = choices(range(100), k=length)
        expect = solvers[0](a[:])
        for solver in solvers:
            result = solver(a[:])
            assert len(result) == len(expect)

for _ in range(3):
    a = choices(range(100), k=10**6)
    for solver in solvers:
        copies = iter([a[:] for _ in range(5)])
        times = repeat(lambda: solver(next(copies)), number=1)
        print(*('%3d ms ' % (t * 1e3) for t in times), solver.__name__)
    print()