Тест для интервью: самая глубокая яма

Ответ 1

Не кажется слишком сложным. Одного цикла достаточно. Вы храните два триплета, один из них лучший, а другой - как рабочий набор.

• 1) Отметьте первый элемент как P в рабочем наборе
• 2) Прочитайте элемент, а Q не отмечен
  • Если значение меньше предыдущего, продолжайте движение: 2)
  • Если значение больше или равно предыдущему, отметьте предыдущее как Q
  • Если у вас заканчиваются номера, то это не настоящая яма, goto 6)
• 3) Прочитайте элемент, пока R не отмечен
  • Если значение больше предыдущего, продолжайте движение: 3)
  • Если значение меньше или равно предыдущему, отметьте его перед ним как R
  • Если у вас закончились номера, отметьте последний как R, перейти 4)
• 4) Решите, лучше ли это лучше, это довольно просто.
• 5) Отметьте предыдущий элемент как P в рабочем наборе, установите Q = R = null, перейдите к 2), если у вас есть какой-либо элемент слева
• 6) Если наилучшее значение равно 0 глубокому или нулевому, то ямы не найдены

Нужен исходный код для этого?

UPDATE:

Исходный код:

    int A[]= {0, 1, 3, -2, 0, 1, 0, -3, 2, 3};
    int depth = 0;

    int P = 0, Q = -1, R = -1;

    for (int i = 1; i < A.length; i++)
    {
        if (Q < 0 && A[i] >= A[i-1]) 
            Q = i-1;

        if ((Q >= 0 && R < 0) && 
            (A[i] <= A[i-1] || i + 1 == A.length))
        {
            if (A[i] <= A[i-1])
                R = i - 1;
            else
                R = i;
            System.out.println(P+"  "+Q+"  "+R);
            depth = Math.max(depth, Math.min(A[P]-A[Q], A[R]-A[Q]));
            P = i - 1; 
            Q = R = -1;
        }
    }
    if (depth == 0) depth = -1;
    System.out.println("Depth: "+depth);

Я не тестировал для каждого случая, но он работает нормально.

Ответ 2

Пусть:

dp1[i] = longest decreasing substring ending at i     
dp2[i] = longest increasing substring starting at i

Имеем:

dp1[i] = dp1[i - 1] + 1 if A[i - 1] > A[i]
         1 otherwise

dp2[i] = dp2[i + 1] + 1 if A[i + 1] > A[i]
         1 otherwise

Теперь Q в вашей проблеме представляет dp1[Q] + dp2[Q].

Каждый массив может быть вычислен в O(n): для dp1 сканировать влево-вправо, для dp2 сканировать вправо.

Ответ 3

Вот что я получил. Вспоминая, что для наибольших глубин и зная, что A [P] > A [Q] A [R], мы хотим:

• Самый большой A [P] → последний из уменьшающейся цепочки
• Самый маленький A [Q] → первый из восходящей цепочки

• Самый большой A [R] → последний из восходящей цепочки

  public static int dp(int[] A) {
  int length = A.length;
  
  if (length < 3) {
      return -1;
  }
  
  int currentDepth = 0;
  int maxDepth = -1; 
  
  int P, Q, R; 
  int i, j, k; 
  for (i=0; i<length-2; i++) {
      j=i+1;
  
      if (A[i] > A[j]) {
          //The biggest P.
          P = A[i];
  
          while (j+1<length && A[j]>A[j+1]) {
              j++;
          }
          //The smallest Q.
          Q = A[j];
  
          k = j+1;
          while (k+1<length && A[k]<A[k+1]) {
              k++;
          }
          if (k >= length) {
              break;
          }
          //The biggest R.
          R = A[k];
  
          System.out.println(i+"  "+j+"  "+k);
  
          currentDepth = (int)Math.min(P-Q, R-Q);
          if (currentDepth > maxDepth) {
              maxDepth = currentDepth;
          }
          i = k-1;
      }
  }
  
  return maxDepth;
  

  }

