爪哇codility青蛙河-一

Question

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

下面是提到的练习和我的解决方案的链接。

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

有人能告诉我为了提高分数，我的代码中可以纠正什么吗？

以下是任务描述，以防万一：

一只小青蛙想去河的另一边。青蛙目前位于位置0，想要到达位置X。树叶从树上掉落到河面上。

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

目标是找到青蛙能跳到河对岸的最早时间。只有当树叶出现在从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位。这是最早的树叶出现在河对岸的每个位置。

写一个函数：

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

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

如果青蛙永远无法跳到河的另一边，函数应该返回−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

100/100

public static int solution (int X, int[] A){

    int[]counter = new int[X+1];
    int ans = -1;
    int x = 0;

    for (int i=0; i<A.length; i++){
        if (counter[A[i]] == 0){
            counter[A[i]] = A[i];
            x += 1;
            if (x == X){
                return i;
            }
        } 
    }

    return ans;
}

Answer 2

这是我的解决方案。它给了我100/100:

public int solution(int X, int[] A)
{
     int[] B = A.Distinct().ToArray();
     return (B.Length != X) ? -1 : Array.IndexOf<int>(A, B[B.Length - 1]);
}

Answer 3

您正在循环中使用< code>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;
    }