java codility Frog-River-One

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

您正在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;
    }

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

更好的方法是使用Set，因为它只会向列表添加唯一值。只需向 中添加值，并在每次添加新值时Set递减（如果添加了值则返回，否则返回）；看一看，XSet#add()truefalse

public static int solution(int X, int[] A) {
    Set<Integer> values = new HashSet<Integer>();
    for (int i = 0; i < A.length; i++) {
        if (values.add(A[i])) X--; 
        if (X == 0) return i;
    }
    return -1;
}

不要忘记导入，

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

Answer 4

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 5

使用集合(集合框架)的Java解决方案得到100%

import java.util.Set;
import java.util.TreeSet;
public class Froggy {
    public static int solution(int X, int[] A){
    int steps=-1;
    Set<Integer> values = new TreeSet<Integer>();
    for(int i=0; i<A.length;i++){
        if(A[i]<=X){
            values.add(A[i]);
        }
        if(values.size()==X){
            steps=i;
            break;
        }
    }
        return steps;
    }

Answer 6

这是我的解决方案，得分为 100/100：

import java.util.HashSet;

class Solution {
    public int solution(int X, int[] A) {
        HashSet<Integer> hset = new HashSet<Integer>();

        for (int i = 0 ; i < A.length; i++) {
            if (A[i] <= X)
               hset.add(A[i]);   
            if (hset.size() == X)
               return i;
        }

        return -1;
    }
}

Answer 7

简单的解决方案 100%

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

Set<Integer> emptyPosition = new HashSet<Integer>();

for (int i = 1; i <= X; i++) {
  emptyPosition.add(i);
}
// Once all the numbers are covered for position, that would be the
// moment when the frog will jump
for (int i = 0; i < A.length; i++) {
  emptyPosition.remove(A[i]);
  if (emptyPosition.size() == 0) {
    return i;
  }
}
return -1;
}