Мин. Средняя двухкаскадная тележка

Ответ 1

Я написал это несколько дней назад:

Проверь это:

http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

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

Надеюсь, поможет!

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

И теперь я также могу предоставить свою реализацию, основываясь на ссылке на CodeSays, которую я предоставил ранее: https://codility.com/demo/results/demoERJ4NR-ETT/

class Solution {
    public int solution(int[] A) {
        int minAvgIdx=0;
        double minAvgVal=(A[0]+A[1])/2; //At least two elements in A.
        double currAvg;
        for(int i=0; i<A.length-2; i++){
            /**
             * We check first the two-element slice
             */
            currAvg = ((double)(A[i] + A[i+1]))/2;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
            /**
             * We check the three-element slice
             */
            currAvg = ((double)(A[i] + A[i+1] + A[i+2]))/3;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
        }
        /**
         * Now we have to check the remaining two elements of the array
         * Inside the for we checked ALL the three-element slices (the last one
         * began at A.length-3) and all but one two-element slice (the missing
         * one begins at A.length-2).
         */
        currAvg = ((double)(A[A.length-2] + A[A.length-1]))/2;
        if(currAvg < minAvgVal){
            minAvgVal = currAvg;
            minAvgIdx = A.length-2;
        }
        return minAvgIdx;
    }
}

Ответ 2

Сложная часть состоит в том, чтобы выяснить даже до того, как вы начнете кодирование, что наверняка будет средний минимальный срез длиной 2 или 3. Оттуда это проще, но у меня есть несколько важных замечаний:

• Вам не нужно деление вообще, вы можете вместо этого умножить, чтобы вы могли получить одинаковое среднее значение по фрагменту длиной 6 и вообще избегать операций с плавающей запятой

• Вам не нужно деление (или в моем случае умножение) в цикле, один раз в конце этого достаточно.

• Если вам нужно было это сделать, вы всегда должны сравнивать два числа с плавающей запятой: EPSILON = 0.0000001 (в зависимости от точности, которую вы ищете, это может быть другое число), и если Math.abs(averageTwo - averageThree) < EPSILON означает, что они равны. И вам не нужна двойная точность, достаточно float.

Вот мое решение на Java, оно получило 100% на Codility:

public int solution(int[] A) {
    if (A.length == 2) return 0;

    int minSliceTwo = A[0] + A[1];
    int minTwoIndex = 0;

    int minSliceThree = Integer.MAX_VALUE;
    int minThreeIndex = 0;

    for (int i = 2; i < A.length; i++) {
        int sliceTwo = A[i - 1] + A[i];
        if (sliceTwo < minSliceTwo) {
            minSliceTwo = sliceTwo;
            minTwoIndex = i - 1;
        }

        int sliceThree = sliceTwo + A[i - 2];
        if (sliceThree < minSliceThree) {
            minSliceThree = sliceThree;
            minThreeIndex = i - 2;
        }
    }
    int averageMinTwo = minSliceTwo*3;
    int averageMinThree = minSliceThree*2;

    if (averageMinTwo == averageMinThree) return Math.min(minTwoIndex, minThreeIndex);
    else return averageMinTwo < averageMinThree ? minTwoIndex : minThreeIndex;
}

Ответ 3

100% балл с C++ по алгоритму Кадане

