无法理解解决方案[FrogRiverOne]背后的逻辑

Question

我无法理解这里https://codility.com/demo/take-sample-test/frog_river_one的可变性解决方案背后的逻辑

任务描述

一只小青蛙想去河的另一边。青蛙最初位于河的一边（位置0），想要到达对岸（位置X+1）。树叶从树上掉到河面上。在

给你一个数组A，由代表落叶的N个整数组成。A[K]表示在时间K时一片叶子掉落的位置，以秒为单位。在

我们的目标是找到青蛙跳到河对岸的最早时间。青蛙只有在河流从1到X的每一个位置都出现树叶时才可以交叉（也就是说，我们要找到从1到X所有位置都被树叶覆盖的最早时刻）。你可以假设河流中的水流速度很小，也就是说，树叶一旦掉进河里就不会改变它们的位置。在

例如，给定整数X=5和数组A，以便：

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

在第二个6，一片叶子落在第5位。这是河对岸每一处都出现树叶的最早时期。在

编写函数：

def溶液（X，A）

如果给定一个由N个整数和整数X组成的非空数组a，则返回青蛙跳到河对岸的最早时间。在

如果青蛙永远不能跳到河的另一边，函数应该返回-1。在

例如，给定X=5和数组A，使得：

^{pr2}$

函数应该返回6，如上所述。在

假设：

N和X是范围[1]内的整数。十万] 数组A的每个元素都是范围（1）内的整数。十） 一。 复杂性：

期望的最坏情况时间复杂度为O（N）； 预期的最坏情况空间复杂性为O（X）（不包括输入参数所需的存储空间）。在

---

解决方案--

Input arguments to Function - (2,[2,2,2,2,2]) and (5, [1, 3, 1, 4, 2, 3, 5, 4])

def solution(X,A):

    covered = 0
    covered_a = [-1]*X

    for index,element in enumerate(A):
        if covered_a[element-1] == -1:

            covered_a[element-1] = element
            covered += 1
            if covered == X:
                return index
    return -1

我想了解创建一个布尔数组并从输入数组A中减去1个元素背后的逻辑是什么

Answer 1

这是因为你想“标记”到目前为止看到的所有数字。因为你还没有看到他们中的任何一个。在

Answer 2

我将给你我的Java解决方案，这个问题得分100%。主要策略是使用java.util.Set来存储完整跳转所需的所有整数，并使用第二个java.util.Set来保存当前的叶，并继续检查第一个集合是否完全存在于第二个集合中。在

package com.codility.lesson04.countingelements;

import java.util.HashSet;
import java.util.Set;

public class FrogRiverOne {
  public int solution(int X, int[] A) {
    SetrequiredLeavesSet = new HashSet();
    for(int i=1; i<=X; i++) {
      requiredLeavesSet.add(i);
    }

    SetcurrentLeavesSet = new HashSet();

    for(int p=0; p<A.length; p++) {
      currentLeavesSet.add(A[p]);
      //keep adding to current leaves set until it is at least the same size as required leaves set
      if(currentLeavesSet.size() < requiredLeavesSet.size()) continue;

      if(currentLeavesSet.containsAll(requiredLeavesSet)) {
        return p;
      }
    }
    return -1;
  }
}

您可以找到这个问题的代码和单元测试here，以及对策略here的解释的编码解决方案的完整列表。在