Peak和Flag Codility最新的chellange

Question

我正在尝试解决最新的codility.com问题(只是为了提高我的技能).我试过分配,但没有超过30分,所以现在好奇我在解决方案中究竟缺少什么.

问题说

给出了由N个整数组成的非空零索引数组A. 峰值是一个比其邻居更大的数组元素.更确切地说,它是指数P

0 < P < N ? 1 and A[P ? 1] < A[P] > A[P + 1]

例如,以下数组A:

A[0] = 1 
A[1] = 5 
A[2] = 3 
A[3] = 4 
A[4] = 3 
A[5] = 4 
A[6] = 1 
A[7] = 2 
A[8] = 3 
A[9] = 4 
A[10] = 6 
A[11] = 2

恰好有四个峰:元素1,3,5和10.

您将前往一系列相对高度由阵列A表示的山脉.您必须选择应该带多少旗帜.目标是根据某些规则设置峰值上的最大标志数.

标志只能在峰值上设置.更重要的是,如果你取K标志,那么任何两个标志之间的距离应该大于或等于K.指数P和Q之间的距离是绝对值| P-Q |.

例如,给定由上面的数组A表示的山脉,N = 12,如果你采取:

> two flags, you can set them on peaks 1 and 5; 

> three flags, you can set them on peaks 1, 5 and 10; 

> four flags, you can set only three flags, on peaks 1, 5 and 10.

因此,在这种情况下,您最多可以设置三个标志.

编写一个函数,给定N个整数的非空零索引数组A,返回可在数组峰值上设置的最大标志数.例如,给定上面的数组

该函数应返回3,如上所述.

假使,假设:

N是[1..100,000]范围内的整数;

数组A的每个元素是[0..1,000,000,000]范围内的整数.

复杂:

预期的最坏情况时间复杂度是O(N); 预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).

所以我根据我对问题的理解尝试了这段代码

var A = [1,5,3,4,3,4,1,2,3,4,6,2];

function solution(A) {
 array = new Array();  
   for (i = 1; i < A.length - 1; i++) {  
    if (A[i - 1] < A[i] && A[i + 1] < A[i]) {  
     array.push(i);  
    }  
   }  

  //console.log(A);
  //console.log(array);
  var position = array[0];
  var counter = 1;
  var len = array.length;
  for (var i = 0; i < len; i++) {
    if (Math.abs(array[i+1] - position) >= len) {
        position = array[i+1];
        counter ++;
        }
    }

  console.log("total:",counter);
  return counter;

}

上面的代码适用于样本数组元素:[1,5,3,4,3,4,1,2,3,4,6,2] 在索引处获取峰值:[1, 3, 5, 10]并设置标志位于1, 5, and 10 (total 3)

但codility.com表示它在阵列上失败[7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7] 我的代码在索引处获得峰值:[1, 4, 6, 8]并将标志设置为1和6(总共2),但coditity.com称它应该是3个标志.(不知道为什么)我想念 - 理解这个问题吗？

请我只是寻找提示/算法.我知道这个问题已被某人提出并在私人聊天室中解决但在该页面上我试图获得该人的帮助,但成员却将我的帖子标记为不恰当的答案,所以我再次在这里提出问题.

PS:您可以点击挑战自己在www.codility.com上试用您的代码!

Answer 1

缺少 100% PHP 解决方案:)

function solution($A)
{
    $p = array(); // peaks
    for ($i=1; $i<count($A)-1; $i++)
        if ($A[$i] > $A[$i-1] && $A[$i] > $A[$i+1])
            $p[] = $i;

    $n = count($p);
    if ($n <= 2)
        return $n;

    $maxFlags = min(intval(ceil(sqrt(count($A)))), $n); // max number of flags
    $distance = $maxFlags; // required distance between flags
    // try to set max number of flags, then 1 less, etc... (2 flags are already set)
    for ($k = $maxFlags-2; $k > 0; $k--)
    {
        $left = $p[0];
        $right = $p[$n-1];
        $need = $k; // how many more flags we need to set

        for ($i = 1; $i<=$n-2; $i++)
        {
            // found one more flag for $distance
            if ($p[$i]-$left >= $distance && $right-$p[$i] >= $distance)
            {
                if ($need == 1)
                    return $k+2;
                $need--;
                $left = $p[$i];
            }

            if ($right - $p[$i] <= $need * ($distance+1))
                break; // impossible to set $need more flags for $distance
        }

        if ($need == 0)
            return $k+2;

        $distance--;
    }
    return 2;
}

Answer 2

这是一个具有更好的复杂度上限的解决方案：