int solution(vector<int> &A) {

    // Find prefix sum.
    int N = A.size();
    vector<int> ps(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        ps[i] = A[i - 1] + ps[i - 1];
    }

    int lft_idx, min_lft_idx;
    double avg_here, min_avg, avg_of_two, avg_with_prev;

    // Initialize variables at the first possible slice (A[0:1]).
    lft_idx = min_lft_idx = 0;
    avg_here = min_avg = (A[0] + A[1]) / 2.0;

    // Find min average of every slice that ends at ith element,
    // starting at i = 2.
    for (int i = 2; i < N; i ++) {

        // average of A[lft_idx : i]
        avg_with_prev = ((double) ps[i + 1] - ps[lft_idx]) / 
                        (i - lft_idx + 1);

        // average of A[i - 1 : i]
        avg_of_two = (A[i - 1] + A[i]) / 2.0;

        // Find minimum and update lft_idx of slice
        // (previous lft_idx or i - 1).
        if (avg_of_two < avg_with_prev) {
            avg_here = avg_of_two;
            lft_idx = i - 1;
        }
        else
            avg_here = avg_with_prev;

        // Keep track of minimum so far and its left index.
        if (avg_here < min_avg) {
            min_avg = avg_here;
            min_lft_idx = lft_idx;
        }
    }

    return min_lft_idx;
}

Хотя этот вопрос кажется довольно популярным, исходя из того, сколько людей уже разместили свой код, я не был удовлетворен решением для 2/3-элементных субликатов (давай! Кто бы мог подумать об этом во время интервью?), ни с объяснениями (или их отсутствием).

Поэтому я продолжал искать другие подходы. Я узнал об алгоритме Кадане для задачи о максимальном подмассиве (MSP), а затем подумал о другом решении.

Основной вопрос (аналогичный MSP): каково минимальное среднее для среза, включающего i-й элемент?

Чтобы ответить на него, мы будем искать срезы, которые заканчиваются на i-й элемент, только обновляя их левый индекс. То есть мы должны проверить наличие срезов A[lft_idx: i].

Предполагая, что мы знаем lft_idx среза A[lft_idx: я - 1] с минимальным средним, тогда у нас есть две возможности:

1. Среднее значение A[lft_idx: i] минимально.
2. Среднее значение A[i - 1: i] является минимальным (кратчайший возможный срез имеет 2 элемента).

В случае 1 происходит то, что мы продолжаем увеличивать фрагмент, начинающийся с lft_idx.

Однако в случае 2 мы находим, что увеличение предыдущего среза фактически увеличивает среднее значение. Таким образом, мы начинаем снова и "сбрасываем" начало среза (lft_idx) к предыдущему элементу (i - 1). Теперь у нас есть новый лучший срез размера 2, чтобы расти с этой точки.

Наконец, мы хотим получить глобальное минимальное среднее, поэтому нам нужно отслеживать минимальное и то, где оно началось (вопрос только об этом, но мы могли бы также сохранить правильный индекс).

Примечание: здесь я использую суммы префиксов для вычисления средних значений среза, потому что там, где вопрос появляется в Codility, но его можно легко заменить на переменную с размером предыдущего среза и другим умножением.

Ответ 4

100% балл. Javascript.

var min_pos = 0;
var min = Number.MAX_VALUE;

function solution(A) {
  for (var a = 0; a < A.length - 2; a++) {
    process((A[a] + A[a + 1]) / 2.0, a);
    process((A[a] + A[a + 1] + A[a + 2]) / 3.0, a);
  }

  process((A[A.length - 2] + A[A.length - 1]) / 2.0, A.length - 2);
  return min_pos;
}

function process(val, a) {
  if (val < min) {
    min_pos = a;
    min = val;
  }
}

Ответ 5

Это математическая проблема... и для ее решения вам нужно понять взаимосвязь между средними значениями срезов.

Из описания проблемы известно, что срезы являются минимальной длиной 2. Фокус этой проблемы состоит в том, что средний средний срез также не может быть больше 3. Поэтому нам нужно только вычислить avg кусочков длины 2 и 3.

Чтобы понять, почему средний средний срез не может быть больше 3, рассмотрим случай, когда он длиннее 3...

ex. [-10, 3, 4, -20]

avg(0,3) = -23 / 4 = -5.75 // entire array is -5.75 average
avg(0,1) = -7 / 2 = -3.5 // subslice (0,1)
avg(2,3) = -16 / 2 = -8 // subslice (2,3)

Обратите внимание, что (avg(0,1) + avg(2,3)) / 2 = avg(0,3) Поэтому, если avg(0,1) != avg(2,3), то один из них должен быть меньше другого.

