我一直在尝试解决Codility网页上的Java练习。
以下是上述练习和我的解决方案的链接。
https://codility.com/demo/results/demoH5GMV3-PV8
谁能告诉我我可以在代码中纠正哪些内容以提高得分？
以防万一，这里是任务说明:
一只小青蛙想去河的另一边。青蛙当前位于位置0，并且想要到达位置X。树叶从树上掉到河面上。
您将获得一个非空的零索引数组A，该数组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;
}
}
最佳答案
您正在循环内使用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;
}