java codility Frog 河一号

Question

我一直在尝试解决 Codility 网页上的 Java 练习。

下面是上述练习和我的解决方案的链接。

https://codility.com/demo/results/demoH5GMV3-PV8

任何人都可以告诉我可以在我的代码中更正哪些内容以提高分数吗？

以防万一这里是任务描述:

一只小 Frog 想要到达河的对岸。 Frog 目前位于位置 0，想要到达位置 X。树叶从树上落到河面上。

给定一个非空的零索引数组 A，它由 N 个表示落叶的整数组成。 A[K]表示一片叶子在时间K落下的位置，以分钟为单位。

目标是找出 Frog 最早能跳到河对岸的时间。只有当从 1 到 X 过河的每个位置都出现树叶时， Frog 才能过河。

例如，给定整数 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号位，这是河对岸各个位置出现树叶最早的时间。

写一个函数:

class Solution { public int solution(int X, int[] A); } 

给定一个由 N 个整数和整数 X 组成的非空零索引数组 A，返回 Frog 可以跳到河对岸的最早时间。

如果 Frog 永远无法跳到河的另一边，函数应该返回-1。

例如，给定 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，如上所述。假设:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

复杂度:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素。

这是我的解决方案:

import java.util.ArrayList;
import java.util.List;

class Solution {

    public int solution(int X, int[] A) {
        int list[] = A;
        int sum = 0;
        int searchedValue = X;

        List<Integer> arrayList = new ArrayList<Integer>();

        for (int iii = 0; iii < list.length; iii++) {

            if (list[iii] <= searchedValue && !arrayList.contains(list[iii])) {
                sum += list[iii];
                arrayList.add(list[iii]);
            }
            if (list[iii] == searchedValue) {
                if (sum == searchedValue * (searchedValue + 1) / 2) {
                    return iii;
                }
            }
        }
        return -1;
    }
}

Answer 1

您在循环中使用 arrayList.contains，这将不必要地遍历整个列表。

这是我的解决方案(我前一段时间写的，但我相信它的分数是 100/100):

    public int frog(int X, int[] A) {
        int steps = X;
        boolean[] bitmap = new boolean[steps+1];
        for(int i = 0; i < A.length; i++){
            if(!bitmap[A[i]]){
                bitmap[A[i]] = true;
                steps--;
                if(steps == 0) return i;
            }

        }
        return -1;
    }