Независимо от того, каким образом мы разделим этот массив, если срезы не совсем одинаковы, то один из них должен иметь более низкое среднее значение, чем полный фрагмент. Играйте с ним, и вы увидите, что это правда. Там есть математические доказательства.

Ответ 6

   static public int solution(int[] A) {
    // write your code in Java SE 8

    float avg = 0f;
    int min_index = 0;
    int P = 0;
    //formula

    float sums[] = new float[A.length ];

    //sufffix sums
    int prefix = 0;
    for (int i = 0; i < A.length; i += 1) {
        prefix += A[i];
        sums[i] += prefix;
    }
    float min_avg = Float.MAX_VALUE;
    for (int i = 1; i < A.length; i++) {
        avg = (sums[i] - sums[P] + A[P]) / (i - P + 1);
        if (avg < min_avg) {
            min_avg = avg;
            min_index = P;
        }

Идея довольно проста, но не так проста, A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1) то есть формула там, сначала вычислите суммы префикса.

формула: min_avg = (префикс [i] - префикс [P] + A [P])/(i - P + 1) '

        if (A[i] < min_avg) {
            P = i;
        }
    }


    return min_index;


}

Ответ 7

Я понимаю, что http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html дает лучшее объяснение и решение, которые я знаю до сих пор. Поскольку это находится в разделе префиксной суммы, следующим является то, которое я пытался ознакомиться с методом суммы префикса.

function solution($A) {
        // write your code in PHP5.3

        $N = count($A);
        if ($N > 100000 || $N < 2 ) {
            return -1;
        } elseif ($N === 2) {
            return 0;
        }

        $presum = array();
        $presum[] = 0;

        $mavg = PHP_INT_MAX;

        $index = 0;
        for ($i = 0; $i < $N; $i++) {                
            $presum[$i+1] = $A[$i] + $presum[$i];
        }

        for ($i = 0; $i < $N-2; $i++) {
            for ($j = $i+1; $j < $i + 3; $j++ ) {
                $avg = ($presum[$j+1] - $presum[$i]) / ($j - $i + 1);

                if ($mavg > $avg) {
                    $mavg = $avg;
                    $index = $i;
                }
            }
        }
        $avg = ($presum[$N] - $presum[$N-2]) / 2;
        if ($mavg > $avg) {
            $index = $N - 2;
        }

        return $index;
}

Ответ 8

 public int solution(int[] A)
        {
//C# solution thats getting 100%. Once you find min avg with always within 2   //or 3 elements of moving index its much simpler sol
            int minIndex = 0;
            double minAvgVal = Double.MaxValue;

            for (int i = 0; i < A.Length-2; i++)
            {
                double twoDigitMin = (A[i] + A[i + 1])/2.0;
                if (minAvgVal > twoDigitMin)
                {
                    minAvgVal = twoDigitMin;
                    minIndex = i;
                }

                double threDigitMin = (A[i] + A[i + 1] + A[i+2]) / 3.0;
                if (minAvgVal > threDigitMin)
                {
                    minAvgVal = threDigitMin;
                    minIndex = i;
                }
            }

            double last2Avg = (A[A.Length - 2] + A[A.Length - 1])/2.0;
            if (minAvgVal > last2Avg)
            {
                minIndex = A.Length - 2;
            }

            return minIndex;
        }

Ответ 9

Здесь другое Java-решение 100/100 с использованием префиксных сумм:

public int solution(int[] A) {
        int len = A.length, result = len - 1, sum = 0;
        int[] prefixSums = new int[len + 1];

        for (int i = 1; i <= len; ++i) {
            prefixSums[i] = prefixSums[i-1] + A[i-1];
        }

        double min = Double.MAX_VALUE, average = 0d;

        for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
            sum = prefixSums[Q + 1] - prefixSums[P];
            average = (sum)/(double) 2;

            if (average < min) {
                min = average;
                result = P;
            }

            if ( Q + 2 < prefixSums.length ) {
                sum = prefixSums[Q + 2] - prefixSums[P];
                average = (sum)/(double) 3;

                if (average < min) {
                    min = average;
                    result = P;
                }
            }

        }

        return result;
    }

