爪哇鳕鱼青蛙-河-一

algorithm java

2022-09-03 16:18:22

我一直在尝试解决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;
    }
}

答案 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;
    }

答案 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]);
}