Ответ 4

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

    int[] a = {0, 1, 3, -2, 0, 1, 0, -3, 2, 3 };
    int p = 0, q = -1, r = -1;
    int depth = -1;

    for(int i = 1; i < a.length; i++) {
        if(q < 0) {
            if(a[i] < a[i-1]) {
                q = i;
                continue;
            } else {
                p = i;
                continue;
            }
        }

        if(a[i] > a[i-1]) {
            r = i;
            depth = Math.max(depth, Math.min(a[p] - a[q], a[r] - a[q]));
        } else if(r < 0){
            q = i;
        } else {
            q = i;
            r = -1;
            p = i - 1;
        }
    }

    System.out.println("depth = " + depth);     

Ответ 5

Это мое решение в С#. Получил 100/100 на Codility

public int solution(int[] A) {
    // write your code in C# 5.0 with .NET 4.5 (Mono)    
    int P = -1, R = -1, Q = -1, depth = -1;

    for(int i = 0; i < A.Length - 1; i++){
        if(Q < 0){
            if(A[i] > A[i+1]){
                Q = i +1;    
                P = i;
            }
        }
        else{
            if(R < 0){
                if(A[i] > A[i + 1])
                    Q++;

                if(A[i] < A[i + 1])
                    R = i + 1;    

                if(A[i] == A[i + 1]){
                    P = Q = R = -1;    
                }
            }
            else{
                if(A[i] < A[i + 1])
                    R++;
                else{
                    depth = Math.Max(depth, Math.Min(A[P] - A[Q], A[R] - A[Q]));

                    if(A[i] > A[i + 1]){
                        P = i;
                        Q = i + 1;
                        R = -1;
                    }
                    else{
                        P = Q = R = -1;    
                    }
                }
            }
        }
    }

    if(R > 0){
        depth = Math.Max(depth, Math.Min(A[P] - A[Q], A[R] - A[Q]));
    }

    return depth;
}

Ответ 6

Ответ, имеющий временную сложность O (n).

private static int fun1(int[] a) {
        // TODO Auto-generated method stub
        int P[] = new int[a.length];
        int Q[] = new int[a.length];
        int R[] = new int[a.length];
        int p = 0, q = 0, r = 0;
        int tmp = 0;
        int tmp2[] = new int[a.length];
        boolean flag1 = false, flag2 = false;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                if (flag1 == true)
                    continue;
                //
//              System.out.println("CHK....");
                flag1 = true;
                tmp2[p] = i;
                P[p++] = a[i];
            } else
                flag1 = false;
        }
        for (int i = tmp2[0]; i < a.length - 1; i++) {
            if (a[i] < a[i + 1]) {
                if (flag1 == true)
                    continue;
                //
//              System.out.println("CHK....");
                flag1 = true;
                tmp2[q] = i;
                Q[q++] = a[i];
            } else
                flag1 = false;
        }
        int tmp3 = 0;
        for (int i = a.length - 1; i >= 0; i--) {
            tmp2[tmp3++] = a[i];
            //
    //      System.out.print(a[i] + " ");
        }
        flag1 = false;
        for (int i = 0; i < tmp2.length - 1; i++) {
            if (tmp2[i] > tmp2[i + 1]) {
                if (flag1 == true)
                    continue;
                //
    //          System.out.println("CHK....");
                flag1 = true;
                // tmp2[p]= i;
                R[r++] = tmp2[i];
            } else
                flag1 = false;
        }
        int finalLength = q;
/*
        System.out.println("P---->");
        for (int i = 0; i < finalLength; i++) {
            System.out.print(P[i] + " ");
        }
        System.out.println("\nQ---->");
        for (int i = 0; i < finalLength; i++) {
            System.out.print(Q[i] + " ");
        }
        System.out.println("\nR---->");
        for (int i = finalLength - 1; i >= 0; i--) {
            System.out.print(R[i] + " ");
        }
*/
        int depth[] = new int[a.length];
        int d3 = 0;
        for (int i = 0; i < finalLength; i++) {
            int p1 = P[i] - Q[i];
            int p2 = R[finalLength-1-i] - Q[i];

            depth[d3++] = p1 > p2 ? p2 : p1;
        }
        int maxDepth = depth[0];

        for (int i = 1; i < d3; i++) {
            if (maxDepth < depth[i])
                maxDepth = depth[i];
        }
        return maxDepth;
    }

Ответ 7

Это мое решение, написанное на С++, но его можно легко переписать на Java. Решение касается склона, например, следующий массив чисел 3, -1, 2, 4 содержит два наклона (3, -1) = -4 и (-1, 2, 4) = 5. Поэтому, когда отрицательный наклон за которым следует положительный уклон, у нас есть яма. В этом случае min (- (- 4), 5) = 4.