Здесь ссылка на кодовость: https://codility.com/demo/results/demo4S4VJX-WMJ/

Ответ 10

Здесь выполняется реализация префикса Sum (100% в Codility):

import sys

def solution(A):

    n             = len(A)
    pre_sum       = [0] * (n+1)
    min_slice_avg = sys.maxint
    min_slice_idx = 0

    for i in xrange(1,n+1):
        pre_sum[i] = pre_sum[i-1] + A[i-1]

        # calculate at least 2 prefix sums
        if i-2 < 0: continue

        # check prev 3 slices if we have calculated 3 prefix sums
        if i>=3:
            prev_3_slice_avg = (pre_sum[i] - pre_sum[i-3]) / 3.0

            if prev_3_slice_avg < min_slice_avg:
                min_slice_avg = prev_3_slice_avg
                min_slice_idx = i-3

        # check prev 2 slices
        prev_2_slice_avg = (pre_sum[i] - pre_sum[i-2]) / 2.0

        if prev_2_slice_avg <  min_slice_avg:
            min_slice_avg = prev_2_slice_avg
            min_slice_idx = i-2

    return min_slice_idx

Ответ 11

100% правильность и производительность (java)

void sumArray(int[] A, int[] sum) {
    for (int i = 1; i < sum.length; i++) {
        sum[i] = sum[i - 1] + A[i - 1];
    }
}

int getTotalSum(int[] sum, int start, int last) {
    return sum[last + 1] - sum[start];
}

double minav = Double.MAX_VALUE;
int minind = Integer.MAX_VALUE;

public int solution(int[] A) {
    int[] sum = new int[A.length + 1];
    sumArray(A, sum);
    int startpos = 0;
    for (int i = 1; i <= 2; i++) {
        startpos = 0;
        while (startpos + i < A.length) {
            double suma = getTotalSum(sum, startpos, startpos + i);
            double size = (startpos + i) - startpos + 1;
            double av = suma / size;
            if (av <= minav) {

                if (av < minav || startpos < minind) {
                    minind = startpos;
                }
                minav = av;


            }
            startpos += 1;
        }
    }
    return minind;
}

Ответ 12

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

Таким образом, минимум элементов, которые мы можем добавить к срезу до того, как он вырастет до 2 срезов минимальной длины, равен 1. Поэтому мы должны проверить срез длины 2 и 3. Нам не нужно выходить за пределы среза длины 3, так как в конечном итоге это будет есть 2 ломтика длиной 2.

Давайте возьмем другой пример, предположим, что минимальная длина слайса равна 3. Теперь в этом случае, согласно нашей формуле, нам нужно проверить от слайса длиной от 3 до 5. Рассмотрим следующий массив

-30, -1, -1, -1, -30, -1, -1, 1, 2, 3,4,45

Здесь, если мы берем Slice (0, 4), среднее значение составляет -1 2,6 (что является минимумом). Попробуйте все другие комбинации (для длины 3 и 4) и поиграйте с ними. Ты поймешь.

Если мы возьмем срез длиной 6, то срез (0, 5), среднее -1 0,66, что равно среднему среза (0, 2) и среза (3, 5)

Решение без использования префиксных сумм (100% баллов)

    public int solution(int[] A)    {
    float tempAverage,finalAverage = Float.MAX_VALUE;
    int startLocation = 0;
    int lengthOfTheSlice = 0;
    for(int i=0; i < A.length -1; ++i)  {
        tempAverage = (float)(A[i] + A[i+1])/2;
        if(tempAverage < finalAverage)    {
            finalAverage = tempAverage;
            startLocation = i;
            lengthOfTheSlice =2;
        }
    }
    for(int i=0; i < A.length -2; ++i)  {
        tempAverage = (float)(A[i] + A[i+1]+ A[i+2])/3;
        if(tempAverage < finalAverage)    {
            finalAverage = tempAverage;
            startLocation = i;
            lengthOfTheSlice =3;
        }
    }
    System.out.print("Length of the slice \t"+lengthOfTheSlice);
    return startLocation;
}

