Флаг Codility Java - PullRequest
Новая
       45

Флаг Codility Java

0 голосов
/ 10 сентября 2018

Я знаю, что этот вопрос задавался пару раз, но я ищу объяснение, а не решение.

Задача следующая:

Дан непустой массив A, состоящий из N целых чисел.

Пик - это элемент массива, который больше, чем его соседи. Точнее, это индекс P такой, что 0 < P < N − 1 и A[P − 1] < A[P] > A[P + 1].

Например, следующий массив A: 

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

имеет ровно четыре пика: элементы 1, 3, 5 и 10.

Вы отправляетесь в путешествие по ряду гор, относительные высоты которых представлены массивом A, как показано на рисунке ниже. Вы должны выбрать, сколько флагов вы должны взять с собой. Цель состоит в том, чтобы установить максимальное количество флагов на пиках в соответствии с определенными правилами.

Флаги можно устанавливать только на пиках. Более того, если вы берете K флагов, то расстояние между любыми двумя флагами должно быть больше или равно K. Расстояние между индексами P и Q является абсолютным значением |P − Q|.

Например, с учетом горного хребта, представленного выше массивом A, с N = 12, если вы берете:

два флага, вы можете установить их на пики 1 и 5; три флага, вы можете установить их на пики 1, 5 и 10; четыре флага, вы можете установить только три флага, на пиках 1, 5 и 10. Поэтому в этом случае вы можете установить максимум три флага.

Написать функцию: 

class Solution { 
   public int solution(int[] A);
}

что, учитывая непустой массив A из N целых чисел, возвращает максимальное количество флагов, которые могут быть установлены на пиках массива.

Например, следующий массив A: 

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

функция должна возвращать 3, как описано выше.

Напишите эффективный алгоритм для следующих предположений:

N - целое число в диапазоне [1..400,000]; каждый элемент массива A является целым числом в диапазоне [0..1,000,000,000].

Пока мой код: 

class Solution {
 public int solution(int[] A) {
    // write your code in Java SE 8
    List <Integer> index= new ArrayList <Integer> ();
    int N=A.length;
    boolean block=false;
    int divisor=0;
    int flags=0;
    int counter=0;
    for(int i=1;i<A.length-1;i++){

        if(A[i]>A[i+1] && A[i]>A[i-1]){

            index.add(i);
        }

    }

    for(int k=N;k>=1;k--){

    if(N%k==0) {
        divisor=k;
        block=true;


    }

Я думал, что прохождение каждого из индексов в списке будет более быстрым подходом, а использование делителей - лучший подход, поскольку эта задача рассматривается в уроке простых / составных чисел. Я просто не знаю, как это сделать, поэтому любые идеи с объяснениями в терминах непрофессионала действительно помогут. Спасибо

...