• 时间复杂度： O(sqrt(N) * log(N))
• 空间复杂度：（O(1)超过原始输入存储）

Python 实现

from math import sqrt

def transform(A):
    peak_pos = len(A)
    last_height = A[-1]
    for p in range(len(A) - 1, 0, -1):
        if (A[p - 1] < A[p] > last_height):
            peak_pos = p
        last_height = A[p]
        A[p] = peak_pos
    A[0] = peak_pos

def can_fit_flags(A, k):
    flag = 1 - k
    for i in range(k):
        # plant the next flag at A[flag + k]
        if flag + k > len(A) - 1:
            return False
        flag = A[flag + k]
    return flag < len(A)  # last flag planted successfully

def solution(A):
    transform(A)
    lower = 0
    upper = int(sqrt(len(A))) + 2
    assert not can_fit_flags(A, k=upper)
    while lower < upper - 1:
        next = (lower + upper) // 2
        if can_fit_flags(A, k=next):
            lower = next
        else:
            upper = next
    return lower

描述

O(N) 预处理（就地完成）：

A[i] := next peak or end position after or at position i
        (i for a peak itself, len(A) after last peak)

如果我们可以插k旗，那么我们当然也可以插k' < k旗。如果我们不能插k旗，那么我们当然也不能插k' > k旗。我们总是可以设置 0 个标志。让我们假设我们不能设置X标志。现在我们可以使用二分搜索来确切地找出可以种植多少个标志。

Steps:
  1. X/2
  2. X/2 +- X/4
  3. X/2 +- X/4 +- X/8
  ...
  log2(X) steps in total

通过之前的预处理，k可以在O(k)操作中进行每一步测试是否可以植入标志：

• 标志（0）=下一个（0）
• 标志(1) = 下一个(标志(1) + k) ...
• 标志(k-1) = 下一个(标志(k-2) + k)

总成本 - 最坏的情况 - 何时X - 1可以插旗：

== X * (1/2 + 3/4 + ... + (2^k - 1)/(2^k))
== X * (log2(X) - 1 + (<1))
<= X *日志（X）

使用X == N会起作用，并且很可能也是次线性的，但不足以用于证明该算法的总上限低于O(N)。

现在一切都取决于找到一个 good X，并且由于k标志需要大约k^2位置来适应，因此似乎应该在 附近的某个地方找到标志数量的一个很好的上限sqrt(N)。

如果X == sqrt(N)或接近它的东西有效，那么我们得到一个O(sqrt(N) * log(sqrt(N)))绝对是次线性的log(sqrt(N)) == 1/2 * log(N)上限，因为该上限等于O(sqrt(N) * log(N))。

让我们寻找周围所需标志数量的更准确的上限sqrt(N)：

• 我们知道k标志需要Nk := k^2 - k + 3标志
• 通过求解方程k^2 - k + 3 - N = 0，k我们发现如果k >= 3，那么任意数量的标志 <= 结果k可以适合某个长度为 N 的序列，而更大的则不能；该方程的解是1/2 * (1 + sqrt(4N - 11))
• 因为N >= 9我们知道我们可以容纳 3 个标志 ==> for N >= 9，k = floor(1/2 * (1 + sqrt(4N - 11))) + 1是我们可以容纳的标志数量的严格上限N
• 因为N < 9我们知道 3 是一个严格的上限，但这些情况与我们寻找大 O 算法复杂度无关

floor(1/2 * (1 + sqrt(4N - 11))) + 1
== floor(1/2 + sqrt(N - 11/4)) + 1
<= floor(sqrt(N - 11/4) ) + 2
<= 楼层(sqrt(N)) + 2

==>floor(sqrt(N)) + 2也是一个不错的严格的上限为一些能够适应的标志N元素+这其中甚至对N < 9因此它可以作为一种通用的严格在我们执行上限以及

如果我们选择，X = floor(sqrt(N)) + 2我们将得到以下总算法上限：

O((floor(sqrt(N)) + 2) * log(floor(sqrt(N)) + 2))
   {floor(...) <= ...}
O((sqrt(N) + 2) * log(sqrt(N) + 2))
   {for large enough N >= 4: sqrt(N) + 2 <= 2 * sqrt(N)}
O(2 * sqrt(N) * log(2 * sqrt(N)))
   {lose the leading constant}
O(sqrt(N) * (log(2) + loq(sqrt(N)))
O(sqrt(N) * log(2) + sqrt(N) * log(sqrt(N)))
   {lose the lower order bound}
O(sqrt(N) * log(sqrt(N)))
   {as noted before, log(sqrt(N)) == 1/2 * log(N)}
O(sqrt(N) * log(N))
                                  QED