Ответ 13

Решение для оценки 100/100, написанное на php http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html

Ответ 14

Мой ответ со счетом 100

public class MinAvgTwoSlice {

public static void main(String[] args) {

    System.out.println(new MinAvgTwoSlice().solution(new int[] {4, 2, 2, 5, 1, 5, 8} ));    
}

public int solution(int[] A) {

    double minAvg = 100000;
    int index=0;

    if(A.length<=2) {

        return 0;
    }

    for(int i=0;i<A.length-2;i++) {

        if((A[i]+A[i+1])/2.0<minAvg) {
            minAvg=(A[i]+A[i+1])/2.0;
            index=i;
        }

        if((A[i]+A[i+1]+A[i+2])/3.0<minAvg)  {

            minAvg=(A[i]+A[i+1]+A[i+2])/3.0;
            index=i;
        }
    }

    int aMax = A.length-2;

    if((A[aMax]+A[aMax+1])/2.0<minAvg) {

        minAvg=(A[aMax]+A[aMax+1])/2.0;
        index=aMax;
    }

    return index;
}
}

Спасибо: Исходя из логики, представленной в codesays.com

Ответ 15

Это мое решение написано на C (набрано 100%)

#include <string.h>

int solution(int A[], int N) {
    // write your code in C99

    int *p, i;
    float minAvg, tmpAvg;
    int index=0;

    p=malloc(sizeof(int)*(N+1));
    memset(p, 0, sizeof(int)*(N+1));

    if(N == 2) {
        return 0;
    }

    *p=0;

    //Building prefixes vector
    for(i=0;i<N;i++) {
        *(p+i+1)=*(p+i)+A[i];
    }

    minAvg=*(p+N)/(float)(N);

    for(i=0; i<N-1; i++) {
        tmpAvg=(*(p+i+2)-*(p+i))/(float)(2);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }

    for(i=0; i<N-2; i++) {
        tmpAvg=(*(p+i+3)-*(p+i))/(float)(3);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }

    free(p);
    return index;
}

Ответ 16

Вот реализация Go:

func Solution(A []int) int {
    if len(A) < 2 {
        return -1
    }

    result := 0
    minAvg := float64(A[0]+A[1]) / 2
    var curAvg float64
    for index := 0; index < len(A)-2; index++ {
        curAvg = float64(A[index]+A[index+1]) / 2
        if curAvg < minAvg {
            minAvg = curAvg
            result = index
        }

        curAvg = float64(A[index]+A[index+1]+A[index+2]) / 3
        if curAvg < minAvg {
            minAvg = curAvg
            result = index
        }
    }

    curAvg = float64(A[len(A)-2]+A[len(A)-1]) / 2
    if curAvg < minAvg {
        minAvg = curAvg
        result = len(A) - 2
    }

    return result
}

Ответ 17

Я получил 100% на С#. Попробуйте https://codility.com/demo/results/demoV25DUE-9A8.

    public static int solution(int[] A)
    {
        float min_avg = (A[0] + A[1]) / 2;
        int minpos = 0;

        for (int i = 0; i < A.Length-2; i++)
        {
            float firsttwo = (float)(A[i] + A[i+1])/2;

            if (firsttwo < min_avg)
            {
                min_avg = firsttwo;
                minpos = i;
            }

            float three = (float)(A[i] + A[i+1] + A[i+2])/3;
            if (three < min_avg)
            {
                min_avg = three;
                minpos = i;
            }

            float lasttwo = (float)(A[i + 1] + A[i + 2]) / 2;
            if (lasttwo < min_avg)
            {
                min_avg = lasttwo;
                minpos = i+1;
            }
        }

        return minpos;
    }

