java codility Frog-River-One
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19459197/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
java codility Frog-River-One
提问by pshemek
I have been trying to solve a Java exercise on a Codility web page.
我一直在尝试解决 Codility 网页上的 Java 练习。
Below is the link to the mentioned exercise and my solution.
以下是上述练习和我的解决方案的链接。
https://codility.com/demo/results/demoH5GMV3-PV8
https://codility.com/demo/results/demoH5GMV3-PV8
Can anyone tell what can I correct in my code in order to improve the score?
谁能告诉我可以在代码中更正哪些内容以提高分数？
Just in case here is the task description:
以防万一这里是任务描述：
A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.
一只小青蛙想要到河的另一边。青蛙当前位于位置 0，想要到达位置 X。树叶从树上掉到河面上。
You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.
给定一个非空的零索引数组 A，它由 N 个代表落叶的整数组成。A[K] 表示在时间 K 时一片叶子落下的位置，以分钟为单位。
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.
目标是找到青蛙可以跳到河对岸的最早时间。青蛙只有在河对岸从 1 到 X 的每个位置都出现叶子时才能过河。
For example, you are given integer X = 5 and array A such that:
例如，给定整数 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
In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
在第 6 分钟，一片叶子落到位置 5。这是河对岸每个位置出现叶子的最早时间。
Write a function:
写一个函数：
class Solution { public int solution(int X, int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
也就是说，给定一个由 N 个整数和整数 X 组成的非空零索引数组 A，返回青蛙可以跳到河对岸的最早时间。
If the frog is never able to jump to the other side of the river, the function should return ?1.
如果青蛙永远无法跳到河的另一边，函数应该返回?1。
For example, given X = 5 and array A such that:
例如，给定 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
the function should return 6, as explained above. Assume that:
如上所述，该函数应返回 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].
Complexity:
复杂：
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).
Elements of input arrays can be modified.
可以修改输入数组的元素。
And here is my solution:
这是我的解决方案：
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;
}
}
采纳答案by rafalio
You are using arrayList.containsinside a loop, which will traverse the whole list unnecessarily.
您arrayList.contains在循环内使用，这将不必要地遍历整个列表。
Here is my solution (I wrote it some time ago, but I believe it scores 100/100):
这是我的解决方案（我前段时间写的，但我相信它的得分为 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;
}
回答by Ariel Voskov
Here's my solution. It isn't perfect, but it's good enough to score 100/100. (I think that it shouldn't have passed a test with a big A and small X)
这是我的解决方案。它并不完美，但足以获得 100/100 的分数。（我认为它不应该通过大A和小X的测试）
Anyway, it fills a new counterarray with each leaf that falls
无论如何，它用counter落下的每一片叶子填充一个新数组
counter has the size of X because I don't care for leafs that fall farther than X, therefore the try-catch block.
counter 的大小为 X，因为我不关心比 X 落得更远的叶子，因此是 try-catch 块。
AFTER X leafs fell (because it's the minimum amount of leafs) I begin checking whether I have a complete way - I'm checking that every int in count is greater than 0. If so, I return i, else I break and try again.
在 X 片叶子落下后（因为它是最小数量的叶子）我开始检查我是否有完整的方法 - 我正在检查计数中的每个 int 是否大于 0。如果是这样，我返回 i，否则我打破并再试一次.
public static int solution(int X, int[] A){
int[] count = new int[X];
for (int i = 0; i < A.length; i++){
try{
count[A[i]-1]++;
} catch (ArrayIndexOutOfBoundsException e){ }
if (i >= X - 1){
for (int j = 0; j< count.length; j++){
if (count[j] == 0){
break;
}
if (j == count.length - 1){
return i;
}
}
}
}
return -1;
}
回答by makki
Just tried this problem as well and here is my solution. Basically, I just declared an array whose size is equal to position X. Then, I declared a counter to monitor if the necessary leaves have fallen at the particular spots. The loop exits when these leaves have been met and if not, returns -1 as instructed.
刚刚也尝试过这个问题，这是我的解决方案。基本上，我只是声明了一个大小等于位置 X 的数组。然后，我声明了一个计数器来监控必要的叶子是否落在特定位置。当满足这些叶子时，循环退出，如果没有，则按照指示返回 -1。
class Solution {
public int solution(int X, int[] A) {
int size = A.length;
int[] check = new int[X];
int cmp = 0;
int time = -1;
for (int x = 0; x < size; x++) {
int temp = A[x];
if (temp <= X) {
if (check[temp-1] > 0) {
continue;
}
check[temp - 1]++;
cmp++;
}
if ( cmp == X) {
time = x;
break;
}
}
return time;
}
}
It got a 100/100 on the evaluation but I'm not too sure of its performance. I am still a beginner when it comes to programming so if anybody can critique the code, I would be grateful.
它的评价是 100/100，但我不太确定它的性能。在编程方面，我仍然是初学者，所以如果有人可以批评代码，我将不胜感激。
回答by Gali
This is my solution. It uses 3 loops but is constant time and gets 100/100 on codibility.
这是我的解决方案。它使用 3 个循环，但时间恒定，可编码性为 100/100。
class FrogLeap
{
internal int solution(int X, int[] A)
{
int result = -1;
long max = -1;
var B = new int[X + 1];
//initialize all entries in B array with -1
for (int i = 0; i <= X; i++)
{
B[i] = -1;
}
//Go through A and update B with the location where that value appeared
for (int i = 0; i < A.Length; i++)
{
if( B[A[i]] ==-1)//only update if still -1
B[A[i]] = i;
}
//start from 1 because 0 is not valid
for (int i = 1; i <= X; i++)
{
if (B[i] == -1)
return -1;
//The maxValue here is the earliest time we can jump over
if (max < B[i])
max = B[i];
}
result = (int)max;
return result;
}
}
回答by Cesar Alvarado
Maybe it is not perfect but its straightforward. Just made a counter Array to track the needed "leaves" and verified on each iteration if the path was complete. Got me 100/100 and O(N).
也许它并不完美，但它很简单。刚刚制作了一个计数器数组来跟踪所需的“叶子”，并在每次迭代时验证路径是否完整。让我得到 100/100 和 O(N)。
public static int frogRiver(int X, int[] A)
{
int leaves = A.Length;
int[] counter = new int[X + 1];
int stepsAvailForTravel = 0;
for(int i = 0; i < leaves; i++)
{
//we won't get to that leaf anyway so we shouldnt count it,
if (A[i] > X)
{
continue;
}
else
{
//first hit!, keep a count of the available leaves to jump
if (counter[A[i]] == 0)
stepsAvailForTravel++;
counter[A[i]]++;
}
//We did it!!
if (stepsAvailForTravel == X)
{
return i;
}
}
return -1;
}
回答by Koin Arab
This is my solution. I think it's very simple. It gets 100/100 on codibility. set.contains() let me eliminate duplicate position from table. The result of first loop get us expected sum. In the second loop we get sum of input values.
这是我的解决方案。我认为这很简单。它在可编码性上获得 100/100。set.contains() 让我从表格中消除重复的位置。第一个循环的结果得到我们预期的总和。在第二个循环中，我们得到输入值的总和。
class Solution {
public int solution(int X, int[] A) {
Set<Integer> set = new HashSet<Integer>();
int sum1 = 0, sum2 = 0;
for (int i = 0; i <= X; i++){
sum1 += i;
}
for (int i = 0; i < A.length; i++){
if (set.contains(A[i])) continue;
set.add(A[i]);
sum2 += A[i];
if (sum1 == sum2) return i;
}
return -1;
}
}
回答by Kamlesh Shewani
Here is my solution. It got me 100/100:
这是我的解决方案。它让我 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]);
}
回答by Sufiyan Ghori
Better approach would be to use Set, because it only adds unique values to the list. Just add values to the Setand decrement Xevery time a new value is added, (Set#add()returns trueif value is added, falseotherwise);
have a look,
更好的方法是使用Set，因为它只向列表添加唯一值。每次添加新值时，只需将值添加到Set并递减X，（如果添加了值则Set#add()返回true，false否则返回）；看一看，
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;
}
do not forget to import,
不要忘记导入，
import java.util.HashSet;
import java.util.Set;
回答by Andrzej Krzyszycha
100/100
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;
}
回答by Shwetha Shenoy
Here's my solution with 100 / 100.
这是我的 100 / 100 解决方案。
public int solution(int X, int[] A) {
int len = A.length;
if (X > len) {
return -1;
}
int[] isFilled = new int[X];
int jumped = 0;
Arrays.fill(isFilled, 0);
for (int i = 0; i < len; i++) {
int x = A[i];
if (x <= X) {
if (isFilled[x - 1] == 0) {
isFilled[x - 1] = 1;
jumped += 1;
if (jumped == X) {
return i;
}
}
}
}
return -1;
}