int solution(const vector<int> &a)
{
    if (a.size() < 3)
        return -1;

    int slope = 0;
    int previousSlope = 0;
    int deepestPit = -1;

    for (size_t i = 1; i < a.size(); i++)
    {
        const int& currentElem = a[i];
        const int& previousElem = a[i-1];

        int elemDiff = currentElem - previousElem;

        if ((slope >= 0 && elemDiff > 0) || (slope <= 0 && elemDiff < 0))
        {
            slope += elemDiff;
        }
        else
        {
            previousSlope = slope;
            slope = elemDiff;
        }

        if (previousSlope < 0 && slope > 0)
        {
            int currentPit = min(-previousSlope, slope);
            deepestPit = max(currentPit, deepestPit);
        }
    }

    return deepestPit;
}

Ответ 8

int solution(int[] a) {
    if (a.length < 2) return -1;

    int p=0, q=-1, r=-1;
    int max = Integer.MIN_VALUE;
    int i = 1;
    while (i < a.length) {
        while(i < a.length && a[i - 1] > a[i]) {
            q = i++;
        }
        while(p < q && i < a.length && a[i - 1] < a[i]) {
            r = i++;
        }
        if (q != -1 && r != -1 && p < q && q < r) {
            System.out.println("p = " + p + " q = " + q + " r = " + r);
            max = Math.max(max, Math.min(a[p] - a[q], a[r] - a[q]));
            p = r;
            q = r = -1;
        } else {
            i++;
        }
    }

    return max == Integer.MIN_VALUE ? -1 : max;
}

Ответ 9

Я нашел лучшее решение, которое Matzi предоставило.

Вот мой эквивалент Swift 3:

    var A = [0, 1, 3, -2, 0, 1, 0, -3, 2, 3]
    var depth = 0
    var P = 0
    var Q = -1
    var R = -1

    for i in 1 ..< A.count {
        if Q < 0 && A[i] >= A[i-1] {
            Q = i - 1
        }

        if (Q >= 0 && R < 0) && (A[i] <= A[i-1] || i + 1 == A.count) {
            if A[i] <= A[i-1] {
                R = i - 1
            } else {
                R = i
            }
            depth = max(depth, min(A[P] - A[Q], A[R] - A[Q]))
            P = i - 1
            Q = -1
            R = -1
        }
    }

    if depth == 0 {
        depth = -1
    }

    print(depth)

Ответ 10

Это мое решение в Python.

def solution( A ):

  P = 0 
  Q = -1
  R = -1

  max_depth = 0
  best = (P, Q , R);

  length = len(A)

  if length < 3:
    return -1

  curr_depth = -1

  for i in range(0,length-2):

    if A[i] > A[i+1]:
      P = i
      Q = P
      j = i

      while A[j] > A[j+1] and j < length-2:
        j += 1
        Q = j
        R = Q

      k = Q
      while k < length-1 and A[k+1] > A[k]:
        k += 1
        R = k

      if P<Q and Q<R:
        curr_depth = min(A[P]-A[Q], A[R]-A[Q])
        if curr_depth > max_depth:
          max_depth = curr_depth
          best = (P, Q , R);

  if curr_depth == -1 or (Q==-1 and R==-1):
    return -1


  return [best, max_depth]

Ответ 11

int[] A =  new int[] {0, 1, 3, -2, 0, 1, 0, -3, 2, 3 };
        int P,Q;
        boolean first_time = true;
        int depth = -1;

        for ( P=0; P < ( A.length -1 ); P++ ) 
        {
           if(A[P] > A[P+1])
           {
               for(Q =P+1; Q <( A.length -1 ); Q++)
               {
                   if(A[Q-1] > A[Q])
                   {
                       if(A[Q] < A[Q+1])
                       {
                            int temp_depth = Math.min(A[P] - A[Q], A[Q+1] - A[Q]);

                            if(first_time){ depth = temp_depth; first_time = false; }

                            if ( depth < temp_depth ) depth = temp_depth;

                            System.out.println("Depth of (" + P + "," + Q + "," + (Q+1) + ")=" + depth);

                            break;
                       }
                   }
               }
           }
        }
        System.out.println("Depth:" + depth);