Ответ 18

private static int solution(int[] a) {
    // TODO Auto-generated method stub

    int sum=0;
    int absSum=0;
    int minAbsSlice=10000;

    for(int i=0;i<a.length;i++){
        sum=a[i];
        for(int j=1;j<a.length;j++){
            if(j>=i){
                absSum=sum+a[j];
                if(absSum<sum){
                    sum=absSum;
                    absSum=Math.abs(absSum);

                }else{

                    absSum=Math.abs(sum);
                    sum=absSum;
                }
            }
        }
        sum=0;
        if(minAbsSlice<absSum){
            minAbsSlice=minAbsSlice;
        }else{
            minAbsSlice=absSum;
        }

    }
    return minAbsSlice;
}

Ответ 19

Вот мое решение в С++ на основе доказательства того, что минимальный срез должен существовать с длиной 2 или 3, см. доказательство в https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

Получил оценку 100% на Codility за правильность и скорость. Нет необходимости выделять какую-либо память для решения этой проблемы, поэтому пространство для алгоритма O (1), не считая входного вектора.

int solution(vector<int> &A) {
    int N             = A.size();
    int minSliceStart = 0;

    if (N > 2) {
        // Min Slice must be of length 2 or 3.
        // If Min Slice is longer, 
        //    it must be divisible into smaller parts of equal average
        int min_2_slice_start = 0;
        int min_3_slice_start = 0;
        int min_2_slice_sum   = A[0]+A[1];
        int min_3_slice_sum   = A[0]+A[1]+A[2];

        for(int i=0; i<(N-1); i++) {
            int cur_2_slice_sum = A[i]+A[i+1];

            // check if the current 2-slice sum is smaller
            if (cur_2_slice_sum < min_2_slice_sum) {
                min_2_slice_sum   = cur_2_slice_sum;
                min_2_slice_start = i;
            }

            // check if the current 3-slice sum is smaller
            if (i<(N-2)) {
                int cur_3_slice_sum = A[i]+A[i+1]+A[i+2];
                if (cur_3_slice_sum < min_3_slice_sum) {
                    min_3_slice_sum   = cur_3_slice_sum;
                    min_3_slice_start = i;
                }
            }
        }

        #ifdef Want_Debug_Statements
            cout << "2-Slice: start=" << min_2_slice_start << ", sum=" << min_2_slice_sum <<endl;
            cout << "3-Slice: start=" << min_3_slice_start << ", sum=" << min_3_slice_sum <<endl;
        #endif

        // If 2-slice or 3-slice are equal, take the first one.
        // Note: rather than computing averages by dividing,
        // multiple each side by the other denominator instead & compare.
        if (min_2_slice_sum*3 == min_3_slice_sum*2) {
            if (min_2_slice_start < min_3_slice_start)
                minSliceStart = min_2_slice_start;
            else
                minSliceStart = min_3_slice_start;
        } else {
            if (min_2_slice_sum*3 < min_3_slice_sum*2)
                minSliceStart = min_2_slice_start;
            else
                minSliceStart = min_3_slice_start;
        }
    }

    return minSliceStart;
}

Ответ 20

100% в python:

def solution(A):
 if(len(A) < 2):
     return 0;
 MinAvg=float(A[0]+A[1])/float(2);
 Index=0;
 for nn in range(1,len(A)-1):
     Avg=float(A[nn]+A[nn+1])/float(2);
     if(Avg<MinAvg):
         MinAvg=Avg;
         Index=nn;     
 for nn in range(0,len(A)-2):
     Avg=float(A[nn]+A[nn+1]+A[nn+2])/float(3);
     if(Avg<MinAvg):
         MinAvg=Avg;
         Index=nn;                    
 return Index;     
pass 

Для объяснения:

