Java codility Frog-River-One

Я пытаюсь решить упражнение Java на веб-странице Codility.

Ниже приведена ссылка на упомянутое упражнение и мое решение.

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); }

что, учитывая непустой нуль-индексированный массив A, состоящий из N целых чисел и целого X, возвращает самое раннее время, когда лягушка может перепрыгнуть на другую сторону реки.

Если лягушка никогда не сможет прыгнуть на другую сторону реки, функция должна вернуть -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]);
}

Ответ 3

Решение Java с использованием Sets (Framework Collections) Получено 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;
    }

Ответ 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;
}

Ответ 5

Лучшим подходом было бы использовать 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;
}

не забудьте импортировать,

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

Ответ 6

Простое решение 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;
}

Ответ 7

Вот мое решение. Это не идеально, но это достаточно хорошо, чтобы набрать 100/100. (Я думаю, что он не должен был проходить тест с большим A и маленьким X)

В любом случае он заполняет новый массив counter каждым листом, который падает

имеет размер X, потому что мне не нужны листья, которые падают дальше X, поэтому блок try-catch.

ПОСЛЕ X листьев упал (потому что это минимальное количество листьев) Я начинаю проверять, есть ли у меня полный путь - я проверяю, что каждый int в count больше 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;
}

Ответ 8

Здесь мое решение с 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;
}

Ответ 9

Здесь мое решение, набравшее 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;
    }
}

Ответ 10

Просто попробовал эту проблему, и вот мое решение. В принципе, я просто объявил массив, размер которого равен позиции 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;
    }
}

Он получил оценку 100/100, но я не уверен в ее производительности. Я все еще новичок, когда дело доходит до программирования, поэтому, если кто-то может критиковать код, я был бы благодарен.

Ответ 11

Возможно, это не идеально, но просто. Просто сделал счетчик Array, чтобы отслеживать нужные "листья" и проверять на каждой итерации, если путь был завершен. Получил 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;

    }

Ответ 12

Это мое решение. Я думаю, это очень просто. Он получает 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;
    }
}

Ответ 13

Вот что у меня на С#. Вероятно, он может быть реорганизован. Мы отбрасываем числа, большие, чем X, где мы хотим остановиться, а затем добавляем числа в массив, если они еще не добавлены. Когда счетчик списка достигнет ожидаемого числа, X, верните результат. 100%

        var tempArray = new int[X+1];
        var totalNumbers = 0;
        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] > X || tempArray.ElementAt(A[i]) != 0)
                continue;
            tempArray[A[i]] = A[i];
            totalNumbers++;

            if (totalNumbers == X)
                return i;
        }

        return -1;

Ответ 14

Ваш алгоритм совершенен, за исключением кода ниже Ваш код возвращает значение, только если список [iii] соответствует searchValue.

Алгоритм должен быть скорректирован таким образом, чтобы он возвращал значение, если сумма == n * (n + 1)/2.

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;
        int sumV = searchedValue * (searchedValue + 1) / 2;   
        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];
                if (sum == sumV) {
                    return iii;
                }
                arrayList.add(list[iii]);
            }
        }
        return -1;
    }
}

Я думаю, вам нужно также проверить производительность. Я просто обеспечил выход только

Ответ 15

Это решение, которое я опубликовал сегодня, дал 100% на кодовости, но уважительно @rafalio отвечает, что он требует в K раз меньше памяти

public class Solution {

    private static final int ARRAY_SIZE_LOWER = 1;
    private static final int ARRAY_SIZE_UPPER = 100000;
    private static final int NUMBER_LOWER = ARRAY_SIZE_LOWER;
    private static final int NUMBER_UPPER = ARRAY_SIZE_UPPER;

    public static class Set {

        final long[] buckets;

        public Set(int size) {
            this.buckets = new long[(size % 64 == 0 ? (size/64) : (size/64) + 1)];
        }

        /**
         * number should be greater than zero
         * @param number
         */
        public void put(int number) {
            buckets[getBucketindex(number)] |= getFlag(number); 
        }

        public boolean contains(int number) {
            long flag = getFlag(number);
            // check if flag is stored
            return (buckets[getBucketindex(number)] & flag) == flag;
        }

        private int getBucketindex(int number) {
            if (number <= 64) {
                return 0;
            } else if (number <= 128) {
                return 1;
            } else if (number <= 192) {
                return 2;
            } else if (number <= 256) {
                return 3;
            } else if (number <= 320) {
                return 4;
            } else if (number <= 384) {
                return 5;
            } else 
                return (number % 64 == 0 ? (number/64) : (number/64) + 1) - 1;
        }

        private long getFlag(int number) {
            if (number <= 64) {
                return 1L << number;
            } else
                return 1L << (number % 64);
        }
    }

    public static final int solution(final int X, final int[] A) {
        if (A.length < ARRAY_SIZE_LOWER || A.length > ARRAY_SIZE_UPPER) {
            throw new RuntimeException("Array size out of bounds");
        }
        Set set = new Set(X);
        int ai;
        int counter = X;
        final int NUMBER_REAL_UPPER = min(NUMBER_UPPER, X);
        for (int i = 0 ; i < A.length; i++) {
            if ((ai = A[i]) < NUMBER_LOWER || ai > NUMBER_REAL_UPPER) {
                throw new RuntimeException("Number out of bounds");
            } else if (ai <= X && !set.contains(ai)) {
                counter--;
                if (counter == 0) {
                    return i;
                }
                set.put(ai);
            }
        }
        return -1;
    }

