3

我正在尝试解决 Codility 的Min Avg Two Slice问题。

我想出了以下代码：

def solution(S, P, Q):
    weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    retVal = []
    for i in range(0, len(P)): 
        if P[i] == Q[i]: 
            retVal.append(weights[S[P[i]]])
        else: 
            retVal.append(local_min(S, weights, P[i], Q[i]))
    return retVal

minimums = {}
def local_min(S, weights, start, end):
    minVal = weights[S[start]]
    for i in range(start,end+1):
        val = weights[S[i]]
        if val == 1: 
            minimums[i] = 1
            return 1
        if val < minVal: 
            minVal = val
        minimums[i] = minVal
    return minVal

这在正确性方面效果很好，但是它具有时间复杂度，O(n*m)因为我local_min每次都重新计算而不重用任何结果。

我正在尝试使用prefix_sums这里的算法来计算局部最小值，或者以某种方式使用minimums对象记住计算出的最小值，并在随后的调用中重用它们local_min。

我遇到的问题是 - 假设我们有以下数组：

[1, 13, 2, 8, 20, 5]

smallest values seen up to this point我们可以计算如下数组：

对于范围0, 6，它只是：

[1,1,1,1,1,1]

因为1,6它将是：

[13, 2, 2, 2, 2]

对于2,6：

[2, 2, 2, 2]

最后：

[8, 8, 8] 和 [20, 5]

我正在努力了解如何采用这种方法来计算smallest value in a given range并降低我的解决方案的时间复杂度。

编辑：

我想出了以下解决方案，它在正确性和性能方面实现了 100% 的 Codility，并实现了时间复杂度O(n+m)：

def solution(S, P, Q):
    weights = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    retVal = []
    for i in range(0, len(P)): 
        if P[i] == Q[i]: 
            retVal.append(weights[S[P[i]]])
        else: 
            if 'A' in S[P[i]:Q[i] + 1]: 
                retVal.append(1)
            elif 'C' in S[P[i]:Q[i] + 1]: 
                retVal.append(2)
            elif 'G' in S[P[i]:Q[i] + 1]: 
                retVal.append(3)
            else: 
                retVal.append(4)
    return retVal

不过，我仍然对此感到有些困惑-我的假设是该in操作将采用的长度O(n)在哪里，因此总体复杂性应该是长度在哪里-任何人都可以解释为什么实际上是复杂性nSO(n * m)mPQO(n + m)

4

2 回答 2

3

这个问题的难点在于证明有一个简单的解决方案。

特别是，您可以证明您只需要查找长度为 2 或 3 的切片。

证明：假设有一个长度 >=4 的切片具有最小的可能平均值。我们可以将它分成两片——一片由前 2 个元素组成，另一片由其余元素组成。任何部分的平均值都不能小于整体，因为整体的平均值可能最小，因此两个部分的平均值必须与整体相同，因此最初的 2 个元素是从同一位置开始的有效结果。

因此，只需遍历起始位置并测试所有长度为 2 或 3 的切片，并记住第一个具有最小平均值的切片。

于 2021-12-25T03:01:42.687 回答
0

Matt Timmermans提供的一种方法在实现上不太复杂，并且具有更好的时间复杂度。下面的方法更容易提出，但效率较低。

如果我们想更快地解决 RMQ，有这样的选择：

  • 段树（对我来说最好的选择）。O(n)用于建筑，O(log(n))用于最小搜索。使用 Python 开发并不容易。
  • Sqrt 分解。O(n)用于建筑，O(sqrt(n))用于最小搜索。非常容易开发。
  • 芬威克树。O(n)用于建筑，O(log(n))用于最小搜索。非常容易开发，很难理解它是如何工作的。
  • 稀疏表。O(n*log(n))用于建筑，O(1)用于最小搜索。很容易开发。

所有链接都包含实现，其中一些在 Python 中。

于 2021-12-25T02:29:20.357 回答