Усреднение и сравнение на 2 последовательных элементах дает почти максимальный балл. Потому что, когда вы добавляете элемент, если среднее значение меньше, то следующие два элемента будут иметь меньшее среднее значение.

Впоследствии остаются только исключения с тремя элементами, такими как [-1, 2, 4, -1, 2, -1].

Ответ 21

Это моя реализация на Java. Я получил 100%. Алгоритм тот же (суммы 2 и 3 последовательных значения), за исключением того, что я не использовал дополнительную память для префиксных сумм. Нам не нужны все суммы сразу, поэтому мы можем удерживать только текущую сумму и вычитать из списка сумму самого левого элемента из суммы.

public int solution(int vect[]) {

    double minAvg = (vect[0] + vect[1]) / 2.;
    int minIndex = 0;

    double tempAvg = minAvg;
    int tempSum = vect[0] + vect[1];
    int tempIndex = 0;
    int tempLength = 2;

    double newAvg;
    int newSum, newIndex;

    for(int j=2; j<vect.length; ++j) {
        ++tempLength;
        tempSum += vect[j];
        tempAvg = (double)tempSum / tempLength;


        newSum = tempSum - vect[tempIndex];
        newIndex = tempIndex+1;
        newAvg = newSum/(j-newIndex+1.);

        while(newAvg < tempAvg && newIndex < j) {
            tempIndex = newIndex;
            tempSum = newSum;
            tempAvg = newAvg;
            --tempLength;

            newSum = tempSum - vect[tempIndex];
            newIndex = tempIndex+1;
            newAvg = newSum/(j-newIndex+1.);
        }

        if (tempAvg < minAvg) {
            minIndex = tempIndex;
            minAvg = tempAvg;
        }
        else if(tempAvg > minAvg && j-tempIndex>1) {
            tempIndex = j;
            tempLength = 1;
            tempSum = vect[j];
        }
    }
    return minIndex;
}

Ответ 22

C++ Решение, прекрасно работает для меня

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2) return 0;
    int min_index = 0;
    double min = (A[0] + A[1]) / 2;

    for(unsigned int i = 2; i < A.size(); i++){

        double temp_three = (A[i - 2] + A[ i - 1] + A[i]) / 3.0;
        double temp_two = (A[ i - 1] + A[i]) / 2.0;

        if(temp_three < min){
          min = temp_three;  
          min_index = i - 2;
        } 
        if(temp_two < min){
            min = temp_two;
            min_index = i - 1;
        }
    }

    return min_index;
}

Ответ 23

В функциональных языках программирования FP таких как Scala или Haskell, префиксные суммы предоставляются с помощью функции Scan высшего порядка.

В нашем случае добавочная функция HOF _ + _ эквивалентна лямбда-функции (x, y) => x + y

https://en.wikipedia.org/wiki/Prefix_sum

FP позволяет более простой способ выразить алгоритм, который я считаю более легким для понимания.

Решение получило 100% даже при recursion и нескольких объяснениях.

https://app.codility.com/demo/results/trainingBZJU4M-NXE/

  def solution(a: Array[Int]): Int = {

    val n: Int = a.length

    /**
      * Let initialize the prefixSums Array
      */
    val prefixSums: Array[Int] = a.scan(0)(_ + _)

    /**
      * Let look for a Minimum that has:
      * a position and an average
      * (i.e. Product Type Data Structure)
      */
    case class Minimum(position: Int, average: Float)

    /**
      * Based on a Slice: Position [P] and [Q]
      * Q here is represented by its size [P - Q] (2 or 3)
      * CAPTURE only if there is a change in the minimum average
      */
    def average(p: Int, q: Int, min: Minimum): Minimum = {
      val average: Float = (prefixSums(p + q) - prefixSums(p)) / q.toFloat
      if (average < min.average) min.copy(position = p, average = average) else min
    }

    /**
      * Let start with the first position
      * and a max average value
      */
    val init = Minimum(position = 0, average = Float.MaxValue)

    /**
      * Let fold through the A Array indices minus one
      * (paying attention to the slice size)
      *
      * while capturing the minimum average.
      * If Q size reaches 3 (instead of regular slice tuple:
      *    capture the last minimum average
      *    otherwise return the current minimum average
      * give the minimal position
      */
    (0 until n - 1).toList
      .foldLeft(init) { (min, p) =>
        val currentMin = average(p, 2, min)
        if (p < n - 2) average(p, 3, currentMin) else currentMin
      }.position

  }