    private static int min(int x, int y) {
        return (x < y ? x : y);
    }
}

Ответ 16

Это мое решение, оно получило меня 100/100 и O (N).

public int solution(int X, int[] A) {
    Map<Integer, Integer> leaves = new HashMap<>();

    for (int i = A.length - 1; i >= 0 ; i--)
    {
        leaves.put(A[i] - 1, i);
    }

    return leaves.size() != X ? -1 : Collections.max(leaves.values());
}

Ответ 17

ниже - мое решение. Я в основном создал набор, который позволяет только uniques, а затем пройти через массив и добавить каждый элемент для установки и сохранить счетчик, чтобы получить сумму набора, а затем использовать формулу суммы последовательных чисел, после чего я получил 100%. Примечание: если вы добавите набор, используя java 8 stream api, решение становится квадратичным, и вы получите% 56.

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

    long sum = X * (X + 1) / 2;
    Set<Integer> set = new HashSet<Integer>();
    int setSum = 0;

    for (int i = 0; i < A.length; i++) {
        if (set.add(A[i]))
            setSum += A[i];

        if (setSum == sum) {
            return i;
        }

    }

    return -1;
}

Ответ 18

Это мое решение

public func FrogRiverOne(_ X : Int, _ A : inout [Int]) -> Int {

    var B = [Int](repeating: 0, count: X+1)

    for i in 0..<A.count {
        if B[A[i]] == 0 {
            B[A[i]] = i+1
        }
    }

    var time = 0

    for i in 1...X {
        if( B[i] == 0 ) {
            return -1
        } else {
            time = max(time, B[i])
        }
    }

    return time-1
}

A = [1,2,1,4,2,3,5,4]
print("FrogRiverOne: ", FrogRiverOne(5, &A))

Ответ 19

На самом деле я переписал это упражнение, не видя своего последнего ответа, и придумал другое решение 100/100 и O (N).

public int solution(int X, int[] A) {
    Set<Integer> leaves = new HashSet<>();

    for(int i=0; i < A.length; i++) {
        leaves.add(A[i]);

        if (leaves.contains(X) && leaves.size() == X)  return i; 
    }

    return -1;
}

Мне больше нравится этот, потому что он еще проще.

Ответ 20

Это мое решение. Он использует 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;
    }
}

Ответ 21

Короткий и сладкий код C++. Получает идеальный 100%... Барабан ролл...

#include <set>
int solution(int X, vector<int> &A) {
    set<int> final;
    for(unsigned int i =0; i< A.size(); i++){
        final.insert(A[i]);
        if(final.size() == X) return i;
    }
    return -1;
}

Ответ 22

import java.util.Set;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int X, int[] A) {
     Set<Integer> positionsCovered = new HashSet<Integer>(); 
//Set covering the leaves fallen to keep track of the distance to destination   

        if(X == 1)
             return 0 ;
       int position = 0;     
       for(int i = 0; i < A.length -1 ;i++ ) {       
           if(A[i] <= X && A[i] > 1 && positionsCovered.size() < (X-1)) { 
      //X-1 as we start from 1
               positionsCovered.add(A[i]);
           }
           if(positionsCovered.size()== (X-1)) {
               position = i ;
            break;
           }
       }         
        return position != 0 ? position : -1;
    }
}

Ответ 23

Мое решение JavaScript, получившее 100 по всем направлениям. Поскольку предполагается, что числа находятся в диапазоне ширины реки, подойдет просто сохранение логических значений во временном массиве, который можно проверить на наличие дубликатов. Затем, как только вы наберете столько чисел, сколько и количества X, вы знаете, что у вас есть все листья, необходимые для пересечения.

function solution(X, A) {
    covered = 0;
    tempArray = [];
    for (let i = 0; i < A.length; i++) {
        if (!tempArray[A[i]]) {
            tempArray[A[i]] = true;
            covered++
            if(covered === X) return i;
        }
    }
    return -1;
}

Ответ 24

Это зацикливает массив A и вставляет данные в массив B (1) в каждую позицию, на которую указывает содержимое в A..

Если A [0] = 4, то при B [4-1] = 1 делайте это до тех пор, пока var = X.

public static int bestSolution(int X, int[] A) {
        int[] B = new int[X];
        int var = 0;
        for (int i = 0; i < A.length; i++) {
            int content = A[i];
            if (B[content - 1] == 0) {
                B[content - 1] = 1;
                var++;
            }
            if(var == X){
                return i;
            }
        }
        return -1;
    }

Ответ 25

 private static int FrogRiverOne(int X, int[] A)
        {
            HashSet<int> occ = new HashSet<int>();
            for (int i = 0; i < A.Length; i++)
            {
                if (A[i] <= X)
                {
                    occ.Add(A[i]);
                }
                if (occ.Count == X)
                    return i;
            }
            return -1;}