Ответ 24

C++ на основе алгоритма Канаде с префиксной суммой: https://app.codility.com/demo/results/training66V2HC-V6S/

Ответ 25

C++ на основе алгоритма Канаде с префиксной суммой: https://app.codility.com/demo/results/training66V2HC-V6S/

int solution(std::vector<int> &A)
{
    int minIndex = 0;
    auto minAvgVal = std::numeric_limits<int>::max();

    int sumOfTwo = 0;
    int twoDigitSum = 0;
    int threeDigitSum = 0;

    size_t size = A.size();
    for (size_t i = 0; i < (size - 2); ++i) {
        sumOfTwo = A[i] + A[i + 1];
        twoDigitSum = 3 * sumOfTwo;
        if (minAvgVal > twoDigitSum) {
            minAvgVal = twoDigitSum;
            minIndex = i;
        }

        threeDigitSum = (sumOfTwo + A[i + 2]) << 1;
        if (minAvgVal > threeDigitSum) {
            minAvgVal = threeDigitSum;
            minIndex = i;
        }
    }

    sumOfTwo = A[size - 2] + A[size - 1];
    twoDigitSum = 3 * sumOfTwo;
    if (minAvgVal > twoDigitSum) {
        minIndex = (size - 2);
    }

    return minIndex;
}

Как видите, sumOfTwo является примером использования префикса Sum.

Ответ 26

100% раствор Scala

  def solution(a: Array[Int]): Int = {
    val n = a.length
    var min = Double.MaxValue
    var minPos = 0
    for (i <- 0 to n - 2) {
        val sum2: Double = a(i) + a(i+1)
        var avg = sum2 / 2
        if (i < n - 2) {
            avg = Math.min(avg, (sum2 + a(i+2)) / 3)
        }
        if (avg < min) {
            min = avg
            minPos = i
        }
    }
    minPos
  }

Ответ 27

Решение Python (100% проход)

def find_2_lowers(A):
    total = 10001 + 10001
    x_pos = 0
    y_pos = 0
    for i,j in zip(range(len(A)), range(1, len(A))):
        if j == len(A):
            return x_pos, y_pos, total
        if A[i] + A[j] == total:
            continue #ignoring the more deeply index
        elif A[i] + A[j] < total:
            total = A[i] + A[j]
            x_pos = i
            y_pos = j


    return x_pos, y_pos, total

def find_3_lowers(A):
    total = 10001 + 10001 + 10001
    x_pos = 0
    y_pos = 0
    z_pos = 0
    for i,j,k in zip(range(len(A)), range(1, len(A)),range(2, len(A))):
        if k == len(A):
            return x_pos, y_pos, z_pos, total
        if A[i] + A[j] + A[k] == total:
            continue #ignoring the more deeply index
        elif A[i] + A[j] + A[k] < total:
            total = A[i] + A[j] + A[k]
            x_pos = i
            y_pos = j
            z_pos = k

    return x_pos, y_pos, z_pos, total

def solution(A):
    if len(A) <= 2:
        return 0

    x2,y2,total2 = find_2_lowers(A)
    x3,y3,z3,total3 = find_3_lowers(A)

    #print("x2,y2,total2 ", x2,y2,total2 )
    #print("x3,y3,z3,total3 ", x3,y3,z3,total3 )

    if total2/2 < total3/3:
        return x2
    elif total2/2 == total3/3:
        return min(x2, x